|
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.
i just read your solution three times and still didn't fully understand it. issit something like infinite monkey theorem ? where if you get a monkey to sit at a keyboard and make it randomly punch out meaningless stuff then at some point it would type out a poem or something, problem is it takes a bit of time.
if thats the case then your original post is quite wrong =(
you said 100% survivors guaranteed
|
ok muri, prove this
suppose i am the judge and i assign hats by tossing a coin. show how you can guarantee ~100% survival rate.
seeing the hat of everyone else confer no information at all about your hat regardless the size of the group.
|
dybydx... read my solution carefully and tell me where the flaw is. I am most familiar with my own writing. I will discuss any point of it with you over PM. However, I can tell you absolutely that the wikipedia article is saying the same thing I am. Here is a third explanation: http://cornellmath.wordpress.com/2007/09/13/the-axiom-of-choice-is-wrong/
Possible clarifications that you might be the source of confusion:
Of course, the entire sequence of hats is determined before anyone writes down anything on a piece of paper. It is necessary that the prisoners see those hats ahead of them before making there guesses. Each prisoner sees infinitely many hats, and only does not see finitely many hats.
|
Wow, my head's gonna explode.
+ Show Spoiler +The solution requires the prisoners to be infinitely fast and have infinite memory, which I can imagine. I'm having a problem with dividing infinity into a finite number of classes, though, which is what the solution seems to require. Maybe that's why I fail at math 
|
Ok more clarifications:
The prisoners do indeed have infinite memory etc.
Not all prisoners escape. However, 100% do because only finitely many die.
BottleAbuser... there are infinitely many classes, each of which contains infinitely many sequences. However, each sequence fits into exactly one of the classes.
Finally, that coin thing is exactly what I am proving dxbydy... infinity is counterintuitive. Read my solution carefully. The fact that nobody has any real information on their own hat means that each has a 50% chance of surviving. Nevertheless, the strange properties of infinity mean that only finitely many die. A very cool paradox in my opinion.
|
On January 23 2008 05:31 Muirhead wrote:
One suddenly realizes that, with a proper strategy, they can ensure that almost 100% of them will survive. What is that strategy?
OK GAIZ wtf do we do?
WAIT i got it. *intense talk* ... so after we do this, our brothers later down the road right around year 982738946826348652837429 are all gonna live! =D but up till then everybody will probably fucking die.
i can only imagine the faces on the prisoners who just heard this strategy.
|
ok bottleabuser,
if you read the wiki solution, it claims at most the first n, prisoners will die, and n+1 onwards will live. this means the prisoners solved the sequence (found the pattern). if i toss a coin instead, you cant solve "randomness".
|
muri,
if i do it by cointoss, 1/2 of em will die, thus infinitely many.
|
dybydx... you are simply wrong... this is why it is a paradox. If the judge does it by cointoss only finitely many prisoners will die.
Read my solution carefully... the key is that all the coin tosses are done before the guesses start. This gives no help in the finite case, but it mysteriously does in the infinite case.
If you do not understand my solution, try reading one of the other two links I gave... to wikipedia and that grad student's blog.
|
muri,
exactly, an infnite number of coin tosses are done before hats are placed. but suppose you see the hats of everyone else, except yours. what colour is your hat? theres no way to guarantee 100%
the wiki soloution says only a finite will die. means you can determine what "finite" is. coin tossing is random and by definition randomness is NOT deterministic. therefore an infinite will die.
|
Okay, infinitely many classes. But still...
+ Show Spoiler +If there are infinitely many classes, how do the prisoners all choose the correct one? There must be some relation (function) that maps each sequence into exactly one class. Is such a function definable? I'm guessing it will also take an infinite amount of memory and time to solve, too, but that's no problem here... I guess if we could define some such function, this problem would be solved. I can't quite grasp it though. Any examples to make it easier to imagine?
|
Ok dybydx... I understand why you think that. You are using your intuition about vague terms like "deterministic." In fact, that finite thing could be as large as the judge wants it to be, and the prisoners will have no way of knowing how big it is. But they will know that it is finite. Before continuing to argue, please read the solutions I gave and look for flaws in them. Once you understand the solutions, then we can continue to discuss. Maybe we should do it by PM so as not to clutter the thread. I'm sorry this caused so much confusion... it is a tricky point :/
|
muri, this is taken from your link....
http://cornellmath.wordpress.com/2007/09/13/the-axiom-of-choice-is-wrong/
How well does this work? Well, the sequence they are actually in and the representative element they picked with the axiom of choice must be equivalent, so they are the same after a finite number of entries. Therefore, after a finite number of incorrect guesses, each prisoner will miraculously guess his hat color correctly!
if its random, you cant rely on it to repeat. it may, it may not. thus, the question require an assumption that the judge can not "truly randomly" assign hats.
|
Definition: Two sequences are in the same class if and only if they differ in only a finite number of places
I hope that is clear.
Ok so the class of a sequence is defined by the eventual behavior of a sequence...
Each prisoner knows exactly how the sequence eventually behaves, even if they don't know how it started out. If you've taken calculus, it's sort of like a limit... the class of the sequence only has to do with eventual behavior.
|
dybydx... Nobody is saying the sequence repeats... the judge can assign hats however the hell he wants
|
muri,
your solution set says the sequence repeats.
|
i got a few questions
what is a "class"?
what is a "sequence"?
if the number of people who die is finite, around how many would you estimate? is the number obscenely large but just because you have infinitely many chances to guess then get it correct from then onwards (i duno how this works but it seems you guys agree on this) the "escaped infinite" will drown out the "obscenely large number of dead" is that right?
hm if the prisoners have super memory and super processing power then i guess memorizing a pattern then finding a pattern wouldn't be impossible but you should have included this in OP =D
|
The classes and sequences are as described in my solution, which I'm repasting here:
+ 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.
I would suggest you look at one of the other two solution sources I gave instead first though, because they are probably clearer than mine...
There is no memorizing of a pattern or processing needed... just the infinite memory required to remember the prisoner's full plan as I described it. If you read my solution it doesn't involve any sort of "cheating" or trickiness. It also doesn't rely on the sequence repeating, dybydx... I just don't understand why you think that
To be clear, two sequences are in the same class if and only if they differ in finitely many places.
As for approximating the finite number of prisoners that survive... that is impossible. It could be anything... as high as the judge wants it to be... but it must be finite.
|
muri,
based on ur description, there are infinitely many classes for each of the prisoners to choose from, and none of the prisoners can guarantee their survival regardless of their position in line.
therefore you can not guarantee a finite number of deaths.
|
On January 23 2008 10:45 dybydx wrote:
btw that 12 coin question suggests there may be a better solution to the simple logarithmic answer to the 1000 coin question. ^^
although personally i would accept the logarithm solution
I don't see how it suggests any such thing. The method used in the 12 coin problem is essentially a mapping of 27 possible cases of the weighing to possible solutions, I.E. >== : Coin 1 is heavy, <== : Coin 1 is light, etc. If you add the knowledge of whether the fake coin is heavy or light as in the normal problem, you could theoretically accommodate up to 27 coins (1 for each case) by this method with the proper configuration, the same maximum that can be dealt with in 3 weighings under the logarithmic method.
Interestingly, there's a way to do the 12 coin problem using a method resembling the standard method for fake coins of specified weight. It requires a bit of careful thinking about which direction the scale tips and how that could be caused in each set of coins. I didn't know about the other method and had a lot of fun working it out earlier. It's important to note for this solution that the problem doesn't demand that you determine whether the odd coin is light or heavy, just which one it is - although my solution does it in 11/12 cases anyway. Spoiler below for anyone who wants to check an answer.
+ Show Spoiler +Split the coins into 3 groups of 4 as you normally would. I label them a1, a2, a3, a4, b1, etc. Start by weighing a1-4 against b1-4. If the scale balances: weigh c1:c2, then c1:c3. If both balance the oddball is c4, if both tip it's c1, if just one of them does it's c2 or c3 as appropriate. If it doesn't balance on the initial weighing: weigh a1a2b1:a3a4b2. If it balances now, the odd coin is either b3 or b4, by weighing them against each other and taking into account which direction the scale tilted earlier, you can find which one. If on the a1a2b1:a3a4b2 weighing it tips the same direction as the first time, the odd coin is a1, a2, or b2. Weigh a1:a2, if they balance it's b2, otherwise you can decide by the way it leaned earlier as with b3/4 above. If a1a2b1-a3a4b2 tips the opposite way from the original a1-4:b1-4, the odd coin is one of a3, a4, b2, so you weigh a3:a4 and proceed as above. Hopefully I actually typed that all up correctly, it worked out when I did it on paper. 
|
|
|
|
|
|
EPT
