Friday Puzzler -- The next 100 Prisoners

Re: Friday Puzzler -- Observation

Larry Barrett

If the overall odds of success have increased from near zero to 30%, and if the individual odds of success remain equal, then the individual odds are near certainty: .99^100 approx = .3.

It seems unlikely that the individual odds are that high and all equal. Therefore, it is likely that they vary in some way. Perhaps if/when a prisoner finds his number he swaps that drawer for the drawer in his numerical place in the cabinet. For example, suppose prisoner 3 finds number 3 in drawer 35. He swaps drawer 35 with drawer 3 in the cabinet. Then the next prisoner avoids opening all drawers that are out of place, increasing his odds of finding his numbers. I have not tried to see how this might improve the overall odds.

The 30%

Alex Y

Thinking about Larry's post, I realize that I misstated something in my footnote. While it is true that the chance of success varies from 0% to 100%, it is better to say the chance of success will be 0% OR 100% depending on the distribution of the chips.

And no, each prisoner must leave the chips and drawers exactly as they found them.

Just for the record

Kent B

It is inconceivable that I will attempt to swim in the math-focused puzzler pool with a coupla actuaries.

Just sayin'

I do enjoy following the dissection and solution, however

Carry on, men.

LOL!

Alex Y

Nothing actuarial, probability-related, or otherwise mathematical about either of this week's puzzles.

Dive in, sir; the waters are safe.

Re: LOL!

Kent B

In the way-way-WAAAAAAAY back, I was a long-haired, dope-smoking, beer-drinking, war-protesting, frat-rousing hippie. In engine school. I did accrue a mountain of calculus credits, by some remarkable accident. I even have my Post slip-stick around here sumwhurrs. However, decades are decades - no way around that statistical fact..

Y'all carry on as needed. I'll jump in when I won't embarrass you nor I.

I forgot about trivia again until yesterday

david weaver

Please don't release the solution to this yet, just setting up a sheet to run some ideas today at lunch and I'm also a slow problem solver!!

Re: Friday Puzzler -- The next 100 Prisoners

Larry Barrett

I tried my interpretation of the C K G problem with 4 prisoners, 4 drawers, and the numbers 1-4 randomly placed in the drawers. Each prisoner first opens the drawer corresponding to his number; if it contains his number he is done. If not, he gets one more chance, and as in the C K G problem he next goes to the drawer with the number corresponding to the number in the first drawers he opened.

There are 4! = 24 ways to arrange the numbers 1-4 in the drawers.

The results for this 4 prisoner, 2 attempts problem are as follows:

10 times all 4 found their number in 2 or less times. Of the 14 failures, 5 times none found their correct number, 8 times 1 found their correct number and 1 time 2 found their correct number.

This was done one the back of a napkin so might be errors, but it looks promising.

Re:Drawing a blank

david weaver

I'm drawing a blank on this one trying to figure out how to use the information in the "draw" in the drawers to let a subsequent prisoner know what a previous prisoner would have found by the virtue of the subsequent prisoner being invited to the room in the first place.

Re: Friday Puzzler -- The next 100 Prisoners

Alex Y

You are getting there!

In your 4 drawer 2 try version, your one case where two succeeded and two failed is impossible. And you are short one on the four failed count.

Re: Friday Puzzler -- The next 100 Prisoners

david weaver

Do the prisoners need to go in sequence, or more specifically, is the jailer the only one who can choose the order that they go into the room?

Re: Friday Puzzler -- The next 100 Prisoners

Alex Y

Prisoners can go in any order, and may or may not open all of their 50 boxes in one visit to the room (although looking into the possibility of going in multiple selection sessions will just send you down a rabbit hole )

(elmer fudd voice)

david weaver

Is there a wabbit at the bottom of the hole?

(I'm guessing no). Long on work today and tomorrow and short on time, but hate to give up on a problem!

Solution--Closed Loops *LINK*

Alex Y

Let's look at Larry's simplification of the problem (an excellent puzzle-solving tool) to four prisoners with two chances each to find their number. As Larry said, there are 24 permutations of numbers in boxes. Here are five different arrangements of numbers, with a count of how many of the 24 permutations are represented by each example, in a way that will be made clear.

1234 (1)

1243 (6)

2143 (3)

1342 (8)

2341 (6)

Above, each number is related to its container by its position. Each of these permutations can be represented by four ordered pairs, where the first number is the container and the second is the content. For example the third permutation is

(1,2) (2,1) (3,4) (4,3)

The first ordered pair "points to" the second ordered pair, which points back to the first, forming a closed loop. Similarly, the third ordered pair points to the fourth, which points back to the third. So, with two closed loops of length 2, whatever number you are looking for, you will find in the second container you open.

Compare that to the fourth permutation,

(1,1) (2,3) (3,4) (4,2)

In this case we have one "loop" of length 1 and one of length three. If you are looking for a 1, you will find it. But if you are looking for any other number, you will find it only in the third container you open, so will fail.

If there is a loop longer than 2, at least some of the prisoners will not find their number within two tries. This occurs for the 14 permutations represented by the 4th and 5th examples above. In the first 3 permutations above (and the permutations they represent), all closed loops are of length 2 or 1, so anyone following the strategy of picking the container labelled with their own number and then going to the container it points to will find their number.

Application to 100-Prisoner Puzzle

If you choose the container labeled with your number, you have chosen a closed loop with the box containing your number. As long as the closed loop is 50 or shorter, you will find your number. As long as ALL the closed loops in the distribution are of length 50 or shorter, the prisoners will go free. Approximately 30% of the permutations of 100 objects consist only of loops shorter than 51. (I don't know how this was calculated--brute force or a more elegant determination.)

Want to understand more?


Here is a Wiki article

Re: Solution--Closed Loops

Alex Y

I said that I didn't know how the 30% was calculated, but the cited wiki article explains it (and it is closer to 31%.

Also interesting is the "one prisoner is allowed to swap two boxes" paragraph in that article.

Re: Solution--Closed Loops

Larry Barrett

This was an interesting problem but I was not making any headway on the solution. I'm glad you posted the answer and the link. It would take some very clever prisoners to make the closed loops.