Puzzle #11 – Not Just Another Hats Problem
September 16, 2007Here is another puzzle for you to ponder during the upcoming week. It would seem a bit far fetched from our usual digital design stuff, but the solution is somewhat related to the topics discussed in this blog. Moreover, it is simply a neat puzzle.
A group of 50 people are forming a column so person #1 is in front of all, followed by person #2 and so on up to person #50.
Person #50 can see all the people in front of him (#49..#1), person #49 can see only #48..#1 and so on.
The 50 people are now given hats in random. Each hat can be either black or white. The distribution of the hats is totally random (i.e. they might be all black or all white and not necessarily 25-25)
The people now take turn in guessing what color hat they are wearing – They are just allowed to say “white” or “black”, nothing more!. Person #50 starts and they continue in order down to person #1. If the person happens to guess the color of his own hat the group receives $1000.
What is the best strategy the 50 people should agree on before the experiments starts to maximize the amount of money they should expect? And what is the sum of money they should expect to earn from this experiment?
(you can do better than pure chance, or much better than $25,000…)
For the experts
What if the experiment is done with hats which are red, black or white? what about 4 colors? What would be the maximum color of hats that will still guarantee the amount from the original variant? and how?
Adventures in ASIC Digital Design 
My initial thought was that person 50 downto 26 says the colors of the hat that person 25 downto 1 is wearing. That way person 50 downto 26 will have 50% chance of getting the right color and person 25 downto 1 will have a 100% chance of getting the right color.
That way you are guaranteed $25,000 and you would expect something around $37,500. But the solution seems a bit too simple, I guess there is a smarter way to do it.
Cynlre 50 ybbxf ng gur 49 crbcyr va sebag bs uvz. Ur pbhagf gur ahzore bs oynpx ungf gung ur frrf. Vs gurer ner na bqq ahzore, ur fnlf Oynpx, vs gurer ner na rira ahzore, ur fnlf Juvgr. (Ur fnlf n pbybe gb perngr rira cnevgl). Uvf bja ung pbybe vf vzcbffvoyr gb xabj, fvapr ab bar ng nyy pna frr vg. Vs gur cnevgl pbybe ur naabhaprf unccraf gb or pbeerpg, gura terng! Vs abg, gurl fgvyy trg nyy gur erfg evtug.
Cynlre 49 abj xabjf rknpgyl jung pbybe uvf ung vf. Gurer ner sbhe cbffvoyr fvghngvbaf ur zvtug rapbhagre.
1. Vs 50 fnvq Juvgr, naq ur frrf na rira ahzore bs Oynpx ungf va sebag bs uvz, gura ur unf n Juvgr ung. Ur naabhaprf Juvgr, ohg ernyyl ur vf fgvyy tvivat n pbybe gung perngrf rira Oynpx cnevgl.
2. Vs 50 fnvq Juvgr, naq ur frrf na bqq ahzore bs Oynpx ungf va sebag bs uvz, gura ur unf n oynpx ung. Ur naabhaprf Oynpx, ohg ernyyl ur vf fgvyy tvivat n pbybe gung perngrf rira Oynpx cnevgl.
3. Vs 50 fnvq Oynpx, naq ur frrf na rira ahzore bs Oynpx ungf va sebag bs uvz, gura ur unf n Oynpx ung. Ur naabhaprf Oynpx, ohg ernyyl ur vf tvivat n pbybe gung perngrf bqq Oynpx cnevgl. Gur cnevgl fuvsgf jurarire n cynlre fnlf Oynpx (nf cynlre 50 qvq).
4. Vs 50 fnvq Oynpx, naq ur frrf na bqq ahzore bs Oynpx ungf va sebag bs uvz, gura ur unf n Juvgr ung. Ur fnlf Juvgr, ohg ernyyl ur vf tvivat n pbybe gung perngrf bqq Oynpx cnevgl. Gur cnevgl unf fuvsgrq.
Gura zbir ba gb gur arkg cynlre, jub ercrngf gur fnzr ybtvp. Rnpu cynlre fvzcyl ybbxf nurnq naq pnyphyngrf rvgure rira be bqq Oynpx ung cnevgl. Jurarire Oynpx vf naabhaprq, gur cnevgl fuvsgf.
Gur tebhc pna or thnenagrrq gb trg ng yrnfg 49 pbeerpg, naq cbffvoyl 50, fb ybat nf gurl nyy xabj juvpu cnevgl (rira be bqq) gung gurl jvyy fgneg ba, naq juvpu pbybe ung gur cnevgl nccyvrf gb. Vs nal ybfr genpx bs jung gur pheerag cnevgl vf, gung jbhyq ernyyl fperj guvatf hc.
Nf sbe zhygvcyr pbybef, V unira’g dhvgr jbexrq gung bhg lrg.
http://www.rot13.com/index.php
club them in groups of 3
the 50th person says:
white : if the colour of 49th and 48th is same
black : if colour is different
49th person knows his hat color by clubbing this info with 48th persons hat color, 48th person also gets to know his hat color
47th person adopts the same technique as 50th ….
32 + 1 = 33 people state the colour correctly
Guys in the even_no(like 50,48,46…2) just say the color of the odd_no guyz hat just infront of him n odd_no guys just repeat what the even_no guy just said.
eg: guy_50 says guy_49 hat color n guy_49 will just rpeat it. So 25 times bingo n 25 times 50-50.
Ben got it correctly. You can guarantee 49 correct answers while #50 will be a guess and therefore will be right 50% of the time.
what about the multiple color variant???
hi…..
Very good technical info ….
rgds
murali
———————
asic-soc.blogspot.com
———————-
#50 should say the color of the hat #49 is wearing, #49 should say #48’s color and so on. This guarantees 49 right answers.
I think the same startegy applies to the multi-colored version. I can’t see why that would be different. Am I missing something…?
yes – you are missing something substantial!
you get money only if you guess YOUR OWN hat’s color!!!
The multicolored version isn’t too hard if you use modulo x algebra where x is the number of colors. On the other hand, perhaps it is a bit harder if the team don’t know beforehand what colors the hats will have…
it is like an even-odd correcting:-)
hi…..i did it using the XOR function, sounds quite long and calculative, but for $49k, one should go for it…
#50 calculates the XOR of 1 to 49 and tells that…
#49 calculates the XOR of 1 to 48 and says that, which also happens to be the color of his hat…
in these calculations i assume:
white = logic 1
black = logic 0
Hi
I doubt , does the guys know that there are total 25white and 25 black caps ,If so As #50 can see all the remaining guys cap colors , He can guess his color , In the same way #49th guy can guess his color by counting number of whites and blacks infront of him , and also adding the color of the hat told by #50 … This strategy makes 100% correct and winning of $50k
Am i missing something ?
It is specifically stated that it is NOT necessarily 25-25… please reread the post.
I got another solution for both the 2-color version and the expert version.
Let’s use 3-color as an example. The strategy should like below:
I need 3 states A B C which can be considered like the three color, but not exactly the same.
From the point of view of the 50th person, he see the 1st and 2nd persons’ color, and calculate a state for the 2nd person.
1st 2nd 2nd person’s state
red red A
red black B
red white C
black red B
black black C
black white A
white red C
white black A
white white B
after get the 2nd person’s state, he starts to calculate the 3rd person’s state using the same metrics, but this time he’s not using the actual color of the 2nd person, but the state of the 2nd person.
2nd 3rd 3rd person’s state
A red A
A black B
A white C
B red B
B black C
B white A
C red C
C black A
C white B
Finally 50th person gets the state of the 49th person’s state. He just use this as his guess. Red for A, black for B, white for C.
Now it’s the guessing turn for 49th person. He got his state from 50th person’s word, and he can calculate 48th person’s state by his own knowledge. So he could get his own color easily.
For the 48th person, he can calculate 47th’s state by his own knowledge. and he can also get his state by deducing from 49th’s state and color. So he could also get his own color.
One thing leads to another, then 49th~1st persons can all get their color according to this rule. So usually they can get $49000, if lucky enough, they can get $50000. (When 50th person’s guess luckily matches his color)
Actually what interests me is this method seems to have no limitation on how many colors. But I haven’t thought it through. Nir, maybe you could check it for me.