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?
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