We can number the prisoners and the boxes have already been numbered, so a configuration in this case is just a permutation of the numbers 1-100. What you should have is that the final chance doesn't depend on the numbering of the prisoners (or of the boxes).
Let's discuss Mathematics
- Thread starter ParadigmShifter
- Start date
We can number the prisoners and the boxes have already been numbered, so a configuration in this case is just a permutation of the numbers 1-100. What you should have is that the final chance doesn't depend on the numbering of the prisoners (or of the boxes).
ParadigmShifter
Random Nonsense Generator
Let's simplify it for tipsy PS.
Minimum number of prisoners is 4 if looking at the contents of a box is to have any effect (and opening an integer number of boxes).
Minimum number of prisoners is 4 if looking at the contents of a box is to have any effect (and opening an integer number of boxes).
Mise
isle of lucy
The prisoners can't communicate with each other I guess?
ParadigmShifter
Random Nonsense Generator
OK, so wlog (without loss of generality), prisoner 1 opens box 1.
If he doesn't see his name... hmm.
I suspect first move is for prisoner x to open box x, and for subsequent openings depend on something I can't imagine at the moment.
Good so far?
If he doesn't see his name... hmm.
I suspect first move is for prisoner x to open box x, and for subsequent openings depend on something I can't imagine at the moment.
Good so far?
Mise
isle of lucy
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
Random Nonsense Generator
Is it to do with powers of x modulo the number of boxes?
ParadigmShifter
Random Nonsense Generator
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
Random Nonsense Generator
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.
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.
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
Random Nonsense Generator
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?
EDIT: Can that strategy be defeated by a wily prison guard though? Or are you assuming the box/name distribution is random?
Mise
isle of lucy
How the crap does that work?!
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.
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
Random Nonsense Generator
If the guard does know the numbering, can he arrange for there to be a cycle of length > N/2?
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!
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
isle of lucy
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.
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.
Similar threads
