A Random Place at the Table

Can you find a shortcut for solving problems that seem to require a lengthy calculation?

Olena Shmahalo/Quanta Magazine

63

Have you ever encountered a problem that seemed to require a lengthy calculation only to realize that, with a simple shortcut, you can solve it in your head?

A paradigmatic problem of this kind is that of the two bicyclists and the fly:

Two bicyclists start 20 miles apart and head toward each other, each going at a steady rate of 10 mph. At the same time, a fly starts flying at a steady 15 mph from the handlebar of the one bicycle to the handlebar of the other one, and then turns around and flies to the first one again, continuing in this manner back and forth until the bicyclists meet. What total distance did the fly cover?

The “obvious” and standard way to find the answer is to add up the distance that the fly covers on the first leg of the trip, then on the second leg, then on the third, and so on. Each distance gets smaller and smaller, giving an infinite series of distances, which can be summed.

A monthly puzzle celebrating the sudden insights and unexpected twists of scientific problem solving. Your guide is Pradeep Mutalik, a medical research scientist at the Yale Center for Medical Informatics and a lifelong puzzle enthusiast.

There is, however, a simpler way. Notice that the bicycles meet exactly one hour after their start, so that the fly had exactly one hour of flying time. Since the fly’s speed was a constant 15 mph, the answer must be 15 miles.

Legend has it that a version of this question was put to John von Neumann, the incandescent genius who laid the mathematical foundations of quantum mechanics and game theory. Von Neumann’s calculating ability was so stratospheric that many of his peers, brilliant themselves, thought of him as “the smartest man in the world.” As expected, von Neumann solved it in an instant. His questioner said in disappointment, “Oh, you’ve heard the trick before!”

“What trick?” von Neumann reportedly said. “All I did was sum the geometric series.”

Here’s our problem this month. You don’t have to be a von Neumann to solve it!

A clubhouse for a cult has a table with 10 chairs. There are five people who sit around it, occupying a chair each, completely at random. They call their original chairs the “anointed” chairs. After half of the meeting is done, all five people get up and move clockwise to different places, each one moving the same number of places as the others, so that their positions relative to one another are not changed. They have to do so, however, in a way that maximizes anointed chairs. Show that no matter what their original positions were, they can always find new places such that at least three of the anointed chairs are used for the second sitting.

The obvious — and long — way to solve this is to consider all possible positions around the table that five people can occupy (how many?) and then show for each that there is some number of places the cultists can move so that three or more chairs are reused. This would probably require a computer program. But there is a simpler way. Can you find it?

Finding such “short circuit” solutions can be thrilling and, for some, addictive. Here’s a bonus problem for those who can’t get enough:

A ball is thrown up in the air from a certain height. It rises to a maximum height and falls back to the initial height. Does it take longer to go up from its starting to its maximum height or longer to fall down from the top of its flight back to its initial height?

In high school physics, when students are asked to solve such problems, they are told to neglect air resistance. Then you can apply the standard equations of projectile motion and find that both times are the same. But what if you do not ignore the turbulent drag of the air on the ball, which is proportional to the square of the ball’s velocity? Do the times still remain the same or does that change? Factoring in the drag makes the problem much harder if you try to do it the usual way. But you can still answer the above question simply if you short circuit it!

I invite readers to share their favorite “short circuit problem.” Please share your insights with all of us.

Editor’s note: The reader who submits the most interesting, creative or insightful solution (as judged by the columnist) in the comments section will receive a Quanta Magazine T-shirt. (Update: The solution is now available here.) And if you’d like to suggest a favorite puzzle for a future Insights column, submit it as a comment below, clearly marked “NEW PUZZLE SUGGESTION” (it will not appear online, so solutions to the puzzle above should be submitted separately).

Note that we will hold comments for the first day or two to allow for independent contributions.

• Jake Soloff says:

We want to show that the 5 clubhouse members can always find a way to shift to the right some number of chairs so that at least 3 of them are still sitting in anointed chairs. Since there are 10 chairs, there are 9 distinct ways that they could choose to shift—that is, they can all move to the right by 1, 2, 3, 4, 5, 6, 7, 8, or 9 chairs (if they try to shift by 10 then they effectively have not shifted at all).

If the clubhouse members pick the shift number uniformly at random, we can determine on average how many of them are still sitting in anointed chairs. For any given anointed chair, the 4 members who do not start out in that chair can each shift into that position: this means 4/9ths of the time (when the shift number is random), that anointed chair will be occupied after the shift. Since there are 5 anointed chairs, on average 5*4/9 = 20/9 anointed chairs will be occupied. Because 20/9 is bigger than 2, at least one of the possible shifts must have used more than 2 anointed chairs!

• eJ says:

Summing over the nine allowed options for the second sitting, each anointed chair gets visited four times (once by each occupant other than the original), so that's 20 anointed visits total. So at least one option has at least three anointed visits, since otherwise the total could be no more than 18.

