From: johnson@sleipnir.mnesouth.corp.mot.com ("Johnson")
Subject: Re: Problematic smurfs! (answer)
Reply-To: johnson@sleipnir.mnesouth.corp.mot.com
Organization: Motorola Wireless Enterprises, Schaumburg, IL
Date: Mon, 31 Aug 1992 16:56:53 GMT
Keywords: smurfs

In article <94952@bu.edu>, spacefox@acs.bu.edu (Godfrey Degamo) writes:
=)     A group of 1000 smurfs wear either a red or blue hat on their head.
=)They can only wear one color. The color hat on their head is known to all, but
=)the wearer.  The wearer of the hat has no means whatsoever for obtaining the
=)color of his hat.  It is never the case that all 1000 smurfs will wear
=)the same color hat.
=)     One day the mayor, not apart of the 1000 smurfs, decides to call a
=)town meeting.  All 1000 smurfs are gathered into the town hall.  The mayor
=)is not wearing a hat.  During the meeting, the mayor asks that all the
=)smurfs wearing red hats to stand up.
=)     There is a bit of commotion in the crowd, but no one stands up.
=)     The mayor requests the same demand a bit more sternly.
=)     Again, commotion, but no one stands up.
=)     The mayor, irate, demands the red hatted smurfs to stand up.
=)     Then, a certain amount of smurfs rise.
=)find:
=)     The exact amount of smurfs that rise.  
=)         (Hint: This number will be greater than one.)
=)     The color of the hats of the smurfs that rise.
It is necessary to assume that the smurfs do not see each other rise, and
thus are only aware that nobody has stood up by the fact that the mayor
continues to insist that the red-hatted smurfs rise.  Otherwise, the
problem goes asynchronous, and no definite answer is possible.

Three smurfs with red hats rise.
=)
=)more importantly,
=)     Explain how you deduced your answer.
There are three smurfs with red hats, A, B, and C.  While the other 997
smurfs know this, C knows of only two red-hatted smurfs in the crowd.
The first time the mayor asks them to stand, C observes that B thinks
that he is referring to A, and vice versa.  The second time, from C's
standpoint, B and A should both realize that there are two of them, and
that by the process of elimination, they are the second.  The third time
the mayor asks, C realizes that both A and B have failed to stand and
must also know of two red-hatted smurfs, and that the third one must be
him.  A and B, thinking identically, rise also.

If they can see whether anyone else stands, sooner or later one of the
brighter smurfs will stand when he realizes that others are waiting for
him.  For example, the first time the mayor asks, C would watch A and B
momentarily.  A and B would watch each other and C.  Soon C would realize
that if A only saw B and B only saw A, each would realize after a moment's
hesitation that the other also saw a red-hatted smurf, and that they were
waiting for each other. Since they did not rise on noticing that, there
must be a third red-hatted smurf in the meeting.  Therefore, C would rise.
A and B would then feel that they were off the hook for a moment, until each
saw that the other (and the assembly) was still waiting.  Thus, if the mayor
waited long enough, all the red-hatted smurfs would stand on the first
question.
-- 
+-----------------------------------------------------------------------------+
|  "Johnson"                              | "                               " |
|  johnson@sleipnir.mnesouth.corp.mot.com |               -- Marcel Marceau   |
+-----------------------------------------------------------------------------+
|  Disclaimer:  It's just my Tourette's Syndrome acting up again.             |
+-----------------------------------------------------------------------------+
Newsgroups: sci.math