XRDS

Crossroads The ACM Magazine for Students

Sign In

Association for Computing Machinery

The Anarchist and Airplane Problem (FALL 2017)

Puzzle:

One hundred people line up to board a plane with 100 seats. The first person in line has lost her boarding pass, so she randomly chooses a seat.

After that, each person entering the plane either sits in his or her assigned seat, if it is available, or, if not, randomly chooses an unoccupied seat.

When the 100th passenger finally enters the plane, what is the probability that he finds his assigned seat unoccupied?
 

Solution:

The probability, somewhat surprisingly, is 1/2! There are two ways to see this: the long way and and the short way.

Here is perhaps the shortest solution that is still fairly complete.

The key observation is this: When the last person boards, the only possibilities for empty seats are the correct seat or the seat assigned to the first person. Why? Well, if the seat assigned to the 16th person to board is free when the last person boards, then it was also free when the 16th person boarded, so person no. 16 would have taken it then. What we have is a contradiction; and this same contradiction works for everyone else after the first person to board.

A corollary of this observation is whenever a passenger makes a random choice, both the first person's and last person's seat must be available. For if, after one of these seats is taken, a passenger comes on and finds that she or he has to make a random selection between many seats, there is a non-zero probability that she or he takes the other of these two special seats, contradicting the key observation. (The last passenger is forced to sit somewhere other than their own seat or the first person's seat, a situation we now know to be untenable).

Armed with this key observation, we see the event of the last person's correct seat being free, is exactly the same as the event of the first person's seat being taken before the last person's seat. What could be the probability of that?

Well, each person who came on the plane and had to make a random choice, was equally likely to choose the first person's seat or the last person's seat—the random chooser exhibits absolutely no preference toward a particular seat. This means the probability that one seat is taken before the other must be 1/2.

Another way to think of this: If you tried to write down two exact expressions, one (A) for the probability that the first person's seat is taken before the last person's seat, and one (B) for the probability that the last person's seat is taken before the first person's seat, these two expressions would have to be identical. Since every time a random choice is made, the probability of the first person's seat being chosen is equal to the probability of the last person's seat being chosen.

Since A=B, and this covers all possibilities (by the key observation), they must both be equal to 1/2.

(SOURCE: Dr. David Galvin, "Probability Puzzler 3 - The TSA wouldn't like this")

 

City of Lies or Truth (SPRING 2017)

Puzzle:

You are at an unmarked intersection . One way is the City of Lies and another way is the City of Truth. Citizens of the City of Lies always lie. Citizens of the City of Truth always tell the truth. A citizen of one of those cities (you don't know which) is at the intersection. What question could you ask to that citizen to find the way to the City of Truth?

Solution:

You ask "In which of those two directions do you live?". A citizen of the City of Lies will point to the City of Truth and a citizen of the City of Truth will point to the City of Truth.

(SOURCE: Math Is Fun)


Four-Sided Dice (SUMMER 2017)

Puzzle:

I have three special four-sided dice. They have one letter on each side. When I roll them together I get three random letters that I then try to rearrange into a word. After my eighth roll, I have made the words: CAT, SON, POD, RIG, PEG, TAP, DIN, APE. What are the letters on each die?

Solution:

The letters on the three dice are: CNPR AGDS EIOT

(SOURCE: Math Is Fun)