• Our friends from AlphaCentauri2.info are in need of technical assistance. If you have experience with the LAMP stack and some hours to spare, please help them out and post here.

Let's discuss Mathematics

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...
 
Is it to do with powers of x modulo the number of boxes?
 
Ah good call Mise, do the prisoners know the names and numberings of the other prisoners?
 
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.
 
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.
 
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.
 
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.
 
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?
 
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.
 
If the guard does know the numbering, can he arrange for there to be a cycle of length > N/2?
 
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!
 
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.
 
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.
 
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.
 
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...
 
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?
 
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.
 
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!
 
Back
Top Bottom