| Forum Index > General Forum |
|
RzzE
Germany20 Posts
On January 23 2008 05:34 LossLeader wrote: 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. | ||
|
BlackJack
United States10574 Posts
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. | ||
|
Muirhead
United States557 Posts
| ||
|
LTT
Shakuras1095 Posts
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. | ||
|
toopham
United States551 Posts
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. | ||
|
dybydx
Canada1764 Posts
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 :< | ||
|
Muirhead
United States557 Posts
On January 23 2008 10:45 dybydx wrote: 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 | ||
|
BottleAbuser
Korea (South)1888 Posts
+ 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. | ||
|
BottleAbuser
Korea (South)1888 Posts
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. | ||
|
dybydx
Canada1764 Posts
i dont think ur solution is correct... on that pi^e thing http://www.google.com/search?hl=en&safe=off&client=firefox-a&rls=org.mozilla:en-US:official&hs=WHV&q=pi^e - e^pi&btnG=Search i think muri has to explain his questions a lil more. we are all making some assumptions only to be denied the assumption can not be made. we need to know what is allowed and what isnt. | ||
|
BottleAbuser
Korea (South)1888 Posts
On January 23 2008 11:23 dybydx wrote: Murihead, i dont think ur solution is correct... on that pi^e thing http://www.google.com/search?hl=en&safe=off&client=firefox-a&rls=org.mozilla:en-US:official&hs=WHV&q=pi^e - e^pi&btnG=Search 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. | ||
NonY
8751 Posts
| ||
|
dybydx
Canada1764 Posts
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 | ||
|
Muirhead
United States557 Posts
 .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. | ||
|
Rev0lution
United States1805 Posts
On January 23 2008 06:01 BlackJack wrote: + 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... | ||
|
dybydx
Canada1764 Posts
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 | ||
|
BottleAbuser
Korea (South)1888 Posts
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. | ||
|
dybydx
Canada1764 Posts
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. | ||
|
Muirhead
United States557 Posts
 | ||
|
ShOoTiNg_SpElLs
Korea (South)690 Posts
| ||
| ||
StarCraft 2 StarCraft: Brood War Dota 2 League of Legends Counter-Strike Other Games |
|
IntoTheTV X SOOP
PiGosaur Cup
The PondCast
Kung Fu Cup
IntoTheTV X SOOP
FEL
Patches Events
FEL
Sparkling Tuna Cup
Replay Cast
[ Show More ] |
|
|
EPT
