You are in a group of 10 prisoners who are captured and rounded up by a crooked, psycho cop.
He decides to execute the lot of you, but to play a game to give some of you a chance to live.
He tells you his plan to incite a little sadistic fear. His plan is to put either a blue or red
hat on each of your heads, and then he will ask each person what color his hat is. If they guess
correctly, they may leave freely. Otherwise, BANG! he shoots them dead.
Furthermore, the psycho cop will first line all of you up, single file, all facing in one direction,
such that each person is facing the next prisoner's back. Thus, every criminal will be
able to see the hats of every one in front of them, but not their own hat or anyone
behind them. He will ask each of you in order, starting from the back of the line
and moving forward.
After telling you his sadistic plan, he leaves the room to get the hats, which could be in
any combination of red and blue, and in any order. They could all be red, or they could all be blue,
or any combination in between. During this time, you, the prisoners, have the chance to discuss
and try to come up with some sort of communication system, to help each other out in guessing
your hat colors. You happen to be very generous and humanitarian prisoners, or perhaps you have a
hive mind, such that you are not interested in your individual survival, only in ensuring
that as many of you survive as possible.
What communication/code system can you come up with for the prisoners to use,
to save the most prisoners? How many prisoners would be saved, on average and
in the worst case, using your system?
Note that "Red" and "Blue" are the ONLY two words that you can each say, and only once.
You can't say them in any funny voices or stamp your feet, etc.
Thus, you may ONLY give these two distinct outputs.
If you attempt anything funny otherwise, the cop will just kill all of you.
