Hats, puzzles
Ms. Frizzle posts a puzzle.
One hundred people have been selected as prize winners. Each will get the same amount of money, from $1000 to $100,000. This is how the prize will be distributed. The 100 people are lined up so that each person can see everyone in front of her, but not herself or anyone behind her. So, person number 100 can see #99-1, and person 1 can’t see anyone. They will be given time to plan a strategy, then lined up in this way and either a red hat or a blue hat put on each person’s head. Then, starting with person 100 and working forwards, each person will say either “red” or “blue.” The prize will be $1000 times the number of people who say the color of their own hat. The idea is to maximize the number of people who get their hat color right since each person gets the same amount of money in the end. Also, the organizers of the contest can listen in to the strategizing session and will try to minimize the amount of money they have to pay out, so definitely take into account worst-case scenarios when thinking about this problem.
Think! I’m about to discuss what I thought for my solution, though not my solution, exactly.
Now, I think I’ve read the puzzle right, and I think I can guarantee that 99 people will get a correct answer, with a 50% chance of all 100, though given that the organizers minimize the amount of money, it should be a 100% chance of 99.
This feels *way* too easy. Am I right?
August 1st, 2004 at 7:06 am
The best I could come up with off the top of my head was about half the people guessing correctly. But I have a dim recollection of being shown a very clever problem similar to this one which used Hamming Codes in its solution, so I’m uselessly fixating on that idea and no longer making any progress.
August 1st, 2004 at 8:55 am
Well, you can guarantee half the people getting it right by having every other person call out the colour of the hat in front of them. What are Hamming Codes?
August 1st, 2004 at 9:49 am
I had figured that the person at the back would count how many red & how many blue & would call out whichever color there was more of & then everyone could call out that color. That would give you at least 50 right. Then I tried to figure out if there was some good method to cue the group to change to the other color if it was to their advantage. Something like, if the group has changed color n times so far and if changing colors will improve the overall accuracy by at least n+1, then call out the other color. But I haven’t traced that through yet. I want to avoid everyone being wrong in the case where it alternates.
Hamming Codes are a very clever system to ensure accurate transmission of digital signals. Only certain patterns are allowed, and they are selected based on a nifty mathematical structure. In the other problem I was thinking of, the players compare the red/blue pattern of the hats they can see to the 0/1 pattern of these codes and use this information to decide what to call out.
August 1st, 2004 at 10:02 am
I was thinking of XORing. The first person gets the XOR of all the red =0, blue =1, then after that you subtract things you’ve seen/heard. It seems like sort of a pain, but not too impossible to do. Of course as soon as someone screws up, the whole thing is dead.
August 1st, 2004 at 11:05 am
Oooooh. That’s clever.
August 1st, 2004 at 10:16 pm
Thanks. But I wonder — it doesn’t seem like quite the right answer for a lateral thinking puzzle. I can’t see it not working, though. (Barring the problems with people making mistakes.) Of course once I thought of it, I couldn’t think of any other solution.
July 30th, 2005 at 9:31 am
For those who like to think:
“There are 31 logicians, each have a hat on. There is nothing known about the number of different colours of the hats. The logicians are allowed to look at each others hats but are not allowed to communicate in anyway at all. Now at periodic intervals a bell is rung when people who know the colour of their hat walk out of the room.
When the first bell is rung 4 logicians walk out of the room.
When the second bell is rung all logicians with red hats walk out.
When the third bell rung no one walks out.
When the fourth bell is rung atleast one logician walks out.
Now, sometime in the future (no idea if a bell(bells) have been rung since then) 2 logicians walk out and they have different coloured hats on.
So how many times was the bell rung??”