minsky@hplabsb.UUCP (08/26/84)
Here is a neat little puzzle I heard late last night. Thanks to Tom Mrowka who told it so well. Somewhere in the Great Midwest there is a sleepy little town known as Dot Town, U.S.A. The inhabitants of this town are just like you and me, except that they have the following four properties: 1) Each inhabitant has a dot on the back of their neck. Each dot is either blue or red. No one can see their own dot. 2) The inhabitants are perfectly logical, except for property 3. 3) Whenever any inhabitant discovers the color of their dot, he/she commits suicide on that evening. 4) Everyone turns out on the Town Square every day at noon, to socialize and look at each other's dots. Life in this little town proceeds as usual until one day at noon a Stranger drives through, and looking around him in the Square, exclaims in a voice loud enough for everyone to hear: "Wow! At least one of you people has a blue dot on the back of their neck!" Having spoken, he roars off in a cloud of dust and disappears forever, leaving the good people of Dot Town (U.S.A.) to ponder his words. The question is: what happens? Cheers, Yair Minsky ..!hplabs!minsky (but not for long)
halle1@houxz.UUCP (J.HALLE) (08/27/84)
What happens is that the next day the stranger files claim to all the land of Dottown, since everyone is now dead. You see, everyone had red dots and the stranger lied. Since every person saw only red, each person assumed the blue was on his or her own neck. "Knowing" ones own color, each person committed suicide. Or perhaps he wasn't lying. Either there was exactly one blue dot, in which case everyone dies within 2 days, or there were 2 or more, in which case things go on like before.
das@ucla-cs.UUCP (08/28/84)
...
This is an interesting variant of a puzzle I read, involving unfaithful
spouses instead of dots, but it works the same way. I think you left off
two necessary conditions:
2') Everyone in Dot Town is a perfect logician, AND EVERYONE IN DOT TOWN
KNOWS THIS FACT.
5) Although Dot Town residents gather to look at each other's dots, no one
ever says anything about anyone else's dot. (And the only thing they
"say" about their own dot is killing themselves in the evening of the
day they determine their own dot's color.)
-- David Smallberg, das@ucla-cs.ARPA, {ihnp4,ucbvax}!ucla-cs!dasnorm@ariel.UUCP (08/28/84)
Life continues as before, since noone knows whether or not the stranger (or anyone else) tells the truth, unless they observe it personally. Noone knows enough to commit suicide without personally seeing the back of their own neck.
das@ucla-cs.UUCP (08/28/84)
...
In light of J. Halle's proposed (but incorrect, I'm afraid) answer, there is
another condition which should be made clear:
6) Everyone believed the Stranger when he said "At least one person in town
has a blue dot!", and everyone knows that everyone believed the Stranger.
What makes this puzzle so wonderful is that the answer is NOT "Well, if more
than a couple of people have blue dots, nothing happens."
-- David Smallberg, das@ucla-cs.ARPA, {ihnp4,ucbvax}!ucla-cs!dasmarkb@sdcrdcf.UUCP (08/29/84)
In article <houxz.940> halle1@houxz.UUCP (J.HALLE) writes: >Or perhaps he wasn't lying. Either there was exactly one blue dot, in >which case everyone dies within 2 days, or there were 2 or more, in which >case things go on like before. Not true. If there are 2 blue dots, then most people see 2 blue dots and just 2 people see 1 blue dot. Each of those 2 people notice that the other does not commit suicide on the first evening, therefore they now know that the other must see a blue dot on their own back and commit suicide on the second day and everyone else dies then next day. With 3 blue dots they each reson that the 2 people they see with blue dots can have the only blue dots after 2 days with no deaths, and commit suicide on the 3rd day. Generalizing, with n blue dots all people with blue dots dies on day n followed by everyone else on the next day. The interesting case is if everyone has (and therefore sees) only red dots. Why should you believe the stranger? You have no evidence that he told the truth (if you see a blue dot he had to have told the truth). Because there is no condition stated in the problem claiming that the Dotians always believe what strangers tell them. Whether or not everyone dies now depends on the probability that someone believes the stranger. Mark Biggar {allegra,burdvax,cbosgd,hplabs,ihnp4,akgua,sdcsvax}!sdcrdcf!markb
gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (08/29/84)
Ed Davisson & I discussed the Dot Town puzzle under the assumption that everyone believed the stranger (assume it was God speaking or some such). Under this condition, the puzzle turns into a "prisoner's dilemma". One can reason that the town suicides no matter how many blue dots there are (must be at least one, God has spoken), under additional reasonable assumptions about how long it takes the logicians to reason etc. The dilemma is that in the case of several blue dots no one has received any additional information from God's speech, and it is possible to reason that the town was stable and alive before the speech. If the stranger is not known to be trustworthy, then also there is no new information added, so if the town was stably alive it remains so. Can such a town exist (be self-consistent and stably alive)? Apparently not, since its existence leads to the dilemma. Is there some way to determine that the town cannot exist without invoking the dilemma??
minsky@hplabsb.UUCP (Yair Minsky) (08/30/84)
Doug Gwinn is correct in that everyone will kill themselves eventually after the stranger arrives, although he did not state his reasoning or the exact number of days that the process will take (it depends on the actual number of blue dots). He is wrong, however, in concluding that the stranger imparts no information by his statement. This is a tricky point, but I believe the way to think about it is that the information imparted by the stranger is not just about the number of dots but also about the possible reasoning processes available to the good people of Dot Town. That, in fact, is the beauty of this puzzle. I don't want to say any more for fear of spoiling the puzzle, but at any rate I don't think there is any insoluble dilemma involved. Enjoy, Yair Minsky PS By the way, the additional properties suggested after the original posting are correct. I hadn't included them because they seemed reasonably implicit, but looking back I guess I was wrong.
sharp@farmer.DEC (08/30/84)
What happens is that if n people in Dot Town have blue dots those people commit suicide on the n'th day, and all the rest of the people commit suicide on the n+1'th day. Once the stranger announces that at least one person has a blue dot then: If only one person has a blue dot, that person sees no blue dots, so he or she knows that she's the one with the blue dot. He or she then commits suicide on day 1. If two people have blue dots, then they each see one person with a blue dot. When they see that same person again on day 2, knowing what that person's logical behavior would be if there was only one blue dot, they realize that they both have blue dots, and so commit suicide on day 2. If three people have blue dots, they each see two people, and reasoning as above they realize on day 3 that they each have blue dots. Et cetera, up to day n. Of course on day n+1 all the red dot people follow suit.
gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (08/31/84)
After several of us wasted a lot of time trying to analyze the paradox that the citizenry of Dot Town survive okay until someone tells them something they all knew, Gary Moss finally nailed the error in our analysis. (I had been prepared to bring in G"odel's incompleteness theorem in order to guarantee that there was no way to predict how long one would have to wait before suiciding, but it turns out to be unnecessary to do so.) This is a remarkable puzzle. Thanks for posting it!
dgary@ecsvax.UUCP (08/31/84)
<> It's interesting to note that the Dotians are not only prohibited from saying, 'Your dot is blue,' but cannot say, 'There is at least one blue dot here,' since, in this latter case, they take on the role of the stranger. Gary
lab@qubix.UUCP (Q-Bick) (08/31/84)
But what happens if there is a local radical who is not inquisitive
about the color of his own dot? E.g.:
Stranger: "At least one of you has a blue dot!"
Cool-dot Luke: "So?"
[Lest you think red is hot and blue is cool, ask your local astronomer.]
--
The Ice Floe of Larry Bickford
{amd,decwrl,sun,idi,ittvax}!qubix!lab
You can't settle the issue until you've settled how to settle the issue.matt@oddjob.UChicago.UUCP (Matt Crawford) (09/01/84)
> The dilemma is that in the case of several blue dots no one has received > any additional information from God's speech, and it is possible to reason > that the town was stable and alive before the speech. They do have new information, of a sort: they have a day to start counting from. ___________________________________________________________ Matt University ARPA: crawford@anl-mcs.arpa Crawford of Chicago UUCP: ihnp4!oddjob!matt