md65536 Posted February 9, 2012 Share Posted February 9, 2012 I think I see how it works, now. This is one of those problems that I can't stop thinking about. More analysis: Say there are 100 blues and I'm one, and of course I don't know it. I can try assuming I'm blue, and never derive a contradiction. I can try assuming I'm not blue, and not derive a contradiction till after the 99th day. If I assume I'm not blue, I assume that there are 99 blues. Let A be me. Let B be the set of blues that I see. Like me, any of B can assume they're not blue, and they'll think there are 98 blues (this is an incorrect part of my assumption, but I won't know it's incorrect until I realize that B hasn't left when I thought they would). Let C be the set of blues that is seen by some member of B. Again, like A and B, I can assume that B can assume that C assumes there are only 97 blues! *I* know that C sees at least 98 blues, and B knows it too!, but I don't know that B knows it! So A can assume that B doesn't know any better, and that B assumes that C doesn't know any better, and that B assumes that C assumes that D doesn't know any better and so on. The tricky part is that I know (or assume) that B's assumptions are wrong, but I don't know that B never even makes that assumption because my assumption was wrong! Does that make sense? So the key piece of information that the guru or visitor gives is this: I know that no one can assume that there are 0 blue (already known), and that no one can assume that anyone else can assume that there are 0 blue (already deducible), and that no one can assume that anyone else can assume that anyone else can assume there are 0 blue, etc... The 100th such statement is actually new information. So I never assume that anyone sees less than 98, but I can incorrectly assume that someone else incorrectly assumes it! And I never assume that B (the only one which I assume to be incorrect) assumes anyone sees say only 1 blue, but I *do* assume that B incorrectly assumes that someone else incorrectly assumes that someone else incorrectly assumes that someone else incorrectly assumes that someone else ... etc ... does. This is probably my favorite logic puzzle now too. Not a lot of mental math to do (the inductive solution is pretty light), but definitely some ideas to twist your brain up in understanding it. Link to comment Share on other sites More sharing options...
imatfaal Posted February 9, 2012 Share Posted February 9, 2012 This is one of those problems that I can't stop thinking about. More analysis: /spoiler snipped This is probably my favorite logic puzzle now too. Not a lot of mental math to do (the inductive solution is pretty light), but definitely some ideas to twist your brain up in understanding it. Great isn't it! I will maintain it works - but I also know, through bitter experience, that I am incapable of explaining it to others. Link to comment Share on other sites More sharing options...
John Cuthber Posted February 9, 2012 Share Posted February 9, 2012 I still think the traveller brings no new information (of any order) to the island. Because, as far as I can see, the logic works perfectly well if one of the islanders dreams that a traveller arrives and makes his dreadful pronouncement. A dream clearly doesn't add new information. I think the flaw in using inductive logic is that you cannot put the islanders in order. How do you decide who dies on the first day? Who dies on the second and third and so on. Inductive logic works for things that form a clear sequence, but people don't. Link to comment Share on other sites More sharing options...
md65536 Posted February 9, 2012 Share Posted February 9, 2012 I still think the traveller brings no new information (of any order) to the island. Because, as far as I can see, the logic works perfectly well if one of the islanders dreams that a traveller arrives and makes his dreadful pronouncement. A dream clearly doesn't add new information. I think the flaw in using inductive logic is that you cannot put the islanders in order. How do you decide who dies on the first day? Who dies on the second and third and so on. Inductive logic works for things that form a clear sequence, but people don't. No, the "dream information" is not the same unless the dreamer knows that everyone else also knows the dream information, which they don't. The people can be ordered by, for example: Choose any one blue, let them choose any blue, etc. Obviously the order doesn't matter, and it will work the same for each blue I may choose, and each that each of those may choose, etc. No one dies on the first day. Say I see 99 blues. I can make an assumption that I'm not blue. If I'm brown, I'll learn by the 99th day that I'm right, when the blue islanders all leave/die. If I'm blue, I'll learn the next day, after realizing no one left as I assumed they would. If I'm brown, I know that the blues will leave on day 99 because they'll have realized after the 98th day that their assumption that there were 98 blues, is wrong. Link to comment Share on other sites More sharing options...
John Cuthber Posted February 10, 2012 Share Posted February 10, 2012 "No, the "dream information" is not the same unless the dreamer knows that everyone else also knows the dream information, which they don't." The others know exactly the same as the dreamer. That's my point. What if everyone had the same dream on the same night and didn't realise it was a dream? The traveller doesn't say anything that the islanders couldn't predict that he might say. Also, there still needs to be some external factor that puts the islanders in order. Otherwise you have to explain who dies first, who second etc? How does the first suicide know that he has to be first? What stops everyone thinking "I should be first" or, later on "I should have been first"? If it follows from strict logic that they all die then that same logic must say who dies third. Who is it? Fundamentally, this is a symmetry breaking problem. As written, the puzzle is fully symmetrical with respect to an exchange of any blues (or any browns) So any solution must also be symmetrical in that way. But the given solution is not symmetrical. If I swap corpse 1 with corpse 3 it doesn't work properly because someone died before there was a reason for them to do so. So the given solution must be incorrect. Link to comment Share on other sites More sharing options...
md65536 Posted February 10, 2012 Share Posted February 10, 2012 (edited) "No, the "dream information" is not the same unless the dreamer knows that everyone else also knows the dream information, which they don't." The others know exactly the same as the dreamer. That's my point. What if everyone had the same dream on the same night and didn't realise it was a dream? The traveller doesn't say anything that the islanders couldn't predict that he might say. Also, there still needs to be some external factor that puts the islanders in order. Otherwise you have to explain who dies first, who second etc? How does the first suicide know that he has to be first? What stops everyone thinking "I should be first" or, later on "I should have been first"? If it follows from strict logic that they all die then that same logic must say who dies third. Who is it? Fundamentally, this is a symmetry breaking problem. As written, the puzzle is fully symmetrical with respect to an exchange of any blues (or any browns) So any solution must also be symmetrical in that way. But the given solution is not symmetrical. If I swap corpse 1 with corpse 3 it doesn't work properly because someone died before there was a reason for them to do so. So the given solution must be incorrect. If the islanders are acting on dream information then they're not acting on perfect logic. The solution requires that every blue acts with flawless logic AND, CRUCIALLY, also assumes that every other blue will act with flawless logic. Edit: Imagine a case where there are 1 or 2 people with blue eyes and you dream that a guru says "someone has blue eyes". Do you know if you have blue eyes? If there are 5 blues and I'm one of them, I can assume that [there are only 4 blues which can assume that (there are 3 blues which assume that there are 2 blues which assume there is 1 blue which assumes there might be no blues)]. If someone tells everyone that there is at least 1 blue, then I know that MY assumption is wrong (though I already knew that everyone else's assumptions listed here were wrong), and that no one can assume that anyone can assume that anyone can assume that anyone can assume that there might be no blues. If I'm brown, I'll find out that my assumption was right when the 4 blues derive their contradiction on the 4th day. Otherwise if the blues don't leave then, I'll realize my assumption (including that I'm not blue) is wrong, and I'll leave the next day. No one dies first, second, etc. All the blues are symmetrical. They all realize they're blue on the same day. The solution is correct. The weird part is, I'll never assume that anyone actually assumes that there are no blue-eyed islanders. But I can assume that someone else assumes that [long list of assumptions here] that someone else can! And eventually they'll realize that their assumption is wrong. If they don't, then I'll realize my assumption is wrong. Another way to look at it is this: Say I'm one of 100 blue. I see 99 blue. I know there are 99 or 100 blue. I know the browns see either 99 or 100 blue. But the browns may think they're blue. The browns may think there are 101 blue. I know the blues see either 98 or 99 blue. The blues may think there are 98 blue! If there are 99 blue (there aren't, but I don't know that yet), then the blues may, like me, think that the other blues might see only 97 blue. I know that assumption's wrong, but if my assumption's right (it's not), then the other blues will assume that the blues that they see will think that the blues that they see will see only 96 blue, and so on. I know that no one sees only 96, and I know that the blues I see know that no one sees 96, but I don't know whether the blues that I see know that no one else knows whether anyone sees 96. And so forth. Yet another way to state this: I know that nothing's going to happen until day 99 or day 100, but I don't know if perhaps the blues I see think something will happen on day 98 or 99. If I'm a blue, then all the other blues are dealing with the exact same logic problem as I am. But if I'm brown, then all the blues I see are dealing with the problem less one blue. I know this, and I know that the blues are thinking the same way as me. So they may think that the other blues are dealing with one less blue. And so forth. ------------ Here's a variation. Same rules as the original. 100 people with blue eyes. The guru/visitor says to the crowd "Someone on this island has blue eyes." Then Goofuth enters the room and says (truthfully), "What was that??? I was in the bathroom, I missed that!" You look at Goofuth's eyes, and are relieved to know that no one will have to leave the island. What color are Goofuth's eyes? (Not sure if this one works as I think it does...) Edited February 10, 2012 by md65536 Link to comment Share on other sites More sharing options...
John Cuthber Posted February 11, 2012 Share Posted February 11, 2012 "If the islanders are acting on dream information then they're not acting on perfect logic." No, because perfect logic would permit them to grasp how they would react to dream information. " Imagine a case where there are 1 or 2 people with blue eyes " then it's a different question. " assume there is 1 blue which assumes there might be no blues" Bollocks. they can see blues, so they know there are not "no people with blue eyes". At the outset, where there are 100 blues, it is clearly absurd to assume that there is just 1. If there were just 2 islanders you would have a point, but there are many more than 2. "No one dies first" Oh yes they do. Anyway I'm bored so please answer the question. Who dies first? How do they decide it's "their turn"? This is meant to be a logic puzzle so lets see the logic behind the purported outcome. How does the first guy to die know that he shouldn't be the forth guy? Link to comment Share on other sites More sharing options...
md65536 Posted February 11, 2012 Share Posted February 11, 2012 (edited) No, because perfect logic would permit them to grasp how they would react to dream information. If they all knew that everyone shared the same dream, then the logic would also work. All the blues would leave/die on day 100. Edit: AND only if they all knew that everyone else knew that everyone shared the same dream. At the outset, where there are 100 blues, it is clearly absurd to assume that there is just 1. Yes! And I know that. And you know that. But I don't know whether you know that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that every other knows that. Roughly speaking (I've underestimated the number of blues here). "No one dies first" Oh yes they do. Anyway I'm bored so please answer the question. Who dies first? I said no one dies first. You're saying someone dies first. So maybe you tell me. Don't worry, you'll get this eventually. This is meant to be a logic puzzle so lets see the logic behind the purported outcome.How does the first guy to die know that he shouldn't be the forth guy? It doesn't matter. He doesn't know the order, he doesn't care. He can make the same assumption about any of the blues that he sees, an assumption that will prove to be false if that blue (i.e. any blue, i.e. all 99 blues that he sees) are still around after the 99th day. All 100 go on day 100. The ship leaving holds all 100. The guillotine accommodates all 100 at once. They can all go simultaneously. If they happen to go in some order, the order doesn't matter. Edit: Perhaps there is a misconception that the blues suicide when they see others suicide. That's not the case. They suicide because they see the 99th day go by where they expected (or at least hoped for) all the blues to kill themselves. They know their eyes are blue because of the lack of anyone killing themselves first. Edited February 11, 2012 by md65536 Link to comment Share on other sites More sharing options...
John Cuthber Posted February 13, 2012 Share Posted February 13, 2012 (edited) OK, a couple of points. 1 I misread the "given" answer so ignore what I said about who dies first. Secondly, I'm still not sure that the traveller gives them any information. How about this version. The tribe, their island and the taboo are all the same as before. I'm a thief and I have heard that the tribe has gold and I want to steal it. The tribe has another new policy that makes it difficult for me. Any "newcomer" is accompanied by a minder while he is on the island. the minder's job is to discourage breaches of the taboo. It's an easy job- if you mention eye colour he cuts your head off with an axe. No court- no appeal- no exception. But I still want the gold. So I dress up as an anthropologist and I visit the island. I talk to them about dull safe stuff like farming practice for a while. At the end of the day I get some whisky out of my bag and pass it round. Over a few drinks I tell them about another tribe I studied in the past. This tribe were foresters. They lived in an isolated forest fed by a spring in the middle of the desert. There was one odd thing about them; some of them had a red birth-make in the middle of their back. This didn't matter much because their local lore forbade any mention of birthmarks. Also, anyone who found out that they had a birth mark had to kill themselves. So did anyone who found out for sure that they did not have such a mark. I then explained that I'm not studying the foresters any more. They died because one day one of their number got a bit depressed and left a note on the local notcie board. It said "I can see that some people here have birthmarks". Then I went back to my tent and, in the dead of night, I ran away and hid for a hundred days or so. I went back and took the gold without any difficulty because the Islanders were all dead. Here's why. In the morning they sobered up. They realised that their situation was practically the same as the foresters (after all- they do have perfect logic once they are sober). They realised that there was already enough information on the Island to lead to their deaths. The notice board had told the foresters that one of them could see some birthmarks. But the notice board didn't offer any new information- it was written by one of them and it said something which they already knew was not just true, but obvious. Having perfect logic the islanders realised that if they knew that someone knew about blue eyes then they were doomed. They didn't need to know who it was or how they came to this knowledge. It didn't matter if it was a traveller or an islander. As soon as they all knew that someone knew, they had about 14 weeks left. But they also knew that 1 they could see plenty of blue eyes. and 2 Others round them could see plenty of blue eyes. So , with perfect logic, they deduced that everyone on the island was already in the same position as the traveller. They all knew it so nobody had to say anything. They could, with their perfect logic, deduce it. So they died shortly afterwards. But hang on. Nobody told them anything. I (sneaky bastard that I am) made sure I never mentioned eye colour- because my minder would have killed me. I didn't provide them with any more information. Apart from anything else- the foresters were not real. I made them up just so I could get the gold. If I can work that out- motivated by greed, they could work it out too, because they have perfect logic. They would have no choice but to work it out. They would have worked it out before I got there. (after all, I brought them no new information) They would have died out before I or the traveller arrived. Sorry it's a bit long winded. The bit about the whisky is just a ruse to stop them killing me immediately. It's not vital to the plot as long as the only thing on the island with a death penalty is being an outsider who talks about eye colour. It also wouldn't matter if they killed me, by then it's too late, but it spoils my fun. Have I missed something or would the islanders automatically die out 100 days or so after their "society" was set up as described in the puzzle? Edited February 13, 2012 by John Cuthber Link to comment Share on other sites More sharing options...
md65536 Posted February 14, 2012 Share Posted February 14, 2012 (edited) Having perfect logic the islanders realised that if they knew that someone knew about blue eyes then they were doomed. They didn't need to know who it was or how they came to this knowledge. It didn't matter if it was a traveller or an islander. Edit: By the way the first statement is incorrect. It's not even true that they'd be doomed if they knew that everyone knew about someone with blue eyes. They'd be doomed if they knew that everyone knew that everyone knew that someone had blue eyes. --- No wait, I don't think that's right. I think they're only doomed if they know that a long list of assumptions about assumptions, about 100 long, is wrong. Okay so put yourself in the position of someone on the island. You know the information about the birthmark and that everyone else knows it and you know everyone has perfect logic. Do you (or will you) know if your eyes are blue or not? There is a proof by induction on the XKCD link I think, that proves the answer to the original version of the problem is correct. You can't disprove it by showing the absurdity of an absurd variation on it. You'd have to at the very least show a mistake in the induction proof. If you do an induction on the problem size of your variation, it's not going to work like it does for the original problem. Suppose there was only one person with blue eyes. Do you think she would know she has blue eyes, after being told about birthmarks? If it doesn't work for 1 person, it's not going to work for 100. In the original problem, you can do an easy induction on the problem size, i.e. the number of blue-eyed people, but you don't accept that because it doesn't have any intuitive connection to the case where there are 100 blue-eyeds. But it doesn't matter because it works whether or not you understand it and whether or not it makes intuitive sense. Unfortunately for the islanders they all have perfect logic. I think you can also do a much harder induction, without ever considering a case where there are less than 100 blue, on the number of blue eyed people might be assumed to be seen by the other blue eyed people. I could try to do this if you want. I was once told that you don't truly understand something until you can explain it. I believe I understand this problem intuitively now, but it's so twisted that my grasp is frail. I think I'll try an intuitive proof sometime... (But if I fail it only shows that I don't intuitively understand the solution well enough, not that it's incorrect.) Here's an intuitive hint though: If I assume I'm brown, then I think I know something that all the blue-eyed people don't know: If I'm brown, and I see 99 blue, I know there are 99 blue. I also know that all the blue think there might be 1 less. But if I'm blue, that assumption would be incorrect. Either way, I realize that all the blues can think the same way as me. If there are 99 blue, they might assume that there are 98, and they might assume that those 98 think there are 97 and that the 98 assume that the 97 that are assumed to be seen in turn assume there are 96. This works despite my knowledge that all those assumptions are wrong. I also know that the 98 other blue (in any order) don't assume there are only 97, but I also know that the 99 blue I see don't know that! So perhaps I think I know everything about everyone else's assumptions and whether they're right or wrong. What I don't know is whether or not MY assumption is wrong. (I know that everyone else knows whether my assumption is wrong---I don't know anything about my own eye color but everyone else does---but that doesn't even matter). Edited February 14, 2012 by md65536 Link to comment Share on other sites More sharing options...
John Cuthber Posted February 14, 2012 Share Posted February 14, 2012 (edited) Do you agree that an islander posting a notice saying "I can see blue eyes " has the same effect as the traveller ? Proof by induction is the root of the unexpected hanging paradox. It gives the wrong answer. Edited February 14, 2012 by John Cuthber Link to comment Share on other sites More sharing options...
md65536 Posted February 14, 2012 Share Posted February 14, 2012 (edited) Do you agree that an islander posting a notice saying "I can see blue eyes " has the same effect as the traveller ? Proof by induction is the root of the unexpected hanging paradox. It gives the wrong answer. I think that if every islander read the notice on the same day and every islander knew that everyone else read the note that day, that it would be the same effect. Dear lord, don't tell me that we now have to prove that proof by induction is a valid form of proof, before you'll accept the solution?! There is no paradox in this puzzle. I've written an induction proof that never relies on considering the existence of less than 100 blue-eyed islanders. Unfortunately it got far more complicated than I expected. The key bit of understanding is in B3 below, in understanding how an unknown false assumption about a known false assumption can be built up into a chain of assumptions about what others can assume about others. I was hoping to do an induction on the length of the chain of assumptions, but it didn't come to me. Unfortunately, this proof probably offers no help in understanding why it works, because that's lost in the complicated details. But I think that once you get the gist of why the solution works (using any proof or reasoning), then a proof like this can help nail down the intricate details. I'm sure that something a lot simpler is possible. Please let me know of any improvements you see! There are likely mistakes due to being braindead. ---- I'm using the XKCD version: A guru tells everyone she sees someone with blue eyes on day 1. Anyone who knows their eye color must leave the day they find out. Suppose there are M blue-eyed islanders. B1. If there are N blues, they will each see N-1 blues. Proof: It is clearly so. QED. B2. Given N blues, if they can't assume without contradiction that there are N-1 blues, then they will leave today. Proof: Suppose there are N blues. Suppose any one of them assumes that there are N-1 blues and derives a contradiction. Then (since their logic is flawless), there must not be N-1 blues. But by B1 they see N-1 blues, and they know there can only be that many or more, so they know their own eyes must be blue, and by the rules will leave today. QED. B3. If any blue person P sees N blue and assumes without any possible contradiction that there are N blue, and none of the blue leave today, then P can assume without contradiction that the N observed blue can assume without contradiction that there are N-1 blue. Proof: Suppose A1: that some blue person P sees and assumes that there are N blue, with no possible contradiction and that none of the blue leave today. Assume hypothesis B3 is false, and that P cannot assume without contradiction that the N observed blue can assume without contradiction that there are N-1 blue. Then P knows that the N observed blue can't assume without contradiction that there are N-1 blue. If there were N blue, then P knows by B2 they will leave today. Since they don't leave today, P knows that there are not N blue. Therefore P cannot assume without contradiction that there are N blue. This contradicts A1. Thus B3 by contradiction. QED. B4(n): On day n with no one having left yet, every blue knows that there are at least n blue-eyed islanders. B5(n): On day n with no one having left yet, every blue knows that every blue knows there are at least n blue-eyed islanders. Proof by induction: Base case: Everybody sees at least M-1 islanders so everyone knows there are at least M-1 islanders. So clearly every blue knows there are at least 1 blue on day 1, and that every blue knows it. Inductive case: Assume B4(k) and B5(k) holds for some k. On day k with no one having left, every blue knows there are at least k blue, and every blue knows that every blue knows it. Now say on day k+1 no one leaves that day. Assume B4(k+1) is false. Assume that on day k+1 with no one left yet, that not every blue knows that there are at least k+1 blue. Then it is possible for some blue person P to assume that there are k blue without contradiction. If P sees k-1 blue, then since P knows there are at least k blue, P would know she is blue and leave today; since that doesn't happen P must see k blue. By B3, P can assume without contradiction that the k observed blue can assume without contradiction that there are k-1 blue. But since by B5(k) P knows that the blue know there are at least k blue, they cannot assume without contradiction that there are only k-1 blue. Thus by contradiction B4(k+1) must be true. Since each blue has flawless logic, each is able to do the above proof of B4(k+1), and know that on day k+1 with no one having left yet, every blue knows that there are at least n blue-eyed islanders. Thus B5(k+1). By induction, on day M every blue knows that there are at least M blue. By B2, they will leave today. Edited February 14, 2012 by md65536 Link to comment Share on other sites More sharing options...
John Cuthber Posted February 14, 2012 Share Posted February 14, 2012 "Dear lord, don't tell me that we now have to prove that proof by induction is a valid form of proof, before you'll accept the solution?!" No. You just have to explain why it doesn't work for the unexpected hanging paradox. There are lots of versions but the idea is the same. Here's one A teacher tells the class that there will be a test next week but that (in order not to spoil their evening) they will not know about the test on the evening before it happens. The kids soon realise that the test cannot be on Friday. Because if it were, then they would know about it on Thursday night. But, since they know the test can't be on Friday, then if, on Wednesday night they haven't had the test, they realise it must be on Thursday (because Friday was already ruled out. But that breaks the rule so the test can't happen on Thursday. So, if, on Tuesday night they haven't had the test yet, they know it cant't be on Friday or Thursday- so it must be on Wednesday. But, once again, that breaks the rule- so the test can't be on Wednesday. You can carry on this inductive argument and show that the test cannot take place. But in the real world, the teacher can set the test any day but Friday and meet the terms of the rules. So the inductive reasoning gives the wrong answer. My view is that the islanders' fate is similar (but the other way round). So you can't rely on an inductive proof. If the all read the notice board every morning the board is the equivalent of the traveller. But it adds no new knowledge. So why is there a sudden countdown to death? Link to comment Share on other sites More sharing options...
md65536 Posted February 14, 2012 Share Posted February 14, 2012 "Dear lord, don't tell me that we now have to prove that proof by induction is a valid form of proof, before you'll accept the solution?!" No. You just have to explain why it doesn't work for the unexpected hanging paradox. I think this is totally off topic, but gladly. The prisoner assumes that a Friday execution is impossible because otherwise it wouldn't be a surprise. Once she's committed to that logic, she will be surprised if the execution happens on Friday. The prisoner assumes that the judge's statement is true. I.e. that the prisoner will be executed on some day and that it will be a surprise. The prisoner then uses logic to deduce that she won't be executed. Thus by contradiction, the judge's statement cannot be true. In which case, the prisoner has used terribly false logic. This is the opposite of the blue-eye puzzle, where everyone uses perfect logic! The proof by induction in the hanging paradox contradicts the assumption used to set up the induction. Therefore it is an invalid proof. There is no such contradiction in the blue-eyed islanders puzzle. If the all read the notice board every morning the board is the equivalent of the traveller. But it adds no new knowledge. So why is there a sudden countdown to death? I have failed. Wikipedia explains this better and more concisely than I have: http://en.wikipedia.org/wiki/Common_knowledge_(logic) Perhaps if you still don't get it after that, you can edit the wiki with your proof that everyone else is wrong. Link to comment Share on other sites More sharing options...
John Cuthber Posted February 15, 2012 Share Posted February 15, 2012 Who, before they read the notice, did not know that there were islanders with blue eyes? Link to comment Share on other sites More sharing options...
Spyman Posted February 15, 2012 Share Posted February 15, 2012 Who, before they read the notice, did not know that there were islanders with blue eyes? It is NOT the knowledge of that there exists islanders with blue eyes that sets this off, it is the synchronization of all islanders simultaneously with the shared knowledge that all others also are synchronizated. Since they where forbidden by their religion to discuss eye-colour an outsider is necessary for this synchronization to ever happen. Link to comment Share on other sites More sharing options...
md65536 Posted February 15, 2012 Share Posted February 15, 2012 I've written an induction proof that never relies on considering the existence of less than 100 blue-eyed islanders. By the way I think my proof is flawed. If it worked as-is, I think you could replace "blue" with "brown" and conclude that it would work with any color, and it shouldn't. I think I need to add something like: B0. If a blue islander assumes there are 0 blue, they will leave today. Proof: This contradicts the guru's information. Then B3 fails in the case of N=1, because in that case A1 can't be supposed without contradiction. That would need to be fixed. For other colors B3 doesn't fail in the case of N=1. Another subtle flaw is that the proof relies on the islanders using the conclusions of the lemmas, in order to prove that they can deduce that information. So the proof should be rewritten from their perspective. That would include not giving any information that an islander doesn't know, including the actual number of blue. So the induction base case wouldn't use the number of blue. I was wrong; the islanders do have to consider the existence of much less than 100 blue---or at least the possibility that someone might think that someone might think that (repeat a bunch of times) that there might be no blue islanders. Link to comment Share on other sites More sharing options...
John Cuthber Posted February 15, 2012 Share Posted February 15, 2012 Imagine a bunch of islanders with the same characteristics except that they are not very bright. They don't realise what other people think. Then one day suddenly the God of "setting up logic puzzles" gives them perfect logic. ( This is a long time before the traveller arrives or the Guru speaks.) As far as I can see they all suddenly become aware that everyone knows that lots of people have blue eyes and that starts the destruction. Lets look at the simple cases One blue. It depends- but as long as the rules say that they know that there are blue eyed and brown eyed people on the island and he sees no blues, he knows he must be It. So he knows his eye colour and leaves or dies depending on which version of the puzzle If they don't explicitly know there are two colours nothing happens with just 1 blue. With 2 blues clearly they all know there is more than one colour. The two blues now know that there is either 1 blue (the other guy) or there are two and they are one of them. If they see the other guy the next day then they know they are the 2nd blue. And so on. The clock doesn't start ticking when the traveller arrives or when the notice is posted. The notice doesn't tell them anything. The presence of lots of blue eyes is already common knowledge. Any of them could post the notice. None of them would learn anything from it. So the clock starts when the initial conditions of the puzzle are set up. This society cannot last more than 100 days. As spyman says "It is NOT the knowledge of that there exists islanders with blue eyes that sets this off, it is the synchronization of all islanders simultaneously with the shared knowledge that all others also are synchronizated." But this synchronisation starts when they realise their circumstances. That happens as soon as those circumstances arise. (they are perfectly logical. why would they wait for the traveller to tell them something they already know, and they know that their fellow islanders know.) OTOH Spyman also says "Since they where forbidden by their religion to discuss eye-colour an outsider is necessary for this synchronization to ever happen. " They are forbidden to discuss it, but my point is that they don't need to. They know "if I can see lots of blue eyes- so can everybody else"- that is common knowledge. And the answer to MD65536's jibe about me explaining why everybody else got it wrong is that they were distracted by the traveller. Nobody thought to ask what happened a year before he arrived. Link to comment Share on other sites More sharing options...
md65536 Posted February 16, 2012 Share Posted February 16, 2012 (edited) One blue. It depends- but as long as the rules say that they know that there are blue eyed and brown eyed people on the island But they don't say that. If they did then it'd be common knowledge (in the case of just 1 blue existing). But this synchronisation starts when they realise their circumstances. That everyone knows that everyone knows that everyone knows (and so on) that there are blue-eyed people is not known. The synchronization only happens when it becomes common knowledge. They are forbidden to discuss it, but my point is that they don't need to. They know "if I can see lots of blue eyes- so can everybody else"- that is common knowledge. Yes they know first order knowledge and they know second order knowledge and they can deduce k'th-order knowledge up to k-1, which they can't deduce without the outsider's information. And the answer to MD65536's jibe about me explaining why everybody else got it wrong is that they were distracted by the traveller.Nobody thought to ask what happened a year before he arrived. What happened a year before he arrived? What I meant was, why does everyone whose edits resulted in the current version of the wiki http://en.wikipedia....owledge_(logic) get it wrong? Edit: Sorry, I guess I tend to be a bit of an arse about some things. Perhaps I read your posts the wrong way -- when you say "the given solution must be incorrect," do you really only mean to say "I don't understand the given solution"? Cause then you're not intentionally saying that everyone who gives the correct solution is wrong. Edited February 16, 2012 by md65536 Link to comment Share on other sites More sharing options...
Spyman Posted February 16, 2012 Share Posted February 16, 2012 Imagine a bunch of islanders with the same characteristics except that they are not very bright. They don't realise what other people think. Then one day suddenly the God of "setting up logic puzzles" gives them perfect logic. ( This is a long time before the traveller arrives or the Guru speaks.) As far as I can see they all suddenly become aware that everyone knows that lots of people have blue eyes and that starts the destruction. That would be one different way to set up an synchronization, but that information is not included in the original quiz. The clock doesn't start ticking when the traveller arrives or when the notice is posted. The notice doesn't tell them anything. The presence of lots of blue eyes is already common knowledge. Any of them could post the notice. None of them would learn anything from it. So the clock starts when the initial conditions of the puzzle are set up. This society cannot last more than 100 days. The initial conditions in the asked quiz does not include a syncronization point and it is also assumed that the society can last. As spyman says "It is NOT the knowledge of that there exists islanders with blue eyes that sets this off, it is the synchronization of all islanders simultaneously with the shared knowledge that all others also are synchronizated." But this synchronisation starts when they realise their circumstances. That happens as soon as those circumstances arise. (they are perfectly logical. why would they wait for the traveller to tell them something they already know, and they know that their fellow islanders know.) No, one thousand persons living their lives on an island will not individually realise their circumstances simultaneously. OTOH Spyman also says "Since they where forbidden by their religion to discuss eye-colour an outsider is necessary for this synchronization to ever happen. " They are forbidden to discuss it, but my point is that they don't need to. They know "if I can see lots of blue eyes- so can everybody else"- that is common knowledge. No, it is not enough with common knowledge, if they don't know if they count from the same day then they can't make any valid conclusions. And the answer to MD65536's jibe about me explaining why everybody else got it wrong is that they were distracted by the traveller. Nobody thought to ask what happened a year before he arrived. It's possible to set up a lot of different things that happened a year before he arrived, but that is not what is asked for. Link to comment Share on other sites More sharing options...
md65536 Posted February 16, 2012 Share Posted February 16, 2012 (edited) That would be one different way to set up an synchronization, but that information is not included in the original quiz. No, the sudden acquisition of logic does not give them common knowledge (I mean the precise definition in logic) that there exist blue-eyed people. It is still possible to assume that someone assumes that someone assumes that someone assumes ... (repeated many times) that there are no blue-eyed people, and not deduce a contradiction. The puzzle doesn't rely only on an implicit consensus on a "start time", as if there is some secret shared plan that works as long as everyone chooses to follow it. It just relies on the fact that if everyone is acting perfectly logically (which is true by the rules), then if a blue-eyed islander assumes she is not blue-eyed, she will derive a contradiction on the N-1th day, and thus know that she has blue eyes. If the guru had only said "You can all start your logical voodoo now", no one would leave the island, because no one would be able to deduce their eye color. The guru's statement about blue eyes really is essential. Further, even if there are only blue and brown-eyed islanders, and all the blue leave, then (if it's not common knowledge that there were only blue or brown), the brown could stay indefinitely. For, if I see only brown eyes around me, but I still have no way to say for sure that I don't have green eyes, then I don't know my eye color. In other words, if I can assume without possible contradiction that I have green eyes, and I can assume without contradiction that I have brown eyes, then I don't know my eye color. All I know at that point is whether or not I have blue eyes. Edited February 16, 2012 by md65536 Link to comment Share on other sites More sharing options...
John Cuthber Posted February 16, 2012 Share Posted February 16, 2012 "But they don't say that. If they did then it'd be common knowledge (in the case of just 1 blue existing)." Congratulations! You may have just saved the life of everyone on the island. If they don't know that there are (exactly) two eye colours, and what they are, then they have no reason to die. Any islander can think " I may see lots of blues and browns, but for all I know my eyes are grey, or yellow, or pink with purple stripes. I have no real idea what colour my eyes are- so I don't need to commit suicide." For the puzzle to work they need to know that there are only two colours "available" and what those colours are. "The initial conditions in the asked quiz does not include a syncronization point and it is also assumed that the society can last." It is, indeed, so assumed- but I don't think the assumption is valid. Link to comment Share on other sites More sharing options...
md65536 Posted February 16, 2012 Share Posted February 16, 2012 If they don't know that there are (exactly) two eye colours, and what they are, then they have no reason to die. Any islander can think " I may see lots of blues and browns, but for all I know my eyes are grey, or yellow, or pink with purple stripes. I have no real idea what colour my eyes are- so I don't need to commit suicide." Wrong again. Sure an islander can try to think that, but if a blue assumes that their eyes are not blue they'll eventually be able to derive a contradiction. Thus they know it can't be that their eyes are not blue. Perhaps one way to ensure you stay is to kill all the blue-eyed islanders you see. I'm not sure if it would suffice to kill just one, but I think it would. For the puzzle to work they need to know that there are only two colours "available" and what those colours are. Wrong again. Check the puzzle as written here: http://www.xkcd.com/blue_eyes.html It specifically states "assorted eye colors" and doesn't state what they are, or how many. The puzzle still works. Have you not been looking at any of the links that people provide? All your "questions" are answered in the links. Link to comment Share on other sites More sharing options...
John Cuthber Posted February 16, 2012 Share Posted February 16, 2012 "It specifically states "assorted eye colors" " The xkcd version does. The OP version does not. Link to comment Share on other sites More sharing options...
Spyman Posted February 17, 2012 Share Posted February 17, 2012 (edited) No, the sudden acquisition of logic does not give them common knowledge (I mean the precise definition in logic) that there exist blue-eyed people. It is still possible to assume that someone assumes that someone assumes that someone assumes ... (repeated many times) that there are no blue-eyed people, and not deduce a contradiction. As I interpreted John Cuthber's example, there would suddenly be common knowledge from a God. The puzzle doesn't rely only on an implicit consensus on a "start time", as if there is some secret shared plan that works as long as everyone chooses to follow it. It just relies on the fact that if everyone is acting perfectly logically (which is true by the rules), then if a blue-eyed islander assumes she is not blue-eyed, she will derive a contradiction on the N-1th day, and thus know that she has blue eyes. The start time is needed, if everyone don't start acting on the same day, no islander can derive anything on his own counting. Further, even if there are only blue and brown-eyed islanders, and all the blue leave, then (if it's not common knowledge that there were only blue or brown), the brown could stay indefinitely. For, if I see only brown eyes around me, but I still have no way to say for sure that I don't have green eyes, then I don't know my eye color. In other words, if I can assume without possible contradiction that I have green eyes, and I can assume without contradiction that I have brown eyes, then I don't know my eye color. All I know at that point is whether or not I have blue eyes. I think the quiz in the OP assumes only two eye colours and in the OP's answer those with brown eyes commit suicide the next day. "The initial conditions in the asked quiz does not include a syncronization point and it is also assumed that the society can last." It is, indeed, so assumed- but I don't think the assumption is valid. Well, I think the assumption is valid, can you show how the society in the OP dies early without introducing new stuff? Edited February 17, 2012 by Spyman Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now