August's Puzzle: Prisoners and Switches
A prison warden meets with 23 new prisoners when they arrive. He tells them,
"You may meet today and plan your strategy for the challenge I'm about to propose.
But after today, you'll be in isolated cells and will have no communication
with one another. In the prison is a switch room, which contains two switches
labeled A and B, each of which can be in either the On or Off position. The
switches aren't connected to anything. I'm not telling you the switches' present
positions. After today, from time to time, whenever I feel so inclined, I'll
select one prisoner at random and escort him to the switch room. This prisoner
will select one of the two switches and reverse its position. He must move only
one of the switches: He can't move both switches, and he can't move neither
switch. Then, I'll lead the prisoner back to his cell. No one else will enter
the switch room until I lead the next prisoner there, and I'll instruct him
to do the same thing. I'm going to choose prisoners at random. I might choose
the same prisoner three times in a row, or I might jump around and come back.
However, given enough time, everyone will eventually visit the switch room as
many times as everyone else. At any time, if you're 100 percent certain, any
one of you can declare to me, ‘We have now all visited the switch room.'
If that person is correct, I'll set you all free. If that person is wrong, and
somebody hasn't yet visited the switch room, I'll feed you all to the alligators."
What strategy can the prisoners use to obtain freedom?
The solution is to put one prisoner in charge of counting and notifying the
warden when the count is complete. That prisoner should follow these instructions:
- Toggle switch A.
- If you toggled switch A from the On state to the Off state, and you weren't
the one who turned it on in your previous visit, increment the count of prisoners
who visited the room.
The prisoners who aren't in charge of counting should follow these instructions:
- If switch A is toggled to Off, and you haven't previously switched it to
On, and you have previously seen it On, turn switch A to the On state.
- In any other case, toggle switch B.
The logic is that only the prisoner in charge of counting can turn switch A
off. A prisoner who isn't in charge of counting will toggle switch A from the
Off state to the On state only after seeing it on previously—and only
once. This means two things: First, when a prisoner who isn't in charge turns
switch A on, he knows that the prisoner in charge visited the room before him,
and after that visit, no other prisoner who isn't in charge turned switch A
on. Second, when the prisoner in charge turns switch A off and that prisoner
wasn't the one who turned it on in his previous visit, he knows for sure that
a new member that wasn't included in the count previously visited the room.
September's Puzzle: Probabilities in China
Is it possible to prove statistically that there must be at least two people
in China who have the same number of hairs on their heads? Try to stick to pure
probability and not to assumptions such as, "There must be many bald people
in China." Also, is it possible to prove statistically that there must be at
least two people in China with the same arrangement of teeth (i.e., missing
or existing in the same positions)? Again, try to stick to pure probability
and not to assumptions such as, "There must be many old people with no teeth,
or people with no missing teeth." (I got these two nice puzzles from my friend,
SQL Server MVP Marcello Poletti.)