EPTBut anyways I just thought the result was really cool
Math Problem - Page 5
| Forum Index > General Forum |
|
Muirhead
United States556 Posts
But anyways I just thought the result was really cool | ||
|
Rev0lution
United States1805 Posts
2. Since the number of prisoners is infinite then even 50% of infinite is still infinite, and 100% of infinite is infinite. It is simply not measurable. 3. in terms of infinite sets, "all" prisoners would be saved because of say N/2 only make it out it is still an infinite amount of prisoners that live. 4. so in fact "almost" 100% make it out alive. or i'm probably flat out wrong >.< | ||
|
dybydx
Canada1764 Posts
| ||
|
Muirhead
United States556 Posts
dybydx, just because infinitely many of them or even more than half survive you can't conclude that ~100% of them survive... I don't understand :/ You do have a nice way to ensure that more than half survive though | ||
|
Slithe
United States985 Posts
| ||
|
iloveHieu
United States1919 Posts
| ||
|
dybydx
Canada1764 Posts
i think we are missing some vital information here. as someone previously said, we need to assume equivalence relations. in other words, to solve this problem we must assume that... 1. the sequencing of the hats are NOT truly random (ie 1 sequence out of a pool of possible sequences is randomly chosen, but once chosen, the sequence repeat eventually) 2. the prisoners know whether or not the previous person was killed or not. + Show Spoiler + http://en.wikipedia.org/wiki/Prisoners_and_hats_puzzle 1. basically what it says is, there is a finite number of ways to sequence the hats. 2. the first person looks to ppl above him and make a best guess what the sequence is. 3. the second person knowing the result of the first person deduces what the remaining possible sequences are, and takes his best guess at it. 4. repeat the result and but deduction, eventually the entire sequencing of hats have been revealed. after n prisoners. 5. n+1'st prisoner and onwards, now knowing the correct sequence, will be able to correctly determine his hat. 6. thus a finite number (even though this number can approach infinite) of prisoners will die, and an infinite number will survive. its incorrect to say "all prisoners have 50% chance of dying." | ||
|
pyrogenetix
China5098 Posts
if these are the rules then i have no way of solving it 1) a black or a white hat is placed on your head at random 2) you are only allowed to look at people in front of you 3) no communication 4) infinitely many people in front of you imo this is impossible. how could I possibly know what coin I tossed simply by looking at what other people got when they all tossed their coins? im sure OP missed something | ||
|
BottleAbuser
Korea (South)1888 Posts
dybydx, your solution makes the assumption that there is a finite number of sequences to assign an infinite number of hats (step 1.). Our problem doesn't give this as a fact, and assuming it is unjustified (there are 2^N possible sequences, where N is infinite). | ||
|
dybydx
Canada1764 Posts
it can be proven that if the sequencing is completely random (ie the life/death of previous prisoner do not convey useful information) then it is not possible to guarantee a survival rate > 50% proof: http://en.wikipedia.org/wiki/One_time_pad | ||
|
dybydx
Canada1764 Posts
On January 23 2008 13:19 BottleAbuser wrote: Our problem doesn't give this as a fact, and assuming it is unjustified (there are 2^N possible sequences, where N is infinite). muri forgot to include that fact. what he meant is n possible sequence and n is arbitarily large and approach infinity, but it is not infinite. the total number of prisoners however is infinite. lets put it this way. 1. the life/death of previous prisoners either a) give you information about future prisoners, or b) it doesnt. 2. if the answer is no, its a one time pad, and it is not solvable. 3. if the answer is yes, then the sequence is either a) a function b) fixed sequence 4. if it is a function, it is not solvable. 5. if it is a sequence, it must repeat and hence solvable. | ||
|
BottleAbuser
Korea (South)1888 Posts
| ||
mikeymoo
Canada7170 Posts
| ||
|
Slithe
United States985 Posts
edit: If you guys want to see some more problems, check my blog. There's one medium level problem and one hard problem. | ||
|
BottleAbuser
Korea (South)1888 Posts
 The problem: + Show Spoiler + There are three doors (or cups, or boxes, or whatever) that you can choose from. You can only choose one. One of the doors, when opened, will give you a prize. The other two give you nothing. Once you have chosen a door, one of the two remaining doors is opened to reveal that it contains nothing. You can now choose to keep your first pick, or switch your pick to the other remaining closed door. Should you keep your first pick, or swap? Why? The solution: + Show Spoiler + You should swap. The probability that you correctly chose on your first pick is 1/3. Obvious; there are three doors, and only one of them is correct. Now, the probability that the prize lies behind the remaining two doors is 2/3. This probability does not change when one of those doors is opened. P(revealed door) + P(remaining door) = 2/3. Except that we know P(revealed door) = 0, so P(remaining door) = 2/3. And P(selected door) = 1/3, still. So swapping gives you 2/3, and keeping gives you 1/3 chance to win. | ||
|
pyrogenetix
China5098 Posts
On January 23 2008 13:38 BottleAbuser wrote: Huh, I didn't see it before in the thread, but I remember solving it before The problem: + Show Spoiler + There are three doors (or cups, or boxes, or whatever) that you can choose from. You can only choose one. One of the doors, when opened, will give you a prize. The other two give you nothing. Once you have chosen a door, one of the two remaining doors is opened to reveal that it contains nothing. You can now choose to keep your first pick, or switch your pick to the other remaining closed door. Should you keep your first pick, or swap? Why? The solution: + Show Spoiler + You should swap. The probability that you correctly chose on your first pick is 1/3. Obvious; there are three doors, and only one of them is correct. Now, the probability that the prize lies behind the remaining two doors is 2/3. This probability does not change when one of those doors is opened. P(revealed door) + P(remaining door) = 2/3. Except that we know P(revealed door) = 0, so P(remaining door) = 2/3. And P(selected door) = 1/3, still. So swapping gives you 2/3, and keeping gives you 1/3 chance to win. That is the monty hall | ||
|
dybydx
Canada1764 Posts
suppose all prisoners wrote that "black" and so far after n prisoners, a,b,c...k are dead we can come up with a function that f(1) = a, f(2) = b, f(3) = c..... f(n) = k but there are finitely many functions that will do the same. thus past information do not confer any information about future prisoners. | ||
|
Muirhead
United States556 Posts
"In this variant, a countably infinite number of prisoners, each with a unknown and randomly assigned red or blue hat line up single file line. Each prisoner faces away from the beginning of the line, and each prisoner can see all the hats in front of him, and none of the hats behind. Starting from the beginning of the line, each prisoner must correctly identify the color of his hat or he is killed on the spot. As before, the prisoners have a chance to meet beforehand, but unlike before, once in line, no prisoner can hear what the other prisoners say. The question is, is there a way to ensure that only finitely many prisoners are killed (and hence, an infinite number are saved)? If one accepts the axiom of choice, the answer is yes" | ||
|
Muirhead
United States556 Posts
+ 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. | ||
|
dybydx
Canada1764 Posts
if you read rest of the wiki solution, it says that eventually the prisoners can deduce the sequence and after n trials, n+1 and onwards prisoners will be saved. thus a finite number will die, an infinite number will live. despite n being arbitrarily large and approach infinity, it is NOT infinite. if the sequence is "just anything" (truly random), it will not be deducible no matter how large n is. when wiki said "randomly assiged" it actually meant a sequence, out of a possible pool of size 2^n is randomly assigned. | ||
| ||
