Let's discuss Mathematics

[dutchfire]

The prisoners can't communicate with each other I guess?

No they can't.

I suspect first move is for prisoner x to open box x

Sounds good.

In the n=4 case, the chance of success is 10/24.

 

[Mise]

If prisoner x opens box x to find prisoner i's name, where i<x, then prisoner x knows that prisoner i already opened that box. So whatever the algorithm is, it must be respondent to that somehow... EDIT: Wait no that doesn't help...

 

[ParadigmShifter]

Is it to do with powers of x modulo the number of boxes?

 

[ParadigmShifter]

Ah good call Mise, do the prisoners know the names and numberings of the other prisoners?

 

[dutchfire]

The various prisoners could, in principle, open their boxes at the same time.

If you start with prisoner 1, you want to maximise the chance of prisoner 2 succeeding, provided prisoner 1 succeeds etc.

 

[dutchfire]

Ah good call Mise, do the prisoners know the names and numberings of the other prisoners?

Yes.
You could also just take the situation as: every prisoner has a number 1-100, in each box there's a number 1-100.

 

[ParadigmShifter]

Right, so if prisoner x opens box x first go, it has to be something to do with opening the box that has the name/number they just looked at next, and so on. Is that the answer?

EDIT: If it isn't, it has to be some kind of formula for maximising the (wrap around) distance between boxes based on the number they just saw, and numbers they have left.

 

[dutchfire]

Yes

Prisoner n starts by opening box n. Once someone has opened a box containing name i, he opens box i next.

Given a bijection of N=100 (a way of putting the names in the boxes), this process is successful if the longest cycle in the bijection has a length l =< N/2.

 

[ParadigmShifter]

Where's the faffing proof then?

EDIT: Can that strategy be defeated by a wily prison guard though? Or are you assuming the box/name distribution is random?

 

[Mise]

How the crap does that work?!

 

[dutchfire]

Well, if all cykels are of maximum length N/2, each prisoner will open the entire cykel associated with his number => he will open the box containing his own name.

As long as the guard doesn't know which number the prisoners associate with each name (which is reasonable), he can't defeat them.

 

[ParadigmShifter]

If the guard does know the numbering, can he arrange for there to be a cycle of length > N/2?

 

[dutchfire]

How the crap does that work?!

Let's take the 4 prisoner case:

Let's say the distribution in the boxes is:
box 1 2 3 4
name 4 1 3 2

Prisoner #1 opens box 1, finds name 4 => opens box 4, finds name 2. Fail

Other case
box 1 2 3 4
name 4 2 3 1

Prisoner #1 opens box 1, finds name 4 => opens box 4, finds name 1.
Prisoner #2 opens box 2, finds name 2
Prisoner #3 opens box 3, finds name 3
Prisoner #4 opens box 4, finds name 1 => opens box 1, finds name 4
Success!

 

[dutchfire]

If the guard does know the numbering, can he arrange for there to be a cycle of length > N/2?

Sure

box
1 2 3 4 5 6 7 .... 100
name
2 3 4 5 6 7 8 .... 1

Has a single cycle with length 100.

 

[Mise]

Yeah but how come it makes such a huge difference?! I mean, we're talking raising the probability from 10^-10 or whatever, to 10^-1.

And yeah a wily prison guard would just move the digits one space over, so prisoner n would be in box n-1. EDIT: x-post.

 

[dutchfire]

Yeah but how come it makes such a huge difference?! I mean, we're talking raising the probability from 10^-10 or whatever, to 10^-1.

The trick is that the boxes are numbered, this gives additional stucture to the problem.

 

[ParadigmShifter]

He said 30 times better, not 10^9 times

30 times better than 1/2^100 is bugger all 2^100 is an enormous number...

 

[Mise]

He said it raised it to 30%! edit: from 10^-31 to 10^-1, so 10^30 times better.

I'm going to have to think this over Dutchfire. Is there a wiki link I can peruse?

 

[dutchfire]

He said 30 times better, not 10^9 times

30 times better than 1/2^100 is bugger all 2^100 is an enormous number...

The chance of success is now ~30%. One would expect (1/2)^100, so it's about (1/2)^98 times as good.

In the n=4 case, one might expect a (1/2)^4 chance, instead of the actual 10/24, nearly 1/2.

 

[ParadigmShifter]

30% is miles less than 3000% though, which I said

30/2^100 is still a tiny tiny probability.

EDIT: OK, misunderstood (I thought you said chance is 30% better, not 30% probability of a "win"). At least I got the correct answer though!