I want to make your heads a'splode

[flexagon]

WAKE UP, SLEEPY NEURONS, IT'S BRAINTEASER TIME.

This one is fun to think about, yet has one of the stupidest setups I've ever heard: n people are buried in the sand up to their necks, forming a queue, and each of them is wearing either a red or a blue hat. Each of them can see the hats of all the people in front of them (from which you can infer that they're buried on a slope, and a concave slope at that... but I digress) but no person can see his or her own hat or the hats of the people behind them. You don't know anything about the distribution of red or blue hats... they could be all blue, all red, or chosen by an intelligent and malevolent force.

Now, they get to do something. Starting with the person in the back of the queue, each person can say "red" or "blue" once. No tricks here. The guy in back says a word, then the person in front of him, then the person in front of hat person, etc.

Here is the trick: these people get to strategize before docilely allowing themselves to be buried in the sand. If the idea is for the maximum number of people to say the color of the hat on their own head, what is their strategy and how well can they do? They are not allowed to encode more than one bit of information in their word using tone, rhythm or any other method, as was my first idea: "blooooo-oo-oo-uh-OO-ooh-oo". Strictly one bit per utterance. :)

To guarantee getting 50% right, the people could work in pairs. One person simply says the color of the hat right in front of them, and then the next person says that color. That way, you get a minimum of 50%, and if the distribution is random you get 75%. Not bad for an initial solution.

I find this much easier to think about if each person either has a hat or doesn't, as opposed to having a red or a blue hat. The people can then say "yes" or "no". Mathematically, it's still the same puzzle, but now there's something obvious to focus on.

Lastly, we can assume that nobody panicks from being buried in the sand, nobody is too hungry to think straight, nobody ever messes up the strategy in their head or simply blurts out the wrong thing, nobody's glasses fall off so that they can't see the hats in front of them, there are no shills secretly taking payments from the malevolent intelligence in return for lying, etc. Also, there are no equations in this one, so I don't think I've made any dumb typos this time.

Edit: someone got it. So don't read the comments if you don't want the answer.

Comments

[bluechromis.livejournal.com]

Hmm. Good puzzle. The back guy is fucked, well, 50% fucked. :) Your little hint about yes or no rang a bell...the parity of the remaining hats can be communicated if they decide which color represents 1 and which represents 0 beforehand. The back person starts off by saying 1 or zero depending on whether there was an even or odd number of 1-value hats in front of him (1 for odd, 0 for even, then the next person adds that number to the number of 1-value hats in front of him. If it's even then his hat is 0 value because it is not a part of that sum, if it's odd, then his hat has 1 value because it is part of that sum. So everyone but the last guy will get it right.

Er, that wasn't very clear at all, I'm sure you've got the real explanation.

[flexagon]

Clever girl! That's what HLM and I came up with too, after a few minutes of discussion. Before that we had a slickish trick (I thought) where the little guys worked in 3s, and the rearmost one did an XOR. Then finally we (where we==HLM) realized we could extend it using the parity trick.

I'm too sleepy to explain it any more clearly than you did, so any confused readers may be 50% fucked just like the last doozer in line. Sucks to be you, future readers.

Zzzzzzz...