|
||||||||||
|
Title: red eyes brown eyes Post by jessie theo on Mar 3rd, 2005, 6:37pm There is an island of monks where everyone has either brown eyes or red eyes. Monks who have red eyes are cursed, and are supposed to commit suicide at midnight. However, no one ever talks about what color eyes they have, because the monks have a vow of silence. Also, there are no reflective surfaces on the whole island. Thus, no one knows their own eye color; they can only see the eye colors of other people, and not say anything about them. Life goes on, with brown-eyed monks and red-eyed monks living happily together in peace, and no one ever committing suicide. Then one day a tourist visits the island monastery, and, not knowing that he's not supposed to talk about eyes, he states the observation "At least one of you has red eyes." Having acquired this new information, something dramatic happens among the monks. What happens? Hint: First consider the case where there are only a few monks on the island, some with brown and some with red. Work through the logic and find out what happens over time. Then generalize for the case of M monks on the island, N of which have red eyes. --------------------------------------------------------------------------------plz help me!!!!!!!!!! ::) ::) ::) |
||||||||||
|
Title: Re: red eyes brown eyes Post by Yuniko on Mar 3rd, 2005, 9:06pm I am not complete sure but I think after N days, all the red-eyes monks commit suicide at midnight. |
||||||||||
|
Title: Re: red eyes brown eyes Post by Three Hands on Mar 4th, 2005, 5:20am Pretty much: If N=0, all the monks will look around, see that no-one else has red eyes, assume they have, and so commit suicide. If N=1, the monk with red eyes will see no-one else with red eyes, and so commit suicide. All the other monks will see one monk with red eyes, and so assume that he's the only one who needs to commit suicide If N=2, each of the monks with red eyes will see one other person with red eyes, and so assume that it is the other monk who needs to commit suicide. Then, the next day, when they see the other monk is still alive, figure out that there must be 2 monks with red eyes, realise they are the other monk, and so commit suicide. And so on. Hence, with the exception of N=0, N monks commit suicide after N days. (P.S. - a quick search for "Red Eye Monks" finds some threads already discussing this) |
||||||||||
|
Title: Re: red eyes brown eyes Post by towr on Mar 4th, 2005, 5:35am If the monks have any common sense they won't believe 'there is at least one among them with red eyes' unless they can see one. Otherwise they will all needless kill themselves if it's a lie (as shown in the previous post). This will have more consequences though.. |
||||||||||
|
Title: Re: red eyes brown eyes Post by rmsgrey on Mar 4th, 2005, 6:44am on 03/04/05 at 05:35:43, towr wrote:
It certainly does! If the monks aren't confident that a (hypothetical) single monk with red eyes would commit suicide - not seeing any red eyed monks so not knowing that the statement was true, then they wouldn't expect a (hypothetical) lone pair of red-eyed monks to suicide on the second night since that pair would each not expect the other to suicide on the first night if they were the only red-eyed monk, so be unable to draw firm conclusions about their own eye colour... The same reasoning ripples up through the numbers until the actual group of N red-eyed monks each don't expect the other N-1 to suicide because they don't expect them to expect the (hypothetical) N-2 monks to suicide because... Interestingly, if only one monk believes that all the monks are gullible and believe each other to be gullible (and believe each other to believe each other to be gullible and...), something slightly spooky still happens. |
||||||||||
|
Title: Re: red eyes brown eyes Post by Icarus on Mar 4th, 2005, 3:04pm One of the great classic threads (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1027806383;start=0) of the Medium forum (the puzzle itself is on the Medium riddles page, so you won't see it stated in the thread). Those who are new to the problem may want to also consider these additional questions that Chronos posed. In these questions, it is assumed that all the monks can be depended on to "do the right thing". (1) Suppose that instead of saying "There is at least one red-eyed monk", the tourist instead makes the statement "Brother Bob has red eyes". What happens? Of course, Brother Bob goes and kills himself, and everyone else is safe. But the statement "Brother Bob has red eyes" implies the statement "There is at least one red-eyed monk". So the tourist is actually giving more information in this example, and yet most of the monks (all but the unfortunate Br. Bob) gain less information! How is this possible? (2) The tourist announces at breakfast that there is at least one REM. But later in the day, he learns of the peculiar customs of these monks, and realizes what he's set in motion. Guilt-stricken, he addresses the monks again at supper that night, and tells them all "Monks, I realize now the significance of what I told you this morning. To reduce the number of inevitable deaths, I now tell you that Brother Bob has red eyes". What happens? Explain. (3) The tourist doesn't learn about the monks' habits (pun not intended) until day M, where M < N. What should the tourist say? (4) What happens if, the evening of the first day, the tourist says "I was lying this morning"? Alternately, what if he says "I'm unreliable"? ----------------------------------------- Jeremy also posed the interesting question of what happens if some of the monks are color-blind, a secret each has kept from all others. This one was never fully answered in the other thread. Perhaps this is the same as rmsgrey's scenario, but I'm not completely sure what he means by "gullible", or "believes others are gullible" vs "doesn't believe others are gullible". |
||||||||||
|
Title: Re: red eyes brown eyes Post by towr on Mar 4th, 2005, 3:07pm on 03/04/05 at 06:44:03, rmsgrey wrote:
If there are at least two red-eyes, then everyone knows that the statement is true. Because everyone can see at least one. Quote:
Heh.. what if all the monks believed the red-eyes are gullible and believe eachother to be gullible <etc> :P |
||||||||||
|
Title: Re: red eyes brown eyes Post by towr on Mar 4th, 2005, 3:16pm on 03/04/05 at 15:04:12, Icarus wrote:
Quote:
Quote:
Quote:
But I've never been quite able to wrap my mind around this problem. |
||||||||||
|
Title: Re: red eyes brown eyes Post by rmsgrey on Mar 5th, 2005, 7:05am //(Icarus) :-[:-[I have accidently destroyed this post by rmsgrey - I hit the modify button when I thought I was hitting the quote button, and had deleted the entire post except the part I was quoting. Unfortunately, the same moderator powers that allowed me to do this heinous act, do not extend to allowing me to fix it. The only portion that remains is the one I was quoting: //rmsgrey While the wording may not be exactly the same, my powers of recollection are good enough (I hope) to recreate the substance... on 03/04/05 at 15:07:36, towr wrote:
Let's look at some scenarios: In the first scenario, all the unnamed monks have brown eyes, I have red eyes (but don't know it) and you (towr) don't know what colour eyes you have. When the tourist drops his little bombshell, you know he's telling the truth, but the only way I could know he was telling the truth would be if you had red eyes - so when I turn up to breakfast the next morning, you have to guess whether it's because I saw you had red eyes, or because I didn't trust the tourist. Next scenario: Icarus is there too, and also has red eyes. On the morning of the second day, when Icarus and I both show up to breakfast, you again are faced with two possibilities: If you have red eyes, then each of us was hoping the other two would suicide overnight. If you have brown eyes, then Icarus and I were both faced with the same dilemma as you were in the previous scenario - and, given that neither of us suicided, each decided (incorrectly) that the other didn't believe the tourist. Essentially, the whole structure of deduction rests on being able to assume that a lone red-eyed monk will commit suicide the first night. If that isn't true, then there's insufficient reason for two red-eyed monks to suicide the second night, or three the third, etc. The entire inductive proof fails for lack of a base case. ************************************************ I think there was some more content here, but I've decided to skip it since it's largely redundant given: Some follow-up questions: Definitions: *Gullible - will suicide on the first night if no other monks have red eyes. *Suspicious - not gullible. *Public knowledge - something that all monks know, all monks know that all monks know, all monks know that all monks know that all monks know, etc. An example of public knowledge is the fact of the tourist's statement - everyone knows that the tourist said "at least one monk has red eyes" and that everyone else knows, and ... Assuming that which monks are gullible, and which suspicious, what happens if: 5) No monk has red eyes? (Hint: this is not a trick question) 6) All red-eyed monks are gullible? [edit] Having actually thought about the answers properly: 7a) There is exactly one suspicious red-eyed monk and exactly one gullible red-eyed monk? [/edit] 8) All red-eyed monks are suspicious, and all brown-eyed monks are gullible? [e2] Last change, I promise! 8a) There is exactly one gullible red-eyed monk and at least one suspicious red-eyed monk? [/e2] 9) All monks are suspicious? As close as I can recall, rmsgrey provided a nice explanation as to why the Tourist's 2nd comment in Chronos' question (4) will stop the suicides even though everyone knows the tourist is lying in it and told the truth originally. rmsgrey also provided the definition of "gullible" I asked for above, and posed 4 more questions about gullible vs suspicious monks that I cannot fully recall. I pray he will forgive me for my ham-handed mistake, and post again with what I have destroyed. :-[ :-[ // There were several questions I considered posting originally, and I can't remember which four (apart from the first) I eventually posted. Hence I've posted 5 of them this time around |
||||||||||
|
Title: Re: red eyes brown eyes Post by Icarus on Mar 5th, 2005, 8:30pm Before diving too deeply into discussions of variations, I think it might be wise to provide an explanation to new readers as to why in the original puzzle, assuming all the monks are "gullible", as rmsgrey calls them, that if there are N red-eyed monks, they will kill themselves on the Nth night after the tourist's remark. Jonathan_the_Red posted some very good explanations of it in the other thread, and I will try to recreate the logic here: Assume 1 REM (red-eyed-monk). Since everyone else has brown-eyes, he will realize immediately that he has red eyes, and kill himself the first night. Assume 2 REMs On the day of the remark, they will each see two possibilities: 1 - The other guy alone is a REM, and will kill himself tonight, as above, or 2 - We are both REMs, in which case he is watching to see if I kill myself tonight. Because the two situations exist, they both hold off, and do not kill themselves the first night. On the second day, they realize that case 1 does not hold - the other guy didn't kill himself. So it must be case 2 - we are both REMs! So they kill themselves the 2nd nights. Assume 3 REMs Each REM sees 2 other REMs, so he knows that there are either 2 REMs (he is a BEM), or else there are 3 REMs including himself. So, either 1 - There are only 2 REMs, and as described above, they will kill themselves on the 2nd night, or 2 - There are 3 REMs. So each must wait until the 2nd night to see if the others kill themselves. When they wake up on the 3rd day to find all are still alive, they realize that option 1 is false, and kill themselves on the 3rd night. This goes on inductively: if there are 4 REMs, they each hope that there are only the 3 they see, and must wait until day 4 to see if the others have killed themselves on the 3rd night. When all turn up alive for breakfast, they know that they must be a REM as well, and each kills himself on the 4th night. If there are 5 REMS, ... etc. |
||||||||||
|
Title: Re: red eyes brown eyes Post by rmsgrey on Mar 6th, 2005, 8:41pm on 03/04/05 at 15:04:12, Icarus wrote:
I'm not new to the problem, but I might as well give my answers anyway :) Quote:
In the normal course of events, each monk gains information about the other monks' knowledge - On the Nth day, the red-eyed monks all discover that the other red-eyed monks didn't have enough information to deduce their own eye colour, and on the N+1th day, the brown-eyed monks discover that the red-eyed monks did have enugh information to deduce their eye colour - it's the survival or otherwise of other monks on one given night that tells a given monk what colour eyes he has. In this situation, brother Bob knows his eye colour without needing to know anyone else's, so the monks get no information from his suicide. By giving brother Bob more information than necessary, the tourist prevents anyone else from deducing anything about what else Bob already knew. Quote:
Bob suicides that night. The other red-eyed monks suicide one night earlier than they normally would. Since the tourist claimed that telling them brother Bob had red eyes would reduce the number of deaths, they can deduce that a) more than just Bob would have died if he'd said nothing, so Bob can't have been the only monk with red-eyes, and b) the tourist isn't very good at logic. Since Bob no longer counts towards the induction, there is effectively one red-eyed monk fewer Quote:
Publicly name at least M (if the day of his original statement is day 1) or M+1 (if day 1 is the next day) monks with red eyes. They then kill themselves at midnight, and kill the induction on how many red-eyed monks there are. You have to name at least as many as would be due to die that night if they were the only red-eyed monks as otherwise it would be obvious that there were more (otherwise they'd have suicided earlier) and the induction will continue to its messy conclusion. Quote:
Then the induction fails to get off the ground. A lone red-eyed monk would look around, see nothing but brown eyes, and decide that the unreliable tourist's random utterances have given him no new information and not bother to suicide, so a pair of red-eyedmonks would be unable to deduce anything when neither suicides, etc. |
||||||||||
|
Title: Re: red eyes brown eyes Post by rmsgrey on Mar 6th, 2005, 8:41pm Quote:
There is the question of whether each colour-blind monk believes that he must be the only colour-blind monk or each believes that there may be others (and what they believe about the beliefs of hypothetical others). Suppose colour-blind monks do believe themselves to be unique, and Bob is one of them. Then he's waiting for some number of his fellows to suicide - if they're all brown eyed, then Bob expects all of them would suicide on the first night if he has brown eyes, or the second if his are red. Otherwise, if S monks suicide on the Nth night, he hopes that S=N, meaning he has brown eyes, but fears that S=N-1, meaning he has red eyes. On the Mth night, where M is the number of monks, if no-one's suicided yet, Bob'll figure that everyone (including him) has red eyes, and suicide. Any other pattern of suicides contradicts his assumptions, so he (I assume) deduces that he's not the only colour-blind monk - giving two possibilities: either there were N red-eyed monks, S of whom just suicided, which would only be grounds for Bob to suicide if N=M, in which case he would have already; or there are N-1 red-eyed monks, all of whom are colour-blind, and S normally-sighted brown-eyed monks just suicided - only grounds for Bob to suicide if S+N-1=M, ie only the N-1 red-eyed monks survived. Since the first possibility is never grounds for suicide and can only be ruled out when S>N, Bob won't commit suicide unless S>N and S+N-1=M (or S=M+1-N with 2N<S+N=M+1) So Bob suicides the next night when: N-1 monks suicide on the Nth night; or no-one has suicided after the (M-1)th night; or M+1-N monks suicide on the Nth night with 2N<M+1 (including M-1 on the 2nd night). These correspond to: at least two red-eyed monks, exactly one of whom colour blind, when the normally-sighted red-eyed monks suicide on the usual schedule, then all the colour-blind monks suicide the next night; all the monks have red eyes or all the monks are colour-blind, in which cases they all suicide on the Mth night; all and only the N-1 red-eyed monks are colour-blind, and outnumbered by the brown-eyed monks by at least two monks, in which case all the brown-eyed monks with their normal vision suicide on the Nth night, and the red-eyed colour-blind monks suicide on the following night. If the colour-blind monk Chuck doesn't assume himself the only colour-blind monk (and assumes any other colour-blind monks assume likewise), then he only suicides when either M+1-N monks suicide on the Nth night with 2N<M+1, or at least one monk suicides on the Mth night. In the first case, all and only the red-eyed monks are colour-blind, and outnumbered by the normally-sighted brown-eyed monks by at least 2 monks, and everyone dies over two nights - first the brown-eyed monks, then the rest. In the second case, all the monks have red eyes, and at least one have normal vision, or the one monk with normal vision is the one monk with brown eyes or Bob is one of them - those with normal vision suicide, along with Bob and his fellows, on the Mth night, while Chuck's lot suicide on the M+1th night. If Dave the colour-blind monk assumes that there may be others but that some may be like Bob, then he only suicides if M+1-N monks suicide on the Nth night with 2N<M+1 - when red-eyes are equivalent to colour-blindness (of some kind). So, in summary: If all and only red-eyed monks are colour-blind, and in the minority by at least two monks, then all the monks die over two nights - brown-eyed first. If all the monks have red eyes, or all are colour-blind, or all but one are both and he is neither, then any normals and any Bob-types will suicide on day M. If at least one monk suicides, then any Chuck-types suicide on day M+1. If there are at least two red-eyed monks, exactly one of whom is colour-blind, then the red-eyed monks with normal vision suicide on schedule, followed the next day by any Bob-types. If all the red-eyed monks are colour-blind, at least one monk has normal vision, and either at least one brown-eyed monk is colour blind, or the red-eyedmonks are not in the minority by at least two, then the monks with normal vision (and brown eyes) all suicide the day after the red-eyed monks normally would have. In the case where there are the same number of normals as red-eyed monks, any Bob-types will suicide the following day, each believing himself to be the one red-eyed monk missing from the body-count. If there's at least one red-eyed normal and at least two red-eyed colour-blind monks, then the red-eyed normals will suicide as usual, but no-one else will. If all red-eyed monks are normal, then they suicide as usual. This, and the case where everyone has red eyes and the only colour-blind Monks are Bob-types are the only cases where the suicides align perfectly with the usual case. |
||||||||||
|
Title: Re: red eyes brown eyes Post by Icarus on Mar 7th, 2005, 4:46pm on 03/06/05 at 20:41:04, rmsgrey wrote:
Pretty much. I see it this way: The tourist does impart information to all monks immediately, but the information he imparts is not the statement he actually says. That statement was already known to all monks (with one exception, and then only in the case of a single REM). The information actually obtained by the monks from the original "there is a REM" remark is "if there were a single REM, he would now know it". Now consider if the tourist says "Bob is a REM". For Bob, this is more information now. For everyone else, the information content is not comparable to that obtained before. They learn "Bob knows he is a REM", whereas before they learned "an arbitrary lone REM would know it". The original gives information applicable to any REM, but requires them to be alone. The new version applies only to Bob, but holds whether there are other REMs or not. Since neither statement implies the other, it is not surprising that their results should be different as well. For (2-4) you are also correct. But what about this alternative for (3): What happens if the tourist declares "I was lying" on Day M? (M > 1, and day 1 being the day of the remark.) ------------------ I'm not up to tackling your analysis of the colorblind situation tonight, nor your own gullible vs suspicious questions (thanks for restoring them). Maybe tomorrow. :P |
||||||||||
|
Title: Re: red eyes brown eyes Post by rmsgrey on Mar 8th, 2005, 8:07am on 03/07/05 at 16:46:14, Icarus wrote:
On the morning of day 2, it's already too late to say you're lying - from the lack of suicides overnight, it's public knowledge that there are at least 2 REMs so if there were exactly 2, they'd still suicide - and the information keeps growing. Quote:
It turns out I wasn't up to tackling my own gullible vs suspicious questions - having spotted that the answer to one of them as phrased was more messy than interesting, I've replaced it. Hopefully the colour-blindness is OK - it was past 4am by the time I finished writing it up and whole chunks got re-written as I came up with clearer approaches... |
||||||||||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |