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?
Heard from a fellow Googler in 2009.
A wizard should keep quiet if he sees one black and one white hat. If he sees two black hats, he should announce white. If he sees two white hats, he should announce black. With this strategy, the probability of winning the game is 3/4. Why? The game is lost only when all hats are white or all hats are black. These events occur with probability 1/8 each.
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?