The ball thing looks like it should take longer on the return journey, as drag is effectively adding to gravity on the way up and subtracting from it on the way down. Weaker gravity => longer journey time.

Another simple short-cut puzzle: a laser beam is fired into a V-shaped mirror, aiming parallel to one of the sides; if the angle inside the V is five degrees, how many times does the beam bounce?

• Jon says:

Start with any random seating configuration. Everyone gets up and moves clockwise by one seat, you count the number of people sitting in anointed seats in this configuration and lay that many illuminati coins on the table. Everyone gets up and moves clockwise again by one seat, again you count the number of people sitting in anointed seats in this new configuration and lay that many more illuminati coins on the table. After 10 moves everyone will be sitting in their original seat. After 9 moves (one move before everyone is back in their seat), each of the five anointed seat will have had 4 people sit in it. Thus, there will be 4×5 = 20 illuminati coins on the table when everyone returns to their original seat. But if in each of the 9 configurations, there were a maximum of 2 people sitting in anointed seats, there would be a maximum of 18 illuminati coins on the table. Thus there must be at least one configuration with more than 2 anointed seats being sat in.

Throw a ball up in the air from some starting height and it returns back to that initial height. In the absence of air resistance, at each height, the ball will have the same speed on the way down as on the way up. If you add air resistance, some of that speed will be dissipated to that drag. Thus on the way down it will be moving slower than it was on the way up at that same height. (In other words, it decelerates faster than gravity alone on the way up and it accelerates slower than gravity alone on the way down.) So the ball covers the same distance faster on the way up. The ball takes longer to go down.

• Chris says:

If moving each one sectarian seat clockwise would result in 3 or more unanointedly ensconsed cultists, then there remain 2 or fewer unanointed of the remaining 5 chairs, so 3 or more (of the remnant 5) must have been heretofore consecrated, meaning a two seat swing of cathedrae will achieve the required quorum of hallowed tuckuses.

• Zak says:

