Another riddle for you
Posted by Rob Herman at July 13th, 2006
A three part riddle today.
Part 1: You have 100 teammates, all standing in a row. They are facing forward so each can see the ones in front of him. Each one has either a red hat or a blue hat. Starting with the one in back and proceeding forward, each is asked the color of the hat on his head. If the guesser is right, the team gains a point.
The team gets a chance to decide on a strategy beforehand. However, the gamemaster is aware of their strategy, so they need to optimize the worst-case scenario. What strategy should they choose?
Part 2: Just like part 1, but work out the solution for any number of colors of hats.
Part 3: Like part 1 (only two colors of hats), but one of the teammates is a traitor. He is in league with the gamemaster and will do anything possible to mess up the team’s score. To make matters worse, the gamemaster, being aware of the team’s strategy, can place the traitor where he will do the most damage.
The players are aware of the traitor, though. What strategy can they use to optimize the worst case?
Also (if this is the same riddle we talked about) everyone of your team mates have perfect memory and scientific calculators. (your solution can be as complex as desired) this is particularly important in part 3. The best I can get for part three with a line of one hundred people is 87. If any one can do better or want to know my solution please post.
The player in the back counts the number of blue hats from the eighth player forward. Players 1-7 then spell out this number in binary, blue for 1, red for 0.
The eighth player now has enough information to call the color of his hat. He has been told that there are c blue hats. If he can count c blue hats in front of him, then his hat is red. Otherwise, if he can count c-1, then his hat is blue. Every player forward repeats this procedure, decrementing the count of blue hats everytime someone calls blue, for a score of 93.
This method generalizes to n players by increasing the length i of the ‘coding segment’ of players so that 2^i >= n, giving a score of n - i.
For part 3, you can fool a traitor in the count of hats by using a Hamming error correcting code - for 100 people, and a number of seven bits, you can code the number instead in 11 binary digits such that any single bit error can be detected and corrected, which would nominally give a score of 89 (see http://en.wikipedia.org/wiki/Hamming_code). Therefore, the traitor would be useless if placed in this section.
Therefore, the traitor would be placed in the second section. The traitor will trip up exactly one person further down the line. If the traitor is a red hat and calls blue, then the next red in the sequence will incorrectly call blue. However, then the counts would be fixed, and the rest would be correct. Similarly, if the traitor is blue and calls red, the next blue will be fooled and call red incorrectly, but then the count of hats would be correct after that.
If the traitor is red and call blue, any red players in the sequence between him and the next blue will know that he’s lying, since they can see all the blues they expect (ie, they know there are 40 blues, and after the traitor’s bad call, they can still see 40 blues). Therefore, they won’t be fooled. Similarly, if the traitor is blue and calls red, any blue players in the sequence before the next red won’t be fooled either. Therefore, the maximum damage the traitor can cause is 2, his hat, and the next player of the opposite color. This gives me a solution of 87.
I got the same solution for part three. But for part one there exists a soloution to get a score of 99
Upon further investigation a solution exists for part three that gives a score of 97