View Single Post
  #6  
Old 12-02-2002, 05:00 AM
BruceZ BruceZ is offline
Senior Member
 
Join Date: Sep 2002
Posts: 1,636
Default Answers (both parts)

I figured out the 2 color problem before I saw the other answers and waited to post until I figured out the 3 color problem. Now I have solutions to both parts:

2 colors:
If there are black and white hats, the 10th person will see an odd number of only 1 color since he sees an odd number of people, and only odd + even = odd. He will agree to yell out the color of the odd hats. Based on this, the guy in front of him will know what color his hat must be since he can see the 8 hats in front of him. Similarly, each person in turn can then figure out the color of his hat since he knows 8 other hats and which colors are even and odd. The first 9 will all be correct, and the 10th guy will be correct half the time. So on average we make $47.50.

3 colors:
If there are 3 different color hats it's a little tricker. The 10th guy must see either an odd number of just 1 color, OR an odd number of all 3 colors. If there is an odd number of all 3 colors, he will say "white". The 9th guy will know what this means, and he will always see 1 even color and 2 odd colors in this case. He will know he must be the even color. If there is only 1 odd color, then the 9th guy will either see 2 evens and 1 odd and know he must be one of the two evens but not know which one, or else he will see 1 even and 2 odds, but then he isn't sure if he is one of the odd colors, or if we are in the 3 odd case in which case he would be the even color. The 10th guy is aware of the 9th guy's dilemna and knows what he sees, so the 10th guy will yell out the color of the 9th guy's hat in this case, UNLESS it is white since white already means all odd. Instead, in this case if the 9th guy is white, the 10th guy will yell out the one color that the 9th guy cannot possibly be (black or red, the odd color if 2 evens or the even color if 2 odds). Then the 9th guy will know what case we are in and that his hat is white, and the others will know the situation as well since this is the only case where "red" or "black" is called and the 9th guy doesn't call out the same color.

So the 10th guy's algorithm is:

<pre><font class="small">code:</font><hr>
IF (all 3 colors are odd) say "white"
IF (1 color is odd)
IF (9th guy sees 2 odds and 1 even)
IF(9th guy is not white) say 9th guy's color
ELSE say even color
ENDIF
ENDIF
IF (9th guy sees 2 evens and 1 odd)
IF(9th guy is not white) say 9th guy's color
ELSE say odd color
ENDIF
ENDIF
ENDIF
</pre><hr>

9th guy's algorithm is:

<pre><font class="small">code:</font><hr>
IF (10th guy says white) say even color
IF (see 2 odds and 1 even)
IF (10th guy says odd color) say color 10th guy says
ELSE say "white"
ENDIF
ENDIF
IF (see 2 evens and 1 odd)
IF (10th guy says even color) say color 10th guy says
ELSE say "white"
ENDIF
ENDIF

</pre><hr>
Is there a simpler way? Maybe, maybe not. I'm happy with this. The first 9 guys will be right, and the 10th guy will be right 1/3 of the time, so we make $46.67 on average.

This is like even and odd parity if you know what that is.
Reply With Quote