The problem of the girls around the table can be solved by considering that this problem is equivalent to proving that a collection any 9 integers between 0 and 4 (Including 0 and 5) that sum to 20 must contain at least one integer greater than or equal to 3. The reason this is true is that there are 5 girls and 5 special seats, and 9 possible positions different from the starting position, so there are always exactly 20 instances of a girl getting an anointed chair after 9 single chair rotations (this is because for 5 girls, there are 5 anointed chairs, and when the girls travel all the way around they must reach every seat, so therefore every chair must be sat in by everyone, resulting ing 5*5 = 25 chair-sittings, however each girl has her own chair which she cannot sit in unless everyone returns to their original sitting arrangement, so those 5 aren't considered and we get 20), and so by summing the number of girls in an anointed chair each round for 9 rounds, you must get 20. By proving that any collection of 9 integers that sum to 20 contain at least a 3, we show that any setup of girls around the table has a seating arrangement with girls occupying 3 chairs that they occupied before.

An entertaining way to prove this is by considering the "worst case", which is 5 + 5 + 5 + 5 + 0 + 0 + 0 + 0 which contains the largest possible numbers summing to 20. This corresponds to the table setup where all five girls sit in evenly spaced out intervals, and the sum is really 0 + 5 + 0 + 5 + 0 + 5 + 0 + 5 + 0. Now we're going to change the seating arrangement: If we try to "spread out" the fives into the 5 vacant cells by removing 3 from each one (reducing it to a two, if we took less than that it would still be a 3 and this procedure would be useless) which gives us an extra 12 instances to distribute (each distribution of numbers corresponds to a different seating arrangement around the table) This essentially reduces the problem to 12 as a sum of 4 integers, and the best you can do is 2+2+3+3, if you lower one three the other must increase, and so therefore a collection of 4 integers between 0 and 5 which sum to 12 must contain at least 1 (in fact 2) elements >3, and therefore the same is true for 20 because we already reduced 20 to (12)+(2+2+2+2)=(3+3+2+2+2+2+2+2) which has the exact same property as the collection of integers before.
QED
I wanted to keep this in simple language so I avoided using words like set and also tried to explain why things are true rather than just saying "PIGEONHOLE PRINCIPLE, THESE GIRLS ARE SOCKS IN A DRAWER, QED"

• Broc Seib says:

The one "short circuit" problem I remember is one that I think I read from The Moscow Puzzles as a kid. It went something like this:

A spider and a fly each sit at opposite corners of a box. The dimensions of this box are 2' x 4' x 1'. What is the shortest path the spider may take to reach the fly?

• Greg Egan says:

For each of the five people, we can ask how many places they would need to move counterclockwise to occupy the original chair of one of the other four people. This gives us five sets of four distinct integers, all of which lie between 1 and 9.

If we look at the numbers between 1 and 9, and count how many of the five sets each number belongs to, the total of these 9 counts must equal 20: the total number of elements in all five sets. If the 9 counts were all less than or equal to 2, the total would be less than or equal to 18. So at least one number between 1 and 9 must belong to 3 or more sets, and if the five people all move by that number of places, at least 3 of them will end up in “anointed” chairs.

• Greg Egan says:

Since the ball loses energy to air resistance, it must return to its initial height travelling more slowly than it was thrown. But the same is true for every height it passes through, on its way from the initial height to the maximum height: between its ascent through that height and its descent, it loses some energy to drag.

So, at every height, the ball is travelling more slowly during its descent, and the total time for the descent must be longer than the total time for the ascent.

• Chiu-king Ng says:

—— The Throwing Ball Physics Problem ——-
Suppose the experiment is done in an environment of "nearly-zero gravity".
In spite of this, when the ball goes up, it still decelerates because of air resistance.
After reaching the top, the ball becomes essentially stationary, so it requires an infinitely long time to fall back to the initial height. In other words, the time for it falling down is much longer than that of going up.
At the other extreme, when the gravity is exceedingly large and hence it completely dominates over the air resistance, the two times will approach to be the same.
So we believe that whatever the cases lying between, the time of falling down should always be longer than that of going up.

• Morris Ang says:

For the cult problem:
The cleanest way to view this problem is via the probabilistic method: There are 9 seating choices available: shift by 1, shift by 2, …, shift by 9. If we pick among the 9 seating options uniformly at random, the probability that any particular cultist obtains an anointed chair is 4/9. By the linearity of expectation, the expected number of cultists sitting in anointed chairs is 4/9*5 = 20/9 > 2. Since the best arrangement does at least as well as the average, the best arrangement has at least 3 cultists sitting in anointed chairs.

An alternative, but equivalent way, is by counting the number of cultist-anointed chair pairs among all the seating possibilities. For any particular cultist, 4 of the 9 choices will allow the cultist to sit at an anointed chair. Thus, the 9 seating choices have a total of 4 x 5 = 20 cultist-anointed chair pairs. Thus some seating option gives rise to at least 20/9 > 2 cultists sitting in anointed chairs. Clearly the actual number of cultists sitting in anointed chairs is an integer, and hence at least 3.

In fact, this bound is tight. The following circular arrangement is easily checked to allow at most three cultists to sit in anointed chairs:
CCXCCCXXXX, where C represents a cultist and X an empty chair.

Finally, here's a solution to the bonus problem. Consider the initial speed and final speed of the ball (at the initial height). Air resistance causes the ball to lose energy, hence the initial speed is greater than the final speed. Notice that this argument holds not just for the initial height, but also at any height: the ball is going faster on its way up than on its way down. Since, height for height, the ball is traveling faster on the way up than on the way down, it takes longer to fall than it does to rise.

• Mukund Thattai says:

A meta-puzzle for problems with short-circuit solutions: provide just enough information to prove you have the answer without giving away the actual answer!
Here's my attempt: XX in IX.

• Ian says:

Still thinking about anointed seats, but the ball problem seems obvious. With drag, falling takes longer than rising.

Without drag the rise and fall of the ball are mirror images.

Add in drag. The rising ball is slowed to rest by gravity plus drag. The mirror image would be a falling ball accelerated from rest by gravity plus drag. The actual fall is accelerated from rest by gravity MINUS drag – by less, in other words. So it will take longer to cover the same distance.

• Anil Agarwal says:

Random Circular Seating:
Let's take all 9 rotation choices available to the cult members. (Obviously, a rotation by 10 seats must be disallowed to keep the problem interesting).
Together in the 9 rotations, any given member will be seated once in each of the 4 other anointed chairs.
Among all 5 members, the aggregate number of anointed chairs used across all 9 rotations = 5 * 4 = 20.
The average number of anointed chairs per rotation = 20 / 9 = 2.22.
Some rotations will have less than 2.22 anointed chairs in use, some more, the actual numbers must be integers.
If all rotations contained 2 or fewer anointed chairs in use, then the average would be less than or equal to 2.
Hence, there must be at least one rotation with 3 anointed chairs to bring the average to 2.22.
Similarly, there must be at least one rotation with 2 anointed chairs.
QED.

Drag:
Assume that the ball is thrown up with initial velocity v.
1. With no drag, the ball will rise to a certain height H and fall back and reach velocity v at the end of its downward journey. The average velocity will be identical in the upward journey and the downward one.
2. Now assume drag on the journey upward, but no drag on the way down.
The height of the ball will be H', where H' < H.
On the way down, the final velocity of the ball v' will be less than v, since it traveled a smaller distance than in case 1. Hence, the average velocity of the ball is smaller on the way down; hence the downward journey duration is larger than the upward journey duration.
3. Now assume drag on the journey up and down. The final velocity on the downward journey v'' will be less than v'. Hence, the downward journey will take longer than in case 2.

• Rob says:

As the 5 people cycle around the table to the 9 other possible positions, each of them will occupy 4 anointed chairs, giving a total of 20 anointed chair seatings. If each rotation had at most 2 anointed chair seatings, there would be at most 18 anointed chair seatings in total, giving a contradiction.

• Anil Agarwal says:

The chair seating problem can easily be generalized to N chairs and M members.
No matter what their original positions are, the members can always find a rotation such that at least A of the anointed chairs are used for the second sitting,
where A = ceiling(M * (M -1 ) / (N – 1))

• Wiley says:

(1) Since the relative positions are fixed, there are 9 new
configurations for the group to try. We consider the total number of
"anointed" chairs that would be re-used of these new configurations,
i.e, the whole group move sequentially to the next chair clock-wise 9
times, record the number of re-used chairs each round and sum them up.
Since each person would encounter the 4 other "anointed" chairs that
she wasn't in, the result is 5 x 4 = 20. By the pigeonhole principle,
there is at least one configuration that have > floor(20/9) = 2 (i.e.,
at least 3) "anointed" chairs.

(2) It takes longer to fall down from the top. One way to see this is
to consider the time-reveral "process" of the ball rising to the
maximum height, which takes equally long as the original rise (note
the quotes are used to indicate that it is NOT physical but the
underlying Newtonian law does have the T-symmetry).

Now it's staightforward to compare it with the actual process of the
ball falling down from the top, as both have the same start and end
points. Instead of the air drag decelerating the ball, the
time-reveral "process" has both the gravity and the air drag
accerlerating it, thus the ball in the time-reversal has a strictly
larger speed at any time than in the physical falling, which means
it takes shorter time on its way up.

Speaking of time-reversal, here is a nice problem:
There are n balls colored 1 to n. Each time you pick two balls, both
uniformly at random. You paint the second ball with the color of the
first and put them back into the box. What is the expected number of
times this needs to be done so that all balls end up with the same
color?

I would also recommend the book "Proofs from THE BOOK", dedicated to
Paul Erdős. One of my personal favorites is the proof of Monsky's
theorem.

• Shubhankar says:

1) If the order of the people doesn't change, then if we focus on any one of them, there could always be found a way in which he would sit back on his own annointed seat and hence the others would too, therefore occupying all five annointed seat, which is of course more than three.

