Solution: ‘A Random Place at the Table’

This month’s puzzle focused on problems that at first glance seem to require long, complicated calculations but turn out to have simple and satisfying “shortcut” solutions. Quanta readers responded enthusiastically: Besides solving our two featured problems, they shared their own interesting problems, resulting in a fruitful and interactive comments section.

Our first problem was as follows:

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.

No, we don’t have to try out all 252 possible random positions that the cultists could have been seated in. Here’s the shortcut solution, paraphrased from our first commenter, Jake Soloff:

We want to show that the five clubhouse members can always find a way to shift to the right some number of chairs so that at least three of them are still sitting in anointed chairs. Since there are 10 chairs, there are nine 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).

For any given anointed chair, the four members who do not start out in that chair can each shift into that position on some particular rotation. Since there are five anointed chairs, there will be 5 x 4 = 20 times that an anointed chair will be occupied if all the nine shifts are carried out. Because 20/9 is bigger than 2, at least one of the possible shifts must have used more than two anointed chairs!

In fact, we can say a little more, since the remainder of 20/9 is 2. This implies that for any starting position, there will always be either (a) at least two shifted positions that reuse three anointed chairs, or (b) at least one shifted position that uses four chairs. As Zak and other commenters pointed out, this is a straightforward application of the aptly named “pigeonhole principle,” a simple form of which says that “if (N+1) pigeons occupy N holes, then some hole must have at least two pigeons.”

Our second problem went as follows:

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!

In the presence of drag, the ball takes longer to fall than it does to rise. Here’s the explanation from Greg Egan:

Since the ball loses energy to air resistance, it must return to its initial height traveling 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 traveling more slowly during its descent, and the total time for the descent must be longer than the total time for the ascent.

Some readers, such as Ian, offered another way to think about this:

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.

This latter method is correct too, but you must not infer from this that the falling ball will take longer if the falling phase precedes the rising phase, as in the following variant that I offered:

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 on 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?

Here the rise takes longer than the fall. As the energy explanation clearly shows, the continuous loss of energy of the ball to drag means that after the initial trip, whether rise or fall, every subsequent trip that the ball makes over the same height will take longer and longer. In the above example, the rise on the ball’s second trip will take longer than the initial fall, and when the ball falls down again on its third trip, it will take even longer.

An interesting way to think about this problem is to consider the extreme case: Imagine that the ball had already reached its terminal velocity when it initially came into your view. Terminal velocity is the highest velocity attainable by an object as it falls through air: No falling object can keep accelerating forever. At a certain velocity, the frictional forces such as drag and buoyancy equal the downward force of gravity and the object cannot go any faster. The terminal velocity for a baseball or cricket ball is about 75 miles/hr or 33 m/s — this is the constant speed at which the ball will reach the trampoline. On the way up, this will be the ball’s initial velocity, but this velocity will have nowhere to go but down, thanks to gravity! So it will take longer on the way up. (In fact, if the ball had reached terminal velocity when it was halfway down the building, it would not be able to bounce high enough to reach halfway up the building even off a perfect trampoline. I’ll leave it to you to figure out why.)

There are plenty of other fascinating explorations that both these problems offer. Anil Agarwal gave the following generalization for the table problem with 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)).” This is correct but by no means the whole story. With 10 chairs and five members, for instance, we showed that at least three anointed chairs can be reused. But the “at least” leaves open the question of whether the answer is three, or a higher number such as four. Is three chairs, in this case, what is called a “tight bound”? To prove this we have to find at least one case where the maximum number of reused chairs is exactly three. This was shown by Morris Ang, who gave the following example:  “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.” Wiley showed that anointed chair configurations in this problem can lead to some very deep mathematics.

As I mentioned earlier, readers presented some great shortcut problems of their own. The V-shaped mirror problem, shared by eJ, found some enthusiastic takers, as did Broc Seib’s spider-and-fly problem. Both of these problems have very nice shortcut solutions. Thank you for the other problems as well; we may present them or some variation of them in future Insights columns.

The Quanta T-shirt for this month goes to Greg Egan, who provided nice solutions to both problems and also showed that some other proposed solutions to the table problem didn’t work. Greg also offered some excellent explanations in our very first Quanta Insights puzzle. Congratulations, Greg, glad to see you again!