I saw this yesterday. I'm not that much into puzzles, but this is amazing:
The names of 100 prisoners are placed in 100 wooden boxes, one name to a box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room. They may look into up to 50 of the boxes to try to find their own name, but must leave the room exactly as it was.The prisoners are permitted no further communication after leaving the room. They do have a chance to plot a strategy in advance. Good thing. Unless they all find their own names, they will all be executed.
If each prisoner examines 50 boxes at random, the probability of the group's survival is a miniscule (1/2)^100, or about 0.00000000000000000000000000000008. Even worse, if they all happen to look into the same 50 boxes, their chances drop to zero.
The 'winning strategy' improves the odds to almost 1/3, which is about 30 orders of magnitude better. And its stunningly obvious ... in retrospect. [Actually, I had to mull over the answer for quite a while to figure out why it worked, so I guess that's not true.] More puzzles (and solutions) here.
Hat Tip to Geekpress.
*spoilers follow*
The prisoners are creating a name -> box # "protocol", like this:
John Doe -> Box 1
Jack Ruby -> Box 2
Jane Eyre -> Box 3
etc.
So John walks in, picks Box 1. Inside Box 1 is Jack's name. Jack maps to Box 2, so he opens Box 2, and so on.
Now, it's possible that by following this process, John will just chain through 50 boxes. However, when you create a protocol like this, it's far more likely that you will create loops:
Jack's box has John's name in it -- John = Box 2.
John's box has Jane's name in it -- Jane = Box 3.
Jane's box has Jack's name in it -- Jack = Box 1.
Because of the way the protocol is set up, if you find yourself in a loop, the loop HAS to include your name. (That's the only name that leads back to your starting box.)
If the protocol happens to contain no loops larger then 50, then you will always find your name -- starting with your own name assures that you are on the right loop, so if it's smaller than the number of choices you will always work your way through it.
Then they do sneaky math stuff to show that the chances of such a protocol having no loops too large is around 30%. Presto!
I'm still trying to figure out the solution to one of the other ones in the paper, the one about the people with blue and red dots on their heads. The solution uses induction, but I just don't see it. Suppose there are 100 people in town, 47 with red dots and 53 with blue dots (so it's a Democratic town). A stranger wanders in and says, "The number of blue dots isn't 3". How can anybody use that fact to kill themselves? I mean, everyone in town knew the number of blue dots wasn't three before this joker showed up--the number has to be 52, 53, or 54.
For those who are confused, the puzzle is ... everyone has a red or blue dot on their forehead (and no mirrors). If anyone every knows their own dot, they commit suicide. How much information is requried to make the town (eventually) kill itself, and the answer is "anything non-trivial."
Spoilers
Imagine the stranger says "The number of blue dots isn't three" and the number of blue dots *was* four. Then those who weren't sure it was three or four would know (and commit suicide). After one day if they didnt' kill themselves, you could rule out four blue dots.
By this process, you eventually rule out 50, then 51. Then comes the point where you rule out 52. Now, everyone with a blue dot can see 52 blue dots, so they know "they" have a blue dot, kill themselves, which leaves the red-dotters alive, so they kill themselves.
It's not a satisfying puzzle. The basic idea is that everyone "knew" it was one of two values, but the inductive process can march along through things that could be deduced ... and then it keeps going through things that could not be deduced. I'm not sure why the deductive process doesn't trigger the inductive process. What if one of the dotters said "There aren't three blue dots?" Would that trigger an eventual suicide? How is this knowledge different?
So I guess we're in the same place.
(slightly edited for clarity)
If k > n what value does (n-k)! have? Is it a misprint?
"To see this, let k > n and count the permutations having a cycle C of length exactly k. There are P(2n,k) ways to pick the entries in C, (k-1)! ways to order them, and (2n-k)! ways to permute the rest; the product of these numbers is (2n)!/k. Since at most one k-cycle can exist in a given permutation, the probability that there is one is exactly 1/k."