2) Remembering from high school physics, in each arm of motion, the ball travels at same speeds for similar time intervals and if the drag depends on speed only and is opposing, the effect is same in both arms, so same time. Also since drag slows down the motion, the time would be less than that in the case of no drag.

That it?

• Daniel Briggs says:

For the main problem:

One can think of it in terms of "anointed chairings," by which I mean occasions in which a person sits in an anointed chair. In the original set-up, there are five anointed chairings; considering the other nine set-ups, there must be twenty more, one for each time when a person sits in any of the other four chairs. But if there were only at most two people sitting in anointed chairs in each of the other nine set-ups, that could only add up to at most eighteen more anointed chairings, which is a contradiction. Thus, there must be at least one set-up among the other nine in which at least three people sit in an anointed chair.

For the bonus problem:

On the way up, gravity and drag are working in the same direction: against the ball's motion. On the way down, gravity is working with the ball's motion and drag against it.

But let's consider what happens if instead of seeing it through to the end, we play the first part of the movie backwards after the ball reaches its peak. What would we see? This mysterious acceleration, beyond that of gravity, working with the motion of the ball. And that's what would cause the ball to descend in the same amount of time in which it ascended.

So back in reality, where drag works against the motion of the ball, it takes longer.

Nice tie-in with the fly problem; we can often introduce or remove mirrors to help us figure out a problem. It's useful to keep on hand for billiards problems (both theoretical and in real life), as well as the 100 ants problem:

Minuscule (point-sized) ants are at every integer point in [1,100], which is a stick. The first fifty move forward, and the other fifty move backward, each at a speed of 1. Whenever two run into each other, they each reverse direction. How long is it until they all have exited the stick?

• Oskar Goldhahn says:

The anointed chairs will form groups split apart by unanointed chairs. There will be between one and five groups and there will always be the same number of unanointed groups as anointed groups. Each group of anointed chairs by definition has an unanointed chair to the right of it. This means that if we have 3 or more groups then we can just let everyone move one step to the right to fill at least 3 unanointed chairs. In the case of two or less groups one of the groups will have to have three chairs or more and the same holds for the groups of unanointed chairs. This means that there are at least three consecutive unfilled chairs and at least three consecutive people to fill them.

• Krasimir Avramski says:

It is simple pigeonhole principle.

Let consider arbitrary ititial chair position i1, i2, i3, i4, i5. 0<= ij <= 9, j=1..5. Let consider matrix M of digits:
i1 i2 i3 i4 i5
i1+1 i2+1 i3+1 i4+1 i5+1
i1+2 i2+2 i3+2 i4+2 i5+2
……………
i1+9 i2+9 i3+9 i4+9 i5+9

