|
Someone posted this in my bw qq(chat) group just now and I thought people on TL would like this. Original names are replaced with English ones.
John and Mike are both pupils of Mr.Stevenson, Mr.Stevenson's birthay is on M/N, M = Month, N = Date. Mr. Stevenson told John "M" and Mike "N". John and Mike both know Mr.Stevenson's birthday is one of the following 10 dates.
3/4 3/5 3/8
6/4 6/7
9/1 9/5
12/1 12/2 12/8
John says: "If I don't know the date, then Mike can't either"
Mike says: "I didn't know it at first, but now I know it"
John says: "Now I know it too."
From the above conversation, figure out what Mr.Stevenson's birthday is.
|
Aotearoa39261 Posts
haha my friend gave this to me in stats class was wtf at first but yea
|
either 9/1 or 12/1 my guess is 12/1
|
|
+ Show Spoiler + i dont have any logic, im bad for riddles, but mike said 'i didnt know it at FIRST' so he might be telling him a clue that its on january
|
argh.. ignore what i said earlier lol
|
Its more logic than math imo..
|
The month can't be 12 or 6. The guy starts off by saying his friend can't know the date. Both december and june have days exclusive to them and there is no way for John to know that Mike didn't get an insta-win. My guess is Mike's number is a 5. So either 3/5 or 9/5.
btw, I don't understand why it starts "If I don't know the date.." How on earth could he know the date? All he was given was the month of the year and every single month has more than one day that it could be.. There's no if.
|
On January 22 2008 23:02 dybydx wrote:means knowing day or the month number alone is not sufficient to determine which 1 is correct thus it can not be 6/7 and can not be 12/2
How can John know this ??? He has only the month number. There is no way to reach that conclusion.
|
On January 22 2008 23:04 BlackJack wrote: The month can't be 12 or 6. The guy starts off by saying his friend can't know the date. Both december and june have days exclusive to them and there is no way for John to know that Mike didn't get an insta-win. My guess is Mike's number is a 5. So either 3/5 or 9/5.
btw, I don't understand why it starts "If I don't know the date.." How on earth could he know the date? All he was given was the month of the year and every single month has more than one day that it could be.. There's no if. + Show Spoiler +ah it´s 9/1. misread something
1. statement: month 3 and 9 are left 2. statement: days 1, 4 and 8 are left 3. statement: day 1 is left => 9/1
|
+ Show Spoiler +John says: "If I don't know the date, then Mike can't either"
Means that it cant be either in the month 6 since thn Mike could have known the date 6/7. It cant be any in the month 12 either for the same reason.
Mike says: "I didn't know it at first, but now I know it"
Means it is one of the number which are single days 3/4 3/8 and 9/1
John says: "Now I know it too."
means it is 9/1
|
|
maybe we should all use spoiler tags
|
|
On January 22 2008 23:19 dybydx wrote:means knowing day or the month number alone is not sufficient to determine which 1 is correct thus it can not be 6/7 and can not be 12/2 Mike realizes that if John knows day number is insufficent, it means it can not be 6/X or 12/X Now Mike knows the number. John realizes his statement allow Mike to deduce the month number. This means the day number must b 8, since 8 is in both 3/X and 12/X ANSWER: 3/8
Haha you are falling at the finish..
|
Yeah I didnt understand why it couldnt be 12\8
|
John says: "If I don't know the date, then Mike can't either" means knowing day or the month number alone is not sufficient to determine which 1 is correct
thus it can not be 6/7 and can not be 12/2. Thus John knows it can not be 6/X or 12/X
Mike says: "I didn't know it before, but now I know it" Mike realizes that it can only be 3/X or 9/X Now Mike knows the number.
John says: "Now I know it too." John realizes his statement allow Mike get the month, thus it can not be 3/5 or 9/5 This leaves 3/4, 3/8 and 9/1 Now John has the answer. Because the number he has is 9
ANSWER: 9/1
Meander got it first. GJ
|
how can you conclude that if 12/2 is impossible, 12/1 and 12/8 are impossibe too?
|
On January 22 2008 23:31 dybydx wrote:means knowing day or the month number alone is not sufficient to determine which 1 is correct thus it can not be 6/7 and can not be 12/2. Thus John knows it can not be 6/X or 12/X Mike realizes that it can only be 3/X or 9/X Now Mike knows the number. John realizes his statement allow Mike get the month, thus it can not be 3/5 or 9/5 This leaves 3/4, 3/8 and 9/1 Now John has the answer. Because the number he has is 9 ANSWER: 9/1 Meander got it first. GJ
Maybe it is because of my English, but I don't get it at all. If you can explain the first statement a little bit more, that would help me understand the whole thing a lot.
|
Statement 1: John has the month number, and using that number alone, he knows Mike will not be able to determine the date. Thus John knows the date is not 6/7 or 12/2. He knows this because the month number he got is not 6 and not 12.
|
agreed with 9/1, though i think the whole question is kind of stupid ;P
|
On January 22 2008 23:38 .MistiK wrote: how can you conclude that if 12/2 is impossible, 12/1 and 12/8 are impossibe too? I don't understand this part either.
|
ok
If Mike's number is 7 or 2 then he immediately knows which day it is. (6/7, or 12/2) John's first statement means that he know, using the day of the month alone is insufficent. Thus John knows the month is not 6/X and its not 12/X
|
but why? with only 6/4 left, it's clear that 6 is not possible because then john would know the date but there's 12/1 and 12/8 left so john wouldn't know the date if his month was 12
|
suppose mike's number is 2, then mike know right a way its 12/2 then john's 1st statement is false
|
suppose mike's number is 8, then mike knows what? and how can john then eliminate 12/8? [edit] forget it i'm gonna ask maenander irl to clarify
|
On January 23 2008 01:07 Konni wrote:suppose mike's number is 8, then mike knows what? and how can john then eliminate 12/8? [edit] forget it i'm gonna ask maenander irl to clarify
+ Show Spoiler +If mike's number was D = 8, john would have M = 12. If john had M = 12, he would not know that mike didn't know it, because 12/2 is the only date with 2 as the day. John's first statement shows that he knows it is not a date that has only 1 date with the given day. This means his month cannot be 12 and it cannot be 6.
|
On January 23 2008 01:24 LonelyMargarita wrote:Show nested quote +On January 23 2008 01:07 Konni wrote:suppose mike's number is 8, then mike knows what? and how can john then eliminate 12/8? [edit] forget it i'm gonna ask maenander irl to clarify + Show Spoiler +If mike's number was D = 8, john would have M = 12. If john had M = 12, he would not know that mike didn't know it, because 12/2 is the only date with 2 as the day. John's first statement shows that he knows it is not a date that has only 1 date with the given day. This means his month cannot be 12 and it cannot be 6. Thank you, I got it! + Show Spoiler +I would've understood it better if John just would've said: "Mike can't know the date". Because the if-clause is totally confusing and useless (John can't know the date in the first place with no information about Mike's number)
|
+ Show Spoiler + 3/4
John says: "If I don't know the date, then Mike can't either"
(Mike, knowing he has 4 would deduce that it's either 3/4 or 6/4 at the beginning. John, having 3, knows it's 3/4, 3/5, or 3/8.)
Mike says: "I didn't know it at first, but now I know it"
if it was 6/4, John's statement would be false because John would have 6 which gives the possibility of Mike knowing the answer right from the beginning
John says: "Now I know it too."
(John can use the same logic as Mike here to figure it out)
|
to the op: your use of the word "date" is confusing.
|
atarianimo,
if mike really had 4, john would have no way of guaranteeing 3/4 is the right date
|
to explain the first step: */7 */2 only appear once. Each other number is mirrored. Meaning that If I know the day is the second, only one month is possible. If I know the day is the 8th, 2 different months are possible.
because 7th and the 2nd only appear once, mike can rule those out as soon as john gives the hint
|
He knows it's 3/4 because if it was 6/4, John's statement would be false (John would have 6 and therefore think it is either 6/4 or 6/7, if it was 6/7, Mike would know right away, since that's the only date with the day as 7.)
|
Good question. It's better to set out the problem like this: + Show Spoiler + month 3-- | -- | -- | 4 | 5 | -- | 8 6-- | -- | -- | 4 | -- | 7 |- 9-- | 1 | -- | -- | 5 | -- |- 12 | 1 | 2 | -- | -- | -- | 8
then you clearly see which month have which days i common and you just have to cross out whole rows/colmns
|
if john had 3, as far as john knows, mike could have had 8
|
That is why John didn't know the answer until Mike says: "I didn't know it at first, but now I know it"
If Mike had 8 or 5, he wouldn't have been able to figure it out from John's opening statement.
|
if mike had 8, he would know the date is 3/8, after john tell him 6/X and 12/X are impossible.
Edit by Chill:
Adam, Bruce and Chris got arrested for crimes. Court sentenced 1 of em to death and release the other 2.
Adam asked the guard which one of his friends will be released. The guard said Bruce.
Assuming the guard is honest, what is probability of Chris being sentenced to death?
[Show proof, guessing a number doesnt count]
|
dybydx, your other math problem is not even a math problem. The answer is 100%. Adam asked the guard which one of his friends will be released. So... he obviously knows he's not the guilty one, but one of the other two and since the guard tells who isn't, the answer is obvious.
|
i never said hes not the guilty one. you assumed it.
|
He asked which of his friends will be released, he wouldn't ask if he was guilty, because he would know that both would be released. Also, the guard wouldn't answer in this way, if they were both released.
|
Calgary25942 Posts
I see three cases:
A..B..C I....I...G I...G...I G..I....I
+ Show Spoiler +I must be missing something because I don't see how it is anything but 50%. I'm terrible at these types of logic problems anyways, I always miss the point.
|
well then let me make it clear now, Adam does NOT know whether he got sentenced to death or not.
(even if he was innocent the court can still sentence him to death anyways)
|
Calgary25942 Posts
So basically, + Show Spoiler +there's 3 socks, one is black. Number 3 isn't black. What's the chance Number 1 is black. What am I missing here?
|
Chill not quite.. doesnt work that way. the grouping matters.
|
Calgary25942 Posts
Well I know you're a smart guy so you wouldn't have asked a question that simple. Whatever I'm missing is just going above my head :D
|
1/3 chance Adam is guilty, 2/3 chance one of the other 2 is guilty. Chance that one of the other 2 is not guilty = 100% Chance that Adam is guilty = 1/3, chance that Chris is guilty = 2/3
Guilty = sentenced... whatever wording you prefer, that's just what the answer is.
|
lololol is correct on this one, it's basically the old 2 donkeys, 1 car behind 3 doors problem.
|
ING DING DING* + Show Spoiler +
Next problem! There are 1000 coins, 1 of em is fake and weighs less than others. using a balance scale, how many times do you have to weigh to find out which coin is fake. http://en.wikipedia.org/wiki/Weighing_scale#Balance
[a harder version. there are x coins, and your balance has y bowls (your balance can tilt in m directions). how many times does it need now?]
|
On January 23 2008 03:28 dybydx wrote:ING DING DING* + Show Spoiler +Next problem! There are 1000 coins, 1 of em is fake and weighs less than others. using a balance scale, how many times do you have to weigh to find out which coin is fake. http://en.wikipedia.org/wiki/Weighing_scale#Balance[a harder version. there are x coins, and your balance has y bowls (your balance can tilt in m directions). how many times does it need now?]
You divide the pile of coins in half and measure both halves. You discard the heavier pile.
You repeat the procedure. If your pile has an odd number of coins you set one coin aside and measure the 2 piles. if they both weigh the same, you have found your fake coin.
I counted a maximum of 18 measurements.
Edit: sorry I mean 9 measurements on the balance scale. But the method described below of dividing it into 3 piles is more efficient.
|
If you divide the coins into 3 piles: 333, 333, and 334 then weigh the two piles of 333 against each other. In the worst case, the coin will be in the stack of 334. Repeat the procedure using piles of 111 with the pile of 112 not on the scale. Continue to repeat until you have 5 coins: place 2 stacks of 2 on the scale and leave 1 coin off. In the worst case you need 1 more measurement after that.
I count a maximum of 7 measurements
|
If that was correct (or even if it wasn't ) I'd like to propose the following puzzle:
Four people are on one side of a bridge in the dark. The bridge can only support 2 people at a time. There is only one torch among the four of them and the torch needs to be carried along with the pair crossing the bridge.
The people take different times to cross the bridge:It takes them 10 mins, 5 mins, 2 mins and 1 min respectively. A pair crossing the bridge walks at the speed of the slowest of the two of them.
What is the minimum time for all of them to have crossed the bridge?
Edit: Bad wording, sorry. What is the minimum time it takes to have them all end up on the opposite side of the bridge?
Answer: + Show Spoiler +
|
that's a neat riddle but i first saw it in my math class for 7th grade and almost everyone got it pretty quickly, i think TL is a little beyond that level ;p
|
Oh well, I thought it was fun. Even if you find it too easy, I still think people will appreciate seeing it.
|
On January 23 2008 03:28 dybydx wrote: [a harder version. there are x coins, and your balance has y bowls (your balance can tilt in m directions). how many times does it need now?]
+ Show Spoiler [Answer] +I'm pretty sure this is ceiling(log base (y+1) (x)). In a less technical format, (y+1)^n = x, solve for n, rounding up, gives the smallest possible worst case number of measurements.
|
This one is hard:
You have 12 identical-looking coins and a balance that compares the weight on its two arms and only says which side is heavier and which is lighter. One of the coins is fake and differs only in weight, however, when you get the coins, you don't know if the fake one is lighter or heavier. What you need is a foolproof method of finding the fake coin in 3 weighings.
|
I still don't understand the original op problem, how did you eliminate dates?
|
On January 23 2008 04:56 MPXMX wrote: This one is hard:
You have 12 identical-looking coins and a balance that compares the weight on its two arms and only says which side is heavier and which is lighter. One of the coins is fake and differs only in weight, however, when you get the coins, you don't know if the fake one is lighter or heavier. What you need is a foolproof method of finding the fake coin in 3 weighings.
my favorite riddle of all time. spent like a week trying to figure it out until i gave up, then i nailed it in like 10 minutes months later when waiting for an exam lol
|
MPXMX's problem: + Show Spoiler + Label the coins 1-12. Then do the following weighings: 1 4 6 10 against 5 7 9 12 2 5 4 11 against 6 8 7 10 3 6 5 12 against 4 9 8 11
Listing out all the cases shows that these weighings uniquely determine the false coin and whether it is lighter or heavier.
Problem/Paradox: There are countably infinite many prisoners sitting in a row (i.e. the prisoners are numbered 1,2,3,4,5,... on to infinity)
One day a judge comes and says to them: Tomorrow you will each be given either a black or a white hat. You will be able to see the hats of those prisoners with a higher number than yours, but not the hats of those prisoners with a lower number than yours. You will not be able to see your own hat. You will then each simultaneously write down a guess of either black or white on a piece of paper. If you guess your own hat color correctly, you will be set free. Otherwise you will be executed.
The prisoners discuss all night what they will do. One suddenly realizes that, with a proper strategy, they can ensure that almost 100% of them will survive. What is that strategy?
|
On January 23 2008 04:35 RzzE wrote:If that was correct (or even if it wasn't ) I'd like to propose the following puzzle: Four people are on one side of a bridge in the dark. The bridge can only support 2 people at a time. There is only one torch among the four of them and the torch needs to be carried along with the pair crossing the bridge. The people take different times to cross the bridge:It takes them 10 mins, 5 mins, 2 mins and 1 min respectively. A pair crossing the bridge walks at the speed of the slowest of the two of them. What is the minimum time for all of them to have crossed the bridge? Answer: + Show Spoiler +
I guess I must still be in 6th grade, but it seems that this is a bit of a trick question.
+ Show Spoiler +To answer the question as worded the answer to me would be 16 mins. However, the 1 min person will still be on the same side of the bridge, having crossed the bridge with the 10min person, returning which takes 1 min, and then brought the torch back allowing the 5 min (and 2 min) person to cross with the torch.
If the 4 people are to remain on the opposite side of the bridge, would not the answer be 19 mins, as the 1 min person has to come back twice taking an additional 2 mins, to accomany the others on their respective trips. Please explain how 17 min is correct .
|
Your phrasing of the old monty hall problem is very bad. He asks which one of his friends will be released. To anyone who understands english well, this implies that he realizes only one of them will be released.
To give an everyday sort of example, if you were choosing your schedule for college, and you had a list of math classes, I wouldn't ask "which one are you taking," unless I already knew you were only taking one of them. I don't know any native english speaker who would.
|
On January 23 2008 05:34 LossLeader wrote:Show nested quote +On January 23 2008 04:35 RzzE wrote:If that was correct (or even if it wasn't ) I'd like to propose the following puzzle: Four people are on one side of a bridge in the dark. The bridge can only support 2 people at a time. There is only one torch among the four of them and the torch needs to be carried along with the pair crossing the bridge. The people take different times to cross the bridge:It takes them 10 mins, 5 mins, 2 mins and 1 min respectively. A pair crossing the bridge walks at the speed of the slowest of the two of them. What is the minimum time for all of them to have crossed the bridge? Answer: + Show Spoiler + I guess I must still be in 6th grade, but it seems that this is a bit of a trick question.
Sorry about the wording. I mean what is the minimum time to unite all the four people on the opposite shore.
|
On January 23 2008 05:31 Muirhead wrote: Problem/Paradox: There are countably infinite many prisoners sitting in a row (i.e. the prisoners are numbered 1,2,3,4,5,... on to infinity)
One day a judge comes and says to them: Tomorrow you will each be given either a black or a white hat. You will be able to see the hats of those prisoners with a higher number than yours, but not the hats of those prisoners with a lower number than yours. You will not be able to see your own hat. You will then each simultaneously write down a guess of either black or white on a piece of paper. If you guess your own hat color correctly, you will be set free. Otherwise you will be executed.
The prisoners discuss all night what they will do. One suddenly realizes that, with a proper strategy, they can ensure that almost 100% of them will survive. What is that strategy?
+ Show Spoiler +they each ask the guy below them what color their hat is. then that guy tells them and that's what they right down. everyone lives except for the first guy.
|
Haha... sorry they can't speak with or see anyone below them...
|
The most common posing of this problem has the prisoners guess audibly their hat in sequence. This allows them to use parity to save prisoner 2 and up 100% of the time and prisoner 1 50% of the time.
Requiring the guesses to be simultaneous and written, while not allowing them to communicate in any way, removes this option.
I don't see how they can get anywhere near 100% unless it is something silly like each prisoner writes down his guess and signs it as the prisoner in front of him.
|
On January 22 2008 23:31 dybydx wrote:means knowing day or the month number alone is not sufficient to determine which 1 is correct thus it can not be 6/7 and can not be 12/2. Thus John knows it can not be 6/X or 12/X Mike realizes that it can only be 3/X or 9/X Now Mike knows the number. John realizes his statement allow Mike get the month, thus it can not be 3/5 or 9/5 This leaves 3/4, 3/8 and 9/1 Now John has the answer. Because the number he has is 9 ANSWER: 9/1 Meander got it first. GJ
I think your explanation is kinda confusing so I will try to rephase it. I hope it'll make more sense to other ppl.
John says: "If I don't know the date, then Mike can't either"
Mike says: "I didn't know it at first, but now I know it"
John says: "Now I know it too."
John is given the Month Mike is given the Date. John's 1st statement mean you cant figure it out just by month or date.. X/7 and X/2 is the only 2 date in there that doesnt have any other dates in diff month. Thus the date can't be 7 or 2. Now Mike know that date can't be 7 or 2 but he know the real date. So it can't be 6/X since if he know 6/7 is impossible then 6/4 is left. It can't be 12/X since if it is in 12/X then John's 1st statement wouldn't be true. It would be a contradiction.
Mike realize now it can only be 3/X or 9/X possible choices: 3/4 , 3/5, 3/8 , 9/1, 9/5
Mike now say he didnt know it at first but now he know it. Thus it can't be 3/5 or 9/5 since mike know the date he doesnt know the month thus if it was the 5th, Mike would still dont know if it's 3/5 or 9/5. Possible choices: 3/4, 3/8, 9/1 John know the Month thus now knowing that Mike figure out the date means that the month must be 9/1.
|
On January 23 2008 06:16 Muirhead wrote: Haha... sorry they can't speak with or see anyone below them... By this stmt i am assuming you are telling us they CAN speak with ppl ABOVE them. How about the first prisoner purpose speakout the color of the hat of the person immediately "above" him. (the first person can write anything down, he dies 50% of the time anyways.) this way, the 2nd person knows what to right down. repeat the process and ~100% of em will live.
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
For those interested in some raw math questions... Which is greater, e^pi or pi^e? Provide proof. (obviously "my calculator say so" is not a proof)
[edit o god the typos :<
|
On January 23 2008 10:45 dybydx wrote:Show nested quote +On January 23 2008 06:16 Muirhead wrote: Haha... sorry they can't speak with or see anyone below them... By this stmt i am assuming you are telling us they CAN speak with ppl ABOVE them. How about the first prisoner purpose speakout the color of the hat of the person immediately "above" him. (the first person can write anything down, he dies 50% of the time anyways.) this way, the 2nd person knows what to right down. repeat the process and ~100% of em will live. For those interested in some raw math questions... Which is greater, e^pi or pi^e? Provide proof.(obviously "my calculator say so" is not a proof)
On January 23 2008 10:01 LTT wrote: The most common posing of this problem has the prisoners guess audibly their hat in sequence. This allows them to use parity to save prisoner 2 and up 100% of the time and prisoner 1 50% of the time.
Requiring the guesses to be simultaneous and written, while not allowing them to communicate in any way, removes this option.
I don't see how they can get anywhere near 100% unless it is something silly like each prisoner writes down his guess and signs it as the prisoner in front of him.
Ok you guys there is no trick... they can't speak to one another at all. As a hint, remember that there are infinitely many prisoners. That is very important, and the reason the paradox works. By the way, the paradox is a probabilistic interpretation of the existence of nonmeasurable sets.
As for the e^pi vs. pi^e question... taking logs we want to know if ln(e)/e or ln(pi)/pi is bigger. But ln(x)/x is decreasing on the range [e,pi], as can be seen by taking the derivative. Thus, ln(e)/e>ln(pi)/pi, which implies e^pi>pi^e
|
To LossLeader on the bridge problem: + Show Spoiler + 4 people are on, say, the left side of the bridge, and we want to bring all of them over to the right side. They take 10, 5, 2, 1 minutes to cross, and only 1 or 2 can cross at once, and they need to carry the torch.
Person 1 and Person 2 cross to right side. +2 minutes have elapsed.
Person 1 crosses back to left side. +1 minutes cost.
Person 1 hands the torch over to Person 10 and Person 5, who cross the bridge together. +10 minutes cost.
Person 5 hands the torch over to Person 2, who crosses the bridge again (to the left). +2 minute cost.
Person 2 and Person 1 cross the bridge together to the right. +2 minute cost.
Adding them gives us 17 minutes.
|
Muirhead's hat problem:
We don't know what relationship one's own hat has with the hats other people have. We don't even know if 1/2 of the hats are black or white (that is, everyone's hat might be black but yours, or whatever). I don't think there's enough information to guarantee (statistically) ANY number of survivors.
|
|
I didn't bother going through the reasoning, but the result is correct. If pi^e - e^pi < 0, that implies that e^pi > pi^e, which was his result.
|
8716 Posts
I think that e^pi is greater than pi^e. Throughout the histories of many cultures, there have been a number of discoveries that have startled the peoples of the nations inhabited thereby. One of those such discoveries is that of pi^e whichof when it has been transliterated becomes a number so-called "raised" to another number, both of which of these numbers hitherto referred is another number onto which many special, even "magical" properties subside. Firstly, is the property futurely noted as The Log Property for which the e number and its subsidiaries are so famously recognized by the nations inhabited thereby. Not to be confused with the pi, nor almost equally sometimes confused previously mentioned the number for which it has been "raised" unceremoniously called The Circle Property for which many mysterious mysteries have been conducted by leading investigators of our scientific fields (BBC, 1998). The following sentences are making a transition for a place in a further along beyond "elementary" and so accordingly those of you whom have been satisfactorily understanding so far may no longer "ride the boat" so to speak as the waves tumble and crumble into an advanced setting. Rigorously speaking in mathematically hard terminologies, bolstered by the affections of the sciences of the computers, and so unceremoniously provided by the peoples of the nations inhabited thereby, it is reasonable enough to put forward, in precedent of QED, that pi^e is sometimes considered greater than e^pi, but this is a grave error. Microscopic examinations, and no closer, will reveal that in sample sizes that shallforth staunchly forhold no numbers that should, in any circumstances (and should they, Teamliquid.net © 2002-2008 All Rights Reserved shall not be held responsible) children under the age of 14 should be exercising caution, shall not in whatever cases, as aforementioned peoples should agree, will without question be below 5. In conclusion, Ungoro Crater is a 0.
|
I didn't bother going through the reasoning, but the result is correct. If pi^e - e^pi < 0, that implies that e^pi > pi^e, which was his result.
dat dude edited his answer :< not fair :'(
besides his proof isnt complete anyways
|
I don't understand what is wrong with my proof that e^pi>pi^e... Yes I edited the answer after I made a stupid mistake the first time .
In complete rigor:
ln(x)/x has derivative (x*1/x-ln(x)*1)/(x^2)=(1-ln(x))/(x^2) which is negative in the range (e,pi).
Thus, ln(pi)/pi<ln(e)/e, so e*ln(pi)<pi*ln(e), so ln(pi^e)<ln(e^pi)
Hence, as ln is an increasing function, pi^e<e^pi
My problem really is a paradox... it is in fact true that each prisoner "has a 50%" chance of dying, but overall 100% of them are guaranteed to survive. There is no relationship amongst the hats. You may assume if you like that the judge overheard the prisoners strategy and chooses his assignment of hats in a way to kill as many prisoners as possible. Please ask if you need any specific clarifications. Of course, assume the axiom of choice. There are countably infinite many prisoners, so this is not a "real-life" situation. The sequence of hats could be any infinite sequence like black,white,black,black,black,white,white,black,... It is also possible for all hats to be black.
|
On January 23 2008 06:01 BlackJack wrote:Show nested quote +On January 23 2008 05:31 Muirhead wrote: Problem/Paradox: There are countably infinite many prisoners sitting in a row (i.e. the prisoners are numbered 1,2,3,4,5,... on to infinity)
One day a judge comes and says to them: Tomorrow you will each be given either a black or a white hat. You will be able to see the hats of those prisoners with a higher number than yours, but not the hats of those prisoners with a lower number than yours. You will not be able to see your own hat. You will then each simultaneously write down a guess of either black or white on a piece of paper. If you guess your own hat color correctly, you will be set free. Otherwise you will be executed.
The prisoners discuss all night what they will do. One suddenly realizes that, with a proper strategy, they can ensure that almost 100% of them will survive. What is that strategy? + Show Spoiler +they each ask the guy below them what color their hat is. then that guy tells them and that's what they right down. everyone lives except for the first guy.
I thought of the same lol, the first prisoner would say what hat color he sees and then go on and on until all prisoners are done, all save but the first guy.
EDIT: I will try to solve it in a later post...
|
On January 23 2008 11:30 Muirhead wrote: In complete rigor:
ln(x)/x has derivative (x*1/x-ln(x)*1)/(x^2)=(1-ln(x))/(x^2) which is negative in the range (e,pi).
Thus, ln(pi)/pi<ln(e)/e, so e*ln(pi)<pi*ln(e), so ln(pi^e)<ln(e^pi)
Hence, as ln is an increasing function, pi^e<e^pi
accepted ^^ GJ
|
Muirhead, I'm stumped. PM me the resolution or something pls.
Okay, for each prisoner, he has 50% chance of correctly guessing his own hat if he randomizes his decision. This will imply that an infinite number of prisoners (N/2) will survive, which seems nice, but that still approaches 50%, not 100%. Probably not the correct approach.
|
it has to do with the fact that u can see prisoners above you.
but we need info on what kind of interaction you are allowed to have with other prisoners. muri, are we allowed to interact in any way? other than just seeing ones above you.
|
No, there is no interaction whatsoever allowed. I PMed the answer to you, BottleAbuser
|
If we assume the axiom of choice, then I'm assuming we should be considering equivalence classes of the sequences of black/white hats?
|
Yeah ok shooting_speils you've basically got it... There isn't much left to the problem after all the hints.
But anyways I just thought the result was really cool
|
1. if the chances of living for each prisoner is 50% then there is a N/2 number of prisoners that will make it out alive.
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 >.<
|
|
There are tons of measure 0 sets with the same cardinality as the total space, so that doesn't work Rev0lution
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
|
Now am I to understand that the method that the judge uses for choosing what color hat that a prisoner gets is arbitrary, and possibly adversarial?
|
|
ok... to my interpretation... 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."
|
United Arab Emirates5090 Posts
i have no idea whatsoever as to how to solve the hat problem
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
|
Inifinities can have different "sizes," so saying "an infinite number of prisoners survive" doesn't mean most of them do. Take for example the set of all real numbers and the set of all integers. They're both have an infinite number of elements, but the set of integers is a proper subset of the set of all real numbers.
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).
|
actually what i wrote above simplified some stuff but, at the very very minimum, it must be assumed that the sequencing of the hats follow a function, and the function is not completely random.
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
|
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.
|
Looks like we have proof that there is no solution (unless I misunderstood the constraints of the problem).
|
Canada7170 Posts
lol I reallllly want to post the Monty Hall problem again just to see who doesn't get it by now.
|
I don't understand how there can be an answer either. In most other problems of this type of nature, there's some way of conveying information between the people in question, often based on time or order, but I can't seem to figure out any such thing here, since the prisoners simultaneously write down their guesses. I think I give up on this one, barring some kind of hint or clarification.
edit: If you guys want to see some more problems, check my blog. There's one medium level problem and one hard problem.
|
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.
|
United Arab Emirates5090 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
|
just to elaborate why a function is not solvable.
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.
|
Ok you guys.... the wikipedia article gives the same solution I did. "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"
|
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.
|
muri,
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.
|
United Arab Emirates5090 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. 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.
|
United Arab Emirates5090 Posts
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.
|
United Arab Emirates5090 Posts
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.
|
ok dybydx... there are infinitely many classes, but the moment a prisoner sees the hats in front of him he immediately knows what class he is in. Each prisoner knows the class that all the prisoners are in. Each prisoner knows the eventual behavior of the sequence the judge has chosen.
|
ok so ... 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.
|
Is it worded wrong or osmething? it says
Mike gets told the date John gets told the month
Does mike now its 9/1 and john knows it's 9/?
|
Did it mean john knows the month, mike knows the day, now figure out the date from there statements (month + day = date)
|
Ok: 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?
|
Hah! I think I get it.
+ 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.
|
Ok bottleabuser you completely get it!
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.
|
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
|
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??
|
monoxide,
yes. until the sequence merge, you have no way of telling. so it becomes luck.
|
|
|
|
|