EPTMath Problem - Page 7
| Forum Index > General Forum |
|
Muirhead
United States556 Posts
| ||
|
dybydx
Canada1764 Posts
1. theres infinite classes and infinite elements in each class. 2. each prisoner picks 1 sequence from each class and memorize it. (thus each memorizes infinitely many) 3. since they are able to see prisoners "above" them they know which class they are in. 4. suppose this prisoner's (p1) sequence belong to a class that is equivalent after a trials, there is a finite number of sequences that match this property (2^a). the prisoner guess according to his memorized sequence of that class. 5. the next prisoner's (p2) sequence may belong to a class that is equivalent after b trials. there are 2^b possibilities. the prisoner guess according to his sequence 6. as the prisoners repeat, eventually on the a'th (or b if b is lower) prisoner, after realizing the fate of all prisoners before him, correctly deduces the rest of the sequence. i donno if dats correct interpretation of it. | ||
|
MoNKeYSpanKeR
United States2869 Posts
Mike gets told the date John gets told the month Does mike now its 9/1 and john knows it's 9/? | ||
|
MoNKeYSpanKeR
United States2869 Posts
| ||
|
Muirhead
United States556 Posts
1. No prisoner has any knowledge of the previous prisoners' fates. They all write down their guesses simultaneously. The prisoners have even less information than I think you believe they do. 2. THIS IS THE KEY: In step 2, the prisoners all agree on the SAME sequence from each class. Every prisoner memorizes the same sequence for every class. Now, let's look from the perspective of prisoner 1 as he see the other prisoners' hats. He knows what class he is in. He knows that, after, say, the 2734th prisoner, the judge's sequence starts to agree with the chosen representative of the judge's class. Then, the 2735th prisoner will go free, as will the 2736th, the 2737th, etc. The very first prisoner knows immediately which of his fellow prisoners will go free. Does that help explain? | ||
|
BottleAbuser
Korea (South)1888 Posts
+ Show Spoiler + Each sequence representing its class is identical to every other sequence in its class, except perhaps for the first m elements. The first m people may therefore die. However, every person after person m will definitely live. Where m is, is irrelevant, because it's a finite number. But then again, I keep running into this idea: Every ith person can correctly choose the class that represents the sequence correctly ("correctly enough"), except perhaps his own. Iterating this over i from 0 to N will still give us 1/2 survival? I can't reconcile it. | ||
|
Muirhead
United States556 Posts
 Also, you are right that each individual person has a 1/2 chance of surviving, even though as a whole 100% will survive. This is the paradox and it is intimately related to assuming the axiom of choice, or that it is possible to choose one representative of each of an infinite number of classes. The axiom of choice is generally accepted nowadays, though it wasn't always. It just means that some of the normal notions about expected value and probability don't always extend to infinite situations. It also means that it is impossible to define a good notion of volume for every subset of Euclidean space. | ||
|
dybydx
Canada1764 Posts
2. THIS IS THE KEY: In step 2, the prisoners all agree on the SAME sequence from each class. Every prisoner memorizes the same sequence for every class. Now, let's look from the perspective of prisoner 1 as he see the other prisoners' hats. He knows what class he is in. He knows that, after, say, the 2734th prisoner, the judge's sequence starts to agree with the chosen representative of the judge's class. Then, the 2735th prisoner will go free, as will the 2736th, the 2737th, etc. The very first prisoner knows immediately which of his fellow prisoners will go free. Does that help explain? i think the fallacy in this is to prove there always exists such a sequence, although this might come in conflict with acceptance of AC | ||
|
Monoxide
Canada1190 Posts
On January 23 2008 13:51 Muirhead wrote: Here is the solution as I PMed Bottleabuser. An alternative formulation of the solution can be found on wikipedia. + Show Spoiler + Ok here is the solution. I hope it is satisfactory . It's supposed to be more of a demonstration of a cool paradox than a puzzle. Represent a sequence of hats by 1s and 0s, with 1s being black and 0s being white. Then the judges input is going to be an infinite sequence of 1s and 0s. Call two sequences "almost the same" if, after a finite number of initial entries, they become the same. For example, two almost the same sequences could be different in the billionth place but never differ afterwards. Now, all of the possible infinite sequences can be partitioned into classes, where any two elements of the same class are almost the same. The prisoners all get together and choose one special sequence out of each class. When a given prisoner sees the hats in front of him, he can immediately tell the class of the sequence the judge has chosen, because that does not depend on the hats before him. He then guesses that his hat is the one from the chosen sequence out of that class. Now, the chosen sequence must eventually agree entirely with the judges sequence, so from a certain point onwards all prisoners will be set free. That one-time pad stuff has nothing to do with anything BECAUSE THERE ARE INFINITELY MANY PRISONERS . That is why the problem is so cool... the finite case is obviously very different.Please PM me if you still don't understand. hmm thats correct... when u say from a certain point onwards, all prisoners will be set free, that means from that point BACK, the prisoners will have a 50% chance of being exucuted?? | ||
|
dybydx
Canada1764 Posts
yes. until the sequence merge, you have no way of telling. so it becomes luck. | ||
|
Monoxide
Canada1190 Posts
| ||
| ||