Where, if we have ij+k=10 for some j=1..5 and 0<=k<=9 then we substitute ij=0

Matrix M describes all possible rotations of anoined chair positions around the table center.

Note that in each column of matrix M every digit 0..9 is met exactly 1 time, so the digits i1 i2 i3 i4 i5 are met exactly 5 times and are totally 5×5=25.

Let assume there are at most 2 occurances at every row of digits i1 i2 i3 i4 i5 except the first row.
Then the sum of digits i1 i2 i3 i4 i5 in matrix M would be no more than 5 + 9×2 = 23, which is contradiction.

• Susan Williams says:

Solution to the problem of the month:

Consider all nine of the possible (non-identity) clockwise rotations. Each of the five members will occupy each of the other chairs in turn. Four of these chairs are anointed, giving a total of 20 anointed chairs occupied in nine rotations. Since nine times two is only 18, one rotation must occupy at least three anointed chairs.

I won't answer the main problem. (It uses a standard trick in my field–combinatorics–so I'll leave it to those who haven't seen it before.)

The bonus problem is wonderful. What I particularly enjoyed was that when I started thinking about it, I had no immediate intuition about what the answer should be.

Consider the two points in time when the ball reaches a given height h (at or above the starting height). At each time, it has a gravitational potential energy and a kinetic energy. The gravitational potential energy is the same both times, because it depends only on the mass and height of the ball. As friction acts during the flight of the ball, total mechanical energy decreases, so the kinetic energy is less the second time the ball reaches height h. Kinetic energy is proportional to velocity squared, so the velocity was greater on the way up.

Since the velocity was greater at every point on the way up than at the same point on the way down, the ball took a shorter time to go up than to go down!

• João Rimu says:

I am too tired to try to solve the problems (I liked the one with air resistance :D), but since the writer also asked readers to share their favourite problems, here is mine (I will paraphrase it to be equivalent to the one I learned from Peter Winkler's book "Mathematical Puzzles: A Connoisseur's Collection", I do not want to infringe any copy-right, even though the problem probably did not originate with him (the book is from 2003):

* On the floor there is a row of seventy coins, of many different values. Maria chooses a coin from one of the ends and puts it in her bag, and then João chooses a coin from one of the ends the way they became and puts it in his pocket, and this trundle goes on until João picks the last of the coins. We ask you to prove that there is a strategy for Maria such that she can play to secure at least as much money as João.

(Winkler's original redaction is much better, but as I said, I do not want to infringe copyrights)

I remember it took me 30 minutes to solve this problem, and when I got it, it was like "Lol, it was so easy". 😀

• BC says:

This is a nice one! Here's my solution, I'm guessing that it's the one that most other people have as well…
For each rotation of the table we want to count the number of anointed seats that are occupied. While the problem asks for the minimum of the maximum of this number over all possible nontrivial rotations, we find a quantity we can count: the average over all rotations. Every anointed chair will see 4 people as we range over all nontrivial rotations, so in total there are 4*5=20 instances of someone sitting in an anointed chair. Now there are 9 nontrivial rotations, so on average there are 20/9>2 many anointed chairs taken during each rotation. Therefore there is a rotation where there are at least 3 occupied anointed seats.

• John Chase says:

Suppose for the sake of reaching a contradiction that there is a Cursed Seating Arrangement such that we ALWAYS end up with two or fewer cult members sitting in anointed chairs in all nine rotations of that arrangement.

This implies that if we iterate through all nine rotations of our Cursed Seating Arrangement, that the cult members will visit no more than 18 anointed chairs, collectively.

But on the other hand, it's easy to see that the cult members will make exactly 20 visits to the anointed chairs. This is because each of the five cult members will visit four other anointed chairs while iterating through all the rotations of a given seating arrangement.

Thus we reach a contradiction, and there is no such Cursed Seating Arrangement. That is to say, in *all* possible arrangements, the cult members will be able to rotate to a place where they occupy three or more anointed chairs.

• Laurence Reeves says:

For the main problem, let's have N sitters and 2*N possible sitting positions. Consider the "anointedness" of the sittings as the number of occupied anointed chairs. We know the initial position happens to have "anointedness" of N. As each sitter move around the table, they sit in an anointed chair exactly N times. So the total of all sittings "anointedness" counts will be exactly N^2. Leave out the initial position, and take the average of the "anointednesses" – gives us (N^2-N)/(2*N-1). When we get to N=5, we have this average as 20/9, which is larger than 2, hence at least one sitting must have three anointed chairs occupied.

The bonus problem – conservation of energy easily shows us that the ball must be travelling strictly slower at every point on its descent, versus its speed at the hight on the ascent – hence the descent must take longer.

One of my favourite short cuts, from school days, was geometric. Take an arbitrary triangle. Pick an arbitrary point on each side. For each pair of those points, find the intersection of the line through those points with the third side of the triangle (projected as necessary). Prove those three new points are collinear.

• Geoffrey Berresford says:

Here is a solution to the ten-chairs problem.

1) On circle mark with an X the 5 anointed seats out of the 10 possible positions.

2) Cut a circle of the same size and cut holes in it corresponding to the anointed positions. Lying the second circle on top of the first in the “initial” position, all five Xs will show through the holes. Rotating the second circle on top of the first through nine shifts will give all possible positions for the nine new seating choices, and for each of these shifts, the occupied anointed seats will show as Xs through the holes.

