From: radams@BNR.CA (Rodney Adams)
Subject: Re: Problematic smurfs!
Reply-To: "Rodney Adams" <RADAMS@BNR.CA>
Organization: Bell-Northern Research, Ltd.
Date: Tue, 01 Sep 1992 15:23:04 GMT

In article <65049@cup.portal.com>, ts@cup.portal.com (Tim W Smith) writes:
|> I've heard the problem stated in terms of a village of perfect logicians.
|> Each has either a red dot or a blue dot on the back of his neck.
|> 
[ rest of problem and solution deleted ]
|> 
|> Now for the interesting problem.  Suppose there were at least two blue
|> dots.  Then everyone already knows that there is at least one blue dotted
|> person in the village.  The Stranger seems to have given them no information,
|> so why was his statement fatal?
|> 

As an example, consider the case of two logicians with blue dots from
their perspectives.  Each of the two logicians knows that there is at
least one blue-dotted person in the village, because they can each see
the blue dot on the back of the other's neck.  However, one does not know
what the other sees.  Therefore, one of the blue-dotted logicians does 
not know that the other knows that there is at least one blue-dotted
logician.  Therefore, each blue-dotted logician can conclude that either
there is not a blue dot on the back of his neck and that the other blue-dotted
person does not know that there is at least one blue-dotted person, or that
he does indeed have a blue dot on the back of his neck.

As the red-dotted logicians know that the two blue-dotted logicians can not
determine that they have blue dots, there is no way for any of the red-dotted
logicians to know if there are two or three blue-dotted logicians.  Thus,
they also can not determine the color of their dots.

Therefore, the stranger's statement is fatal because now everyone knows that
everyone else knows that there is at least one blue-dotted logician.

By the way, I checked on sci.math to see if anyone had gotten the Smurf
problem.  Though not the first to get the right solution, Chris D'Costa 
is one of the r.o.m readers whose name I recognized.

Here is another interesting problem from Steven Moon, one of the sci.math 
posters who (incorrectly) answered the Smurf problem:

 This problem [the Smurfs] is a variation of one I heard some time ago.
 It is with three individuals each wearing one of five hats - three
 brown, two black.  They are standing in a line and can only see
 those in front of them.  The last in line can see the color of
 the hats of the two in front of him.  The second in line can see
 only the one in front of him, and the first in line can't see
 anyone's hat.  They can't talk or leave until they are certain what
 color hat they have on.  After a long time the person first in
 line leaves.  What color hat does he have on?

This problem is probably much easier than the Smurf problem (it took about
a minute or two to solve), but I will wait until tomorrow before posting an
answer unless someone else does so (the poster of the problem did not
include an answer).
 
----------------------------------------------------------------------

Rodney G. Adams
The opinions expressed above are not necessarily those of my employer.
As if you didn't already know that....
"Not a shred of evidence exists in favor of the idea that life is 
serious."                                               - Brendan Gill
Newsgroups: rec.org.mensa