I hope you had a chance to play the clock solitaire game that was listed yesterday. When we were kids we laid out six cards face down in one horizontal row, then six cards in a row below that one, and a single card to the right of the two rows. The top row was labeled (in our head) Ace through Six; the bottom row was labeled Seven through King, but we skipped over the Jack. The card on the right was the Jack. We then dealt out all the cards evenly into the thirteen stacks, so each stack had four cards in it. You start the game by picking up the top card in the Jack pile. Whatever card it was, you slid it face up under that stack. So if you picked up a Five, you slid that Five under the Five stack and then picked up the top card in that stack. If that card was a Ten, you slid it face up under the Ten pile and took the top card. You kept doing that until you ran out of cards to turn over. Your goal was to get all the cards in the stacks turned over before the last Jack came up. When the last Jack came up, there were no more cards in the Jack pile to work with (since you started with that pile) so the game was over. There is roughly a 1% chance of winning so it was a huge victory when you did win.
That is similar to the strategy for the 100 Prisoners Problem. Each contestant walks to the box that corresponds to their number. Contestant 1 walks to the first box, opens it, then moves to the box whose number is on the dollar bill in the first box. So if the first box has a 67 on the dollar bill, you would go to Box 67 next. If that box has a dollar bill numbered 43 in it, you would then go to Box 43. You keep repeating this until the box you open has your number - in this case number 1. So now you know which box has dollar bill number 1 in it and you can leave. Contestant 2 walks to Box 2 and checks the number. Then he moves to the Box with that number and so on until he either finds the box with 2 in it or hits his 50 box limit. Contestant 3 starts with Box 3 and so forth.
Let's look at a much simpler version that has only 8 boxes and 8 contestants. The box numbers and dollar bill numbers are listed below. Assume that the limit on boxes you are allowed to open is 4 = half of 8, just like 50 = half of 100.
Box number 1 2 3 4 5 6 7 8
Number on dollar bill 4 7 5 2 6 3 1 8
inside
Where did those numbers come from? I made them up just as the designer of the puzzle would do when they put the dollar bills in the boxes.
Contestant 1 finds a 4 in Box 1 so they go to Box 4, then to Box 2, then to Box 7 and there they find the dollar bill numbered 1 and they leave. They opened 4 boxes, so the game is still going on. Contestant 2 starts at Box 2, then Box 7, Box 1, and finishes at Box 4 (where he finds his number 2 dollar bill). Contestant 3 starts at Box 3, then to Box 5, then Box 6 and they are finished. What we have are cycles of numbers:
(1, 4, 2, 7) is a cycle. If you start at one of these numbers, like 2, you will cycle through the other numbers in the group: 2 goes to 7 then to 1, then to 4. (3, 5, 6) is also a cycle and (8) is a cycle by itself. Because each cycle is 4 or smaller, each contestant will find their number successfully and everyone gets the prize money.
Here's another allotment of dollar bills.
Box number 1 2 3 4 5 6 7 8
Number on dollar bill 2 3 4 5 6 1 8 7
inside
Here the cycles are (1, 2, 3, 4, 5, 6) and (7, 8) and the contestants would lose because the first cycle is longer than 4 numbers.
With the 100 box problem, the contestants would win if the longest cycle of numbers is 50 numbers or less. There can't be more than one of those because there are only 100 numbers to divvy up into cycles. So there could be a 20 number cycle, a 30 number cycle, and a 50 number cycle and that would use up all the numbers (and you would win). The probability calculations (found here, if you would like to follow along) tell us that the longest cycle of numbers is 50 or less about 31% of the time. That is a huge jump from the random strategy probability of winning which was 0.0000000000000000000000000000008.
No comments:
Post a Comment