3) Suppose that the claim is false. Then there is some initial choice of anointed seats for which all nine shifts will show (through the holes) two or fewer Xs. In this case, rotating the second circle through its ten possible positions and counting the total number of Xs showing will give at most 5+2+2+2+2+2+2+2+2+2 = 23 Xs. But each hole rotates around all ten seats and will show each of the five Xs exactly once, so the five holes will show a total of 5×5 = 25 Xs, meaning that the count of 23 cannot happen. Therefore, the claim cannot be false.

• David Travasos says:

Figure this one out while calculating if the "sale" price of broccoli is really a "sale"!

• Philip Calcott says:

The trajectory of the ball with air resistance must be asymmetric with regards to up and down, energy conservation reqires this. Consider any vertical position of the ball on the way up. It starts with a certain KE, then as it rises it loses some energy to friction and the rest is totally converted to GPE at the top when itis stationary. Now consider the path down. The ball now starts with less GPE than it had as KE at the start of its upward trajectory. It then loses more energy to friction again as it falls. Therefore when it reaches the same vertical position as it started it will have less KE, and hence be moving slower than it was on the way up. Hence every point on the way down corresponds to slower movement than the same point did on the way up – hence it takes longer to fall back to the ground.

• Arjan Kohli says:

Bonus Question:

I think the simplest way to approach this is by reasoning how forces are acting on the ball.

Drag forces will allways act opposite to the ball's motion, acting downwards while it moves up and upwards while it moves down. So, while the ball travels up there is more downward force than while the ball travels down. Therefore the time spent traveling up must be less than traveling down since the magnitude of acceleration will be less while it travels down.

• Philip Calcott says:

In the chair rotation problem one can look at it like this: If each cult member rotates 9 places they come within one place of returning to their origianl position. In doing so each cult member must have passed over the 4 annoited chairs belonging to the other cult members. So, for all five cult members in 9 chair-moves they must have passed over 4 x 5 = 20 annoited chairs. As 9 moves x 2 annoited chairs = 18, they must have on at least one occasion had a situation where at least 3 annoited chairs were occupied, as only occupying two annoited chairs per move would not add up to the required 20 in total – at least two "three annoited chair" positions must exist.

• JO'N says:

There are nine possible positions for the cultists to end up in. (Rotating by 10 positions gets them to where they started, a solution we'll ignore.) For each cultist, over those nine possible position the cultist must sit in each of the four other anointed chairs. Because there are five cultists, there are 20 total anointed position over the nine possible seating arrangements. Each seating a1, a2,…a9 has a certain number of anointed seats taken, with the constraint they all sum to 20.

a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 = 20

If we limit a1,…a9 to be at most 2, then the sum can't possibly be more than 18. To get the sum to be 20, at least one of a1,…a9 has to be 3 or more.

• Sedict says:

I tried to solve the first problem in a very simple manner.The explanation is a bit hard to follow (sorry for that), but overall the main idea is simple.

I think of it as they sit at either an odd(O for simplicity) or an even chair(E). At any point they may choose to move around the table in such way that the people sitting at an odd numbered chair will now be sitting at an even numbered one and vice verse .

Now if 5 or 4 of them are sitting at O or E chairs, it is obvious that a solution exists since they can just "switch" (so the O chairs become E instead).When only 3 of them are sitting at chair of the same group (say O)they will again choose to switch(so the biggest group O,becomes E). We can choose to move to a position when at least one old E square moves to a position not previously occupied by former O chairs, so we are gurranteed to have at least 2 free anointed chairs.But remember that the O chairs must also become E and since the old O chairs are 3 and the old E chairs are 2 we are also guranteed to have 1 more free anointed chair.

• Philip Calcott says:

• eJ says:

Yes, Philip, it is 🙂

• Anil Agarwal says:

Hi Philip and eJ – I came up with 35 beam bounces as well. But the method I used is not quite a short-cut, it looks more like brute-force, calculating the bounce angles and their relationships.

• Anil Agarwal says:

Of course there is a simple way to empirically verify the effect of drag on the upward and downward journey times of an object. Instead of a ball, use an air-filled balloon. Flick the balloon up with your fingers and watch it come down – ever so slowly. The upward and downward journey times are vastly different.

• Philip Calcott says:

Hi Anil, I think I probably used the same approach as you. I think the shortcut is along the lines indicated here:

http://puzzling.stackexchange.com/questions/15678/shooting-a-laser-between-two-mirrors

Once you get your head around the coordinate transformation it is obvious that one ray entering parallel to a mirror must cut all 35 mirror representations before "exiting".

Any thoughts eJ?

• Anil Agarwal says:

Hi Philip, eJ,
The solution in http://puzzling.stackexchange.com/questions/15678/shooting-a-laser-between-two-mirrors is more general and more complicated than the method I used. Since I assumed that the mirrors touch each other at the base, my method involved no trigonometry, only addition and division (of angles). It's equivalent to shrinking the inner circle in the diagram to a point and shooting the laser aimed at the center; then the answer is simply 180 / angle – 1.

• eJ says:

Philip,
> … puzzling.stackexchange.com/questions/15678 … thoughts eJ?

Well played, you've found the trick. I've always liked this little puzzle, as it was one of the few that I was able to solve in a "fun" quiz event put on by the university maths society years ago …!

• Chance Beaube says:

The random seating is easy. The five can all move one chair over and if the five seats they moved to do not have don't have at least three anointed seats then the five chairs directly opposite them will so they would move to those chairs in that case.

• Chance Beaube says:

Broc Seib , the spider & fly problem answer a path of length square root of 40, yes? That is a fun problem.

Update

Great explanations, and some excellent new problems, thank you. Continue to enjoy and comment on these!

Regarding the original problems, I have two updates.

The table problem:
I thought that a variant of the table problem with 11 chairs and 6 cult members would be interesting. This would give 30 anointed chairs visited in 10 possible rotations. I thought that it would be quite likely that there would not be any relative placement that would give exactly 3 anointed chairs in each of the 10 rotations. If that were to be the case (and if there were an easy way to prove it), then the minimum number of anointed chairs available would be 4 — quite a significant increase in anointedness with the addition of only one chair and one cult member. The cult would certainly have gone for that!

Unfortunately it turns out that there are not one, but two Cursed Configurations — two sets of relative positions that amazingly, give exactly 3 anointed chairs for each one of the 10 rotations! These configurations would be considered miraculous if the cult considered the balance of anointedness around the table to be a higher virtue that just having maximum anointedness in one particular position!

The ball problem:
Some of you have remarked on the fact that the air resistance acts with gravity on the way up but against gravity on the way down. Does this matter?
Here's a variant with this property reversed.

Someone drops a ball straight down from the top of a 100-floor skyscraper. You are looking out of the window on the 50th floor. You start timing the ball when it crosses your horizontal line of sight. The ball lands onto a mechanized trampoline placed on the ground. This contraption is guaranteed to impart to the ball the same upward velocity as the downward velocity with which the ball landed. The ball shoots up and crosses your line of sight again on the way up. Does the ball take longer to fall from the 50th floor to the trampoline or longer to rise from the trampoline to the 50th floor?

• Philip Calcott says:

Hi Chance, remember the spider has to crawl over the cardboard. This allows you to "unfold" the cardboard box and lay it flat without changing the problem. What had looked like a problem in 3D geometry now is shown to be a probelm in 2D geometry. There are two obvious routes the spider can take but the shortest has a nice integer solution.

• Richard says:

My favorite short circuit problem is to show that it is impossible to cover a chessboard (having 1" x 1" squares) that has had its opposite corners removed, using 31 dominos ( each 1" x 2" ). Very hard by brute force, exceptionally easy if you see the trick.

• Wiley says:

That's a nice observation for the table problem: the naive bound (*) floor[m(m-1)/(n-1)] is not necessarily tight (with n chairs and m cult members where m<=n). skimming through the answers, Morris Ang is the only one giving a configuration to prove the bound 3 is tight for m=5, n=10.

I experimented a bit with pairs that m(m-1) is divisible by (n-1) – the bound should be easier to achieve in other cases. looks like the smallest m that (*) is not tight is m=6 and n=16, i.e., one should be able to prove that with 6 members and 16 chairs, they can always reuse at least three of the anointed chairs.

also it looks like for a class of (m, n), we could use the triangular numbers T(0), …, T(m-1) modulo n to construct the positions that (*) would be tight.

(I see few people had invoked probabilistic method for the original problem. this seems to be a quite nice follow-up problem to work out collectively)

• PMK says:

http://www.amazon.com/Mind-Trap-Game/dp/B00000DMBU/ref=sr_1_3?ie=UTF8&qid=1463540475&sr=8-3&keywords=mindtrap

• Wiley says:

(spoilers below)

After experimenting a bit more with smaller values, I found that these configurations are so-called "difference sets" of cyclic groups (the set of integers modulo n, or Z/n). they have very rich structures, e.g, the configuration of 3 members with 7 chairs that only 1 anointed chair can be reused is equivalent to the Fano plane. See
https://en.wikipedia.org/wiki/Difference_set
http://www.ccrwest.org/diffsets.html
and references therein.

• Morten Thorbjørn Svendsen says:

The ball problem.

It will will fall with the same velocity it rose.

Its a translation of energi:
(initian velocity – (gravity + drag) = height (gravity) = end velocity (gravity) – drag

• Chance Beaube says:

yes, Philip Calcott I now see the spider in the box solution … unfolding the box makes it pop out a very nice answer indeed, thanks for the tip!

• Raymond Rogers says:

My favorite "shortcut" is" : Prove that the number of people who has shaken an odd number of hands is even. An oldie but goody.

• David Thornton says:

Try this one. I remove the core of a spherical apple so that the height of the cored apple is two inches – what is the volume of the cored apple?

• Carl Granstrom says:

@Raymond Rogers

You need two ppl to do a handshake, hence the number of people that has shaken hands is always even.

The other info is just there to mislead.

• Carl Granstrom says:

"Chance Beaube says:
May 15, 2016 at 7:12 pm

The random seating is easy. The five can all move one chair over and if the five seats they moved to do not have don't have at least three anointed seats then the five chairs directly opposite them will so they would move to those chairs in that case".

This looks like the short-circuit solution to me. All other solutions required too much calculation, thinking and tinkering.

• Greg Egan says:

Chance Beaube wrote:

"The random seating is easy. The five can all move one chair over and if the five seats they moved to [don't have] at least three anointed seats then the five chairs directly opposite them will so they would move to those chairs in that case."

Perhaps I've misunderstood this argument, but it seems to be saying that a shift of either 1 or 6 (the latter giving you the chairs if you first move by 1, and then move to the chairs opposite) must always give at least three anointed chairs.

I don't see why that should be true. And if I've interpreted the claim correctly, it's easy to find counterexamples. If the initial seating that determines the anointed chairs is (A for anointed, e for empty)

AAAeeAeAee

then moves of 1 and 6 give the following two seatings:

eSSSeeSeSe
eSeSeeSSSe

in which there are only two people in anointed chairs (positions 2 and 3 in the first case, positions 2 and 8 in the second case.) In fact, the unique move that gives at least three people in anointed chairs is a move of 5 (which puts four people in anointed chairs).

• Nelson Thompson says:

Here is a problem that actually happened to me.
I was in the fifth grade and the teacher wanted to keep us busy while she graded some papers. She told us to take out one sheet of paper and add up all the numbers from 1 to 100.
This surprised the teacher. But what really spun her noggin was that I had written down the correct answer!

The ball loses kinetic energy to turbulence. So it must surely go up faster than it comes down.

Heh. Suppose they move a random number of spaces. The average number of reused seats must be 2.5. There is clearly a position where 5 seats are reused (where they started). Suppose every other position has only 2 (or less) reused seats. Average is at most {5+(2*9)}/10 = 2.3, which is too small. Therefore there must be a position with at least 3 reused seats.

@Wiley,

This is probably related to "difference sets of cyclic groups."

The two configurations that I mentioned that enforce the tight bound of 3 for 11 chairs and 6 members are: 1,2,3,5,6,8 and 1,2,3,7,9,10 assuming the first member is in chair 1.

The differences between the chair positions for these two configurations are 1,1,2,1,2,4 and 1,1,4,2,1,2. These "power of 2" differences seem to enable these configurations to have exactly 3 anointed chairs no matter how many places the members rotate.

• Chance Beaube says:

@Greg you are indeed correct. Hmm, I jumped in way too fast on the problem.

Now I am trying to figure out what the 'shortcut' to the solution is….

• Chance Beaube says:

@Adam Wasenczuk I think you have the easy solution figured out.

If the people rotate repeatedly until they get back to their starting chairs then each original seat is occupied five times for a total of 25 in seat occurrences. But, if only the original arrangement has 3 or more anointed chairs then 5*1 + 2*9 = 23 would be the maximum number of in-seat occurrences. That contradicts that we know the total is 25.

• Anmol says:

1st one I'm assuming they can't move 10 and all be in the same place. If not there are 10 possible clockwise orientations, in which there are 25 people totally in anoninted chairs (people are in anointed chairs half the time). We have seen 1 where 5 are in anointed chairs which leaves 20 chairs in 9 orientations. If at most 2 chairs were used every time, that would use at most 18 chairs. Therefore by the pigeonhole principle at least 3 anointed chairs must be used once.

For the second problem due to air resistance the ball is travelling slower when it hits the ground than it was when it was thrown. Since both cover the same distance, the ball coming down takes longer.

• Ryan Condon says:

Because there can be a maximum of one space between "anointed" chairs, as soon as everybody at the table moves 1 chair, they are either in an anointed chair, or will be in one when they move 1 more. If there are 3 or more people in an anointed chair already, then we are fine. And if there are not, moving one more chair is guaranteed to work.

(Haven't tried to rigorously solve the second one but here's my guess): Air resistance can't make the ball move slower than it would if it was moving slower, if that makes any sense. So the answer is the same.