The 100 prisoner riddle - counterintuitive puzzle

[EllisDee]

@Little_Nemo

First, he would arrange the papers so there is a loop of at least fifty-one boxes. This would would foil the standard strategy.

Then he would place one of the remaining papers inside the box that has the same number. This guarantees that the +5 strategy or any other strategy that depends on displaced numbers will fail.

Well let’s try it with six numbers doing +1. By your rules, the warden sets it up as:

1 => 2
2 => 3
3 => 4
4 => 1
5 => 5
6 => 6

Prisoner 6 checks box 1, which sends him to box 3, then 5, then 6.

Prisoner 5 checks 6, 1, 3, 5.

Let’s try +2:

Prisoner 6 checks 2, 5, 1, 4, 3, 6

Prisoner 5 checks 1, 4, 3, 6, 2, 5

Still guaranteed to be in the same loop every time regardless. You aren’t guaranteed the prisoners will win, of course. That’s a ~31% chance. But you have reshuffled the loops to hopefully getting a favorable ‘roll’.

It’s not lost on me that the examples using your warden strategy did result in the prisoners losing because they had to open more than three boxes. Are you saying it’s still always closed loops, but you can guarantee the loops will be too long?

[Little_Nemo]

@Dr.Winston_OBoogie

Sure it is If you’re number 23, you’re not picking 28 then picking whatever is in 28, you’re picking 28 then whatever is in 28 + 5; then whatever is in that + 5 etc. Logically, you have to have a loop there. Somewhere. And, it doesn’t have to be the same loop or even the same count. I played around, trust me, it works.

Okay, I just did some playing with it and I see it now.

[EllisDee]

@EllisDee

1 => 2
2 => 3
3 => 4
4 => 1
5 => 5
6 => 6

Wait a minute, what’s going on if we do the +1 strategy with prisoner 2?

Prisoner 2 starts with box 3, which sends him to box 5, then 6, 1, 3, but now we’re in a loop and we never get back to box 2.

What am I doing wrong? I can never seem to get back to box 2, and probably same deal with box 4.

[Railer13]

@3AxisCtrl

I think there could be. One example: Boxes 1 through 98 contain their own number. Box 99 contains 100; box 100 contains 99.

Duh. Yes of course, there could be 99 loops. My bad.

[naita]

@EllisDee

Wait a minute, what’s going on if we do the +1 strategy with prisoner 2?

Prisoner 2 starts with box 3, which sends him to box 5, then 6, 1, 3, but now we’re in a loop and we never get back to box 2.

What am I doing wrong? I can never seem to get back to box 2, and probably same deal with box 4.

Let’s simplify by updating the numbers and rearranging the boxes in the loops that are created

So we started with three loops
1 => 2 2 => 3 3 => 4 4 => 1
5 => 5
6 => 6

With the plus 1 strategy we have the updated numbers
1 => 3
2 => 4
3 => 5
4 => 2
5 => 6
6 => 1

And the loops
1 => 3 3 => 5 5 => 6 6 => 1
2 => 4 4 => 2

Prisoner two starts with box three, and eventually gets to box 1, which has the paper with 2 on it. The loop is too long in this case of course, but you still have 2/3 of a chance of death even with this counter strategy.

[EllisDee]

Oh, duh. Box 2 is irrelevant, only paper 2 is, and that is indeed in box 1. Makes sense, thanks much.

I got confused because my examples a couple posts up had the starting papers in the same number boxes. Focusing on the boxes instead of the papers in those cases didn’t matter.

[naita]

Looks to me like +5 is the only choice that works out for the prisoners. I don’t know if that’s a result of the low number of boxes though. I’m at the beach and my simulation code is on a different machine.

+2
1 => 4 4 => 3 3 => 6 6 => 2 2 => 5 5 => 1

+3
1 => 5 5 => 2 2 => 6 6 => 3 3 => 1
4 => 4

+4
1 => 6 6 => 4 4 => 5 5 => 3 3 => 2 2 => 1

+5
1 => 1
2 => 2
3 => 3
4 => 6 6 => 5 5 => 4

[Chronos]

@hajario

Here is the History section of the Wiki article about the puzzle. Do you have reason to dispute it?

That looks to me like someone first posed a related problem, and posited that it had no technique that wasn’t abysmally bad, and that someone else then came up with a slight variant of the problem (this one) for which there is a decent strategy, and found that strategy. But this strategy still doesn’t work for the problem as originally posed.

[CardboardBoxx]

I made a post earlier, which I now believe to be incorrect. It seems to me though that what you’re looking for if you’re prisoner 23 is the slip of paper that has 23 on it. In order to ensure that you’re in the same loop as that slip pf paper you start at the box that that paper would send you to. So if we agree on a +5 strategy, I start at box 28. I know I’m now in the same loop as the paper that says 23. and I am also creating different loops to mess with the warden.