Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Absent-Minded Professor

Puzzle

N women stand in a queue to take seats in an auditorium. Seating is pre-assigned. However, the first woman is an absent-minded professor who chooses any of the N seats at random. Subsequent women in the queue behave as follows: if the seat assigned to her is available, she takes it. Otherwise, she chooses an unoccupied seat at random. What are the chances that the last woman in the queue shall get the seat assigned to her?

Source

From some compendium of Math competition problems.

Solution

The chances are one in two. Proof by induction. The base case, N = 2, is immediate. In general, the absent-minded professor might choose her assigned seat with probability 1/N, in which case the last woman surely gets her assigned seat. The absent-minded professor might choose the last woman's seat with probability 1/N, in which case the last woman definitely loses her seat. In each of the remaining N-2 cases, by induction, the chances of the last woman getting her assigned seat are one in two. Combining these cases, we see that the overall probability is .

Previous Puzzle: Three Boxes and a Ruby

Alice places three identical boxes on a table. She has concealed a precious ruby in one of them. The other two boxes are empty. Bob is allowed to pick one of the boxes. Among the two boxes remaining on the table, at least one is empty. Alice must then remove one empty box from the table. Finally, Bob is allowed to open either the box he picked, or the box lying on the table. If he opens the box with the ruby, he gets a kiss from Alice (which he values more than the ruby, of course). What should Bob do?

Three wizards are seated at a circular room. A magician shall make hats appear on their heads, one hat per wizard. Hats are either black or white, chosen uniformly at random. A wizard cannot see his own hat. At the sound of a bell, all wizards react simultaneously. A wizard reacts by either announcing a color or keeping quiet. If at least one wizard makes an announcement and if all the announcements are correct, the wizards have collectively won the game! Wizards are allowed to confer beforehand to devise a strategy. On average, can they win more than half the times the game is played?

14 Sep 2008
© Copyright 2008—2017, Gurmeet Manku.