pageok
pageok
pageok
[Puzzleblogger Kevan Choset, August 29, 2005 at 12:21pm] Trackbacks
A Hat Problem:

There are a hundred people lined up on the steps of a stadium, each on a different step, all looking down toward the field so that they can see everyone in front of them, but can't see anyone behind them. Each person will be given either a red or black hat. We know nothing about the total number of red or black hats. Each person will not be able to see the color of his own hat (or the ones behind him), but will be able to see the colors of all the hats in front of him. Starting in the back, the last person will be asked what color hat he is wearing. If he guesses correctly, he will live; if he guesses incorrectly, he will be shot immediately. We will then proceed to the person second from the back, and so on, until we have reached the person on the bottom step. Each person will be able to hear what all the people behind him say, and will also be able to hear which people behind him were shot.

Before we begin this process, the 100 people may meet to discuss a strategy. They can plan whatever they want, but once the line-up begins, they may no longer confer. At each person's turn, he may only say "black" or "red," and no other words -- if he says anything else, all 100 people will be executed. He may also not use tone of voice, volume, etc., to convey any meaning -- this will be detected and they will all be shot.

What strategy will guarantee saving the maximum number of people? What is this number?

alkali (mail) (www):
Ubnless I am getting the rules wrong, the correct strategy is for each person to say the color of the hat in front of him, which saves 99 or 100 people depending on whether the last and next-to-last persons have the same or different color hats.
8.29.2005 1:30pm
Carl Sanders (mail):
You can guarantee at least 50 by the following:
Person 1 says the color of the person in front of him.
Person 2 says the color Person 1 says, and lives.
Person 3 says the color in front of him.
Person 4 says the color Person 3 said, and lives.
etc.

I would guess there might be a way to save more, but this is my first stab at the problem.
8.29.2005 1:30pm
Carl Sanders (mail):
alkali: The problem is that you can't simeltaneously say the color the person before you said and the color of the next persons hat if they are different. E.g. guy behind you sees you have a red hat, he says "red", now its your turn and the guy in front has a black hat. How do you save both of your lives?
8.29.2005 1:32pm
jallgor (mail):
Unless I read it too fast, your rules didn't remove the possibility of everyone telling each other what color their hat is during the pre-line up strategy session. Assuming that is no allowed the solution in the 2 posts above seem pretty effective.
8.29.2005 1:33pm
jallgor (mail):
Good point Carl. Those solutions suck :)
8.29.2005 1:35pm
Jeffrey King (mail) (www):
Each Person shouts the color of their hat if it is the same as the person in front of them, speaks normally if it is not. The first person has no indication of the color of his hat, so he is at most risk. Every other person will accurately speak their color, while communicating the next person's hat color. At most, there will be one death, assuming the first person guesses wrong.
8.29.2005 1:35pm
alkali (mail) (www):
Carl, you're quite right.

Thinking about this a little bit more, query whether this is an important part of the puzzle:

Each person will not be able to see the color of his own hat (or the ones behind him), but will be able to see the colors of all the hats in front of him.

Would the result be the same? It seems that way.
8.29.2005 1:36pm
Adam (mail) (www):
for the last guy, red means even number of red hats, black means even number of black hats. the rest have enough information to determine their hat.
8.29.2005 1:38pm
Jeffrey King (mail) (www):
Less effective solution than my last: the first person determines which color hat is most common. He says that color, and everyone else follows suit. This ensures at least 50% survive, potentially much more, assuming disparate distribution.
8.29.2005 1:40pm
claritas:
You can save 99 for sure, and the last person in line has a 50% shot.

Give black a value of 1, red a value of 0. The person in the back of the line adds up all the values in front of him. He then performs the calculation "X mod 2" where X is the sum of all the values. If that calculation gives 0, he says red, if it gives 1, he says black. This personhas a 50% chance of surviving: he'll survive if his hat matches the result of the calculation.

The next person in line now knows for sure what his hat says. He can add up all the values in front of him and do "Y mod 2." If the result of that calculation is the same as what the last person in line said, he knows his hat is red. If it's different, he knows his hat is black because it changed the sum for the person last in line.

Every person after the penultimate can perform the same procedure, because he will know every hat but his own, combining the ones he sees in front of him and the ones (correctly) guessed behind him. He can then perform the mod function and figure out whether his hat is black or red.
8.29.2005 1:40pm
Steve:
I think Adam has it right.
8.29.2005 1:41pm
deweber (mail):
Only one person has to go, I think. The highest person calls out black if he sees an even number of black hats and red if he sees an odd number(he has 1/2 chance). The next person can see the count of hats. Suppose the 1st person's call is black. If the second person sees an even number of black hats, the his hat must be red. If he sees an odd number, it must be black. The the next person. Assume black for the first call and black for the second(all other cases are similar). Now the third person expects an odd count of black hats if his is red and an even count if it is black. The rest follows by induction. QED
8.29.2005 1:44pm
Jeffrey King (mail) (www):
deweber,

Simple... Elegant... Well done.
8.29.2005 1:50pm
Paul Gowder (mail):
deweber: very well done indeed, FWIW I think he's got it. (If I had the faintest idea what mod meant, claritas might have the same?)
8.29.2005 1:53pm
Eduardo S:
Treat 'black' as 0 (zero) and 'red' as 1 (one).

The topmost 7 people all count the number of red hats below them, that is, of the 93 people starting with the lowermost one. They convert it to a 7-bit binary number (0..127). The topmost person calls out the MSB (most significant bit) of this number. Each of the next 6 people call out the next bits.

The lower 93 people now know the exact number of red hats. The first of those will count the people below, and guess his hat color by elimination. Repeat, subtracting one for each red hat called out by one of the 93.

The first 7 people each have a 50% chance of survival. The lower 93 have a 100% chance of survival, assuming they can count correctly -- which they have good incentive to do :-)
8.29.2005 1:55pm
Jeffrey King (mail) (www):
On second look deweber, it does not hold up. Consider the following sequence:

red, red, black, black, black, red, black

Your stradegy produces the following result:

alive, alive, alive, dead, alive, dead, undetermined.

This stradegy convays the needed information sort of, but comes across the same problem other solutions incur. If someone behind you sees an even number of black hats, and you see an odd number, you know you have a black hat, but you are obligated to say red.
8.29.2005 1:57pm
Carl Sanders (mail):
Good catch, claritas and deweber, should have thought of that one. BTW, X mod Y is a function that gives the remainder of X/y. So X mod 2 is 1 if X is odd, 0 if even, so both the solutions are the same.
8.29.2005 1:58pm
Zubon (mail) (www):
Paul: yes, that is the same answer. "x mod y" means "the remainder when you divide x by y," so 12 mod 7 is 5, 12 mod 6 is 0, 12 mod 5 is 2, 12 mod 4 is 0, and so on. Adam, claritas, and deweber have all phrased the same answer differently.

Nice work.
8.29.2005 1:59pm
Jeffrey King (mail) (www):
Eduardo, your solution seems to work, but your comment regarding 50% probability for the first seven is inaccurate. Without assurance of even distribution of the colors, the probability of the death of the first seven is unknown.
8.29.2005 2:01pm
Carl Sanders (mail):
Whoops, looked like I jumped the gun again. I like Eduardos solution now. I originally wanted to do some sort of binary thing, but couldn't get it figured out.
8.29.2005 2:01pm
Zubon (mail) (www):
We're posting too fast for replies not to overlap each other. Curses.

The variously stated solution works because everyone except the first person calls his/her own hat, not giving more information. The even/odd count on the first one is enough info because you can hear everyone else. That is, I know whether the number of black hats should be even because, when it gets to mee, I can tick off how many black hats have been called behind me, subtract that from the even/odd count, and give the right answer.
8.29.2005 2:04pm
Jeffrey King (mail) (www):
I still like my idea of communicating color by intonation. It does not seem to violate the rules, and ensures 99 percent survival.
8.29.2005 2:05pm
Zubon (mail) (www):
"He may also not use tone of voice, volume, etc., to convey any meaning -- this will be detected and they will all be shot."
8.29.2005 2:06pm
Jeffrey King (mail) (www):
Drat.
8.29.2005 2:07pm
informer:
A little aside on determining what the best possible solution is. The first person can not possibly have enough information to save him. After that the nth person can see (100 - n) hats and has those (100 - n) bits. Also, she knows the color of the (n - 1) hats above because she has heard each guess and knows whether each survided. That is 99 bits. The 1st person can convey an extra bit of information to the 2nd through 100th people. Everyone except the first should have complete information and can answer correctly. This analysis didn't help me work out the scheme, but it did lead me to answer the question of how many people can be saved.
8.29.2005 2:10pm
Jeffrey King (mail) (www):
informer,

but you need seven bits to communicate adequate information. Eduardo has the best solution so far, and informer's logic proves no more efficient solution exists by communicating in binary. I can't think of another method.
8.29.2005 2:15pm
BevD:
Here's an idea - look up at the bill of the hat.
8.29.2005 2:17pm
Jeffrey King (mail) (www):
BevD,

What do you think this is? Math class?
8.29.2005 2:18pm
jallgor (mail):
Was I wrong that none of the rules prevents everyone from just telling each other what color their hat is before the lineup? I know its not particulary clever and probably just a mistake in the rules but isn't that the best answer?
8.29.2005 2:22pm
Anonymous Coward:
Jeffrey - No, you don't need 7 bits. You only need one bit. The deweber/claritas solution (which are the same) give you all the info you need, since each person after the 1st will know all of the hats (assumning perfect memory, of courtse).
8.29.2005 2:25pm
cka3n (mail) (www):
Jallgor - they aren't given the hats until they are lined up, if I understand correctly.

I vote that 99 people live (going with Zubon and informer).
8.29.2005 2:29pm
Rebecca Oris Davidson (mail) (www):
The phrasing could have been more clear but I believe the hats are not distributed until everyone is in position. They "are" on the steps, and "will be given" hats. Strategy comes "before we begin this process," i.e., before anyone gets a hat.
8.29.2005 2:36pm
TLove (mail):
It seems to me the bit based schemes assume there will be only one more/fewer red hats than black. Picture the situation if randomly everyone is handed a red hat. Or there are 64 red hats and 36 black ones.

I think you can save 75% of the people. The first calls out the color of the hat in front, and prays his hat is the same. The second calls out their own hat color with perfect certainty. The third calls out the hat in front of him and prays, and so on.

50 live with certainty. 50 are taking and 50/50 risk, and one assumes around 25 would live. Thus, 75 live.
8.29.2005 2:37pm
BevD:
Take the hat off and LOOK at the colour. Geesh.
8.29.2005 2:43pm
erp (mail):


Unless I'm missing something, knowing the color of the hat in front or behind you gives you absolutely no information that would be useful in guessing what color your own hat is.

The information given in the problem is meant to throw us off the scent. Without more information, i.e., the number of black and red hats, the total number of hats and participants or a pattern of some kind, it comes down to each person having a fifty/fifty chance of guessing correctly, so if they all agree to pick the same color, there's an even chance that at least half of them will have guessed correctly saving 50 of the original group of 100.
8.29.2005 2:57pm
claritas:
erp and TLove,

The solution above saves an expected 99.5 people, regardless of the distribution.
8.29.2005 3:02pm
Michelle Dulak Thomson (mail):
TLove, I think claritas is right. It doesn't depend at all on the relative number of red and black hats. erp, I think it was stipulated that each person in line can see all the hats ahead of him. That's why they're on steps.
8.29.2005 3:09pm
Kerry:
Jeffrey,

Adam (informer, etc.) have the best solution by saving everyone but the first, who has a 50/50 chance.

I like Eduardo's solution (and it was along the lines of what I was attempting, i.e. using bits), but the even/odd solution is even simpler and much more effective.
8.29.2005 3:11pm
deweber (mail):
As remarked, claritas's and my solutions are the same(isomorphic for the mathematically inclined). Modulus 2 arithmetic is the same as odd/even. Claritas beat me by 4 minutes so precedence is his.
8.29.2005 3:14pm
Eduardo S:
I concede to claritas and deweber. Their solution is much cleaner and simpler than mine, and indeed guarantees 99 saves versus my 93. They posted while I was still composing mine; if I had seen theirs, I would not have submitted mine.

Good job. And thanks for the puzzle, Kevan.
8.29.2005 3:19pm
BevD:
And my solution saves everyone.
8.29.2005 3:28pm
FlavaFlay:
claritas and dewewber are right. Jeffery King, remember that the people in line have a perfect knowledge of those behind them by the time it is their turn because they know if those behind them have been shot. Also, only the first person uses his answer to give information to everyone else.

I also think that people may be overestimating the amount of memory required to fulfill the task. Suppose that the first person indicates that there is an even number of reds. The next person has to say, "Since there is an even number of reds, if there is an odd number of reds in front of me, I am red. Otherwise, I am black." If he says black, there is still an even number of reds. If he says red, there is now an odd number of reds. The people in line only have to remember if there is an odd or an even number of reds left in order to calculate what hat color they have. At each person's turn, they just have to reason the statement above, or the other scenario, which is, "Since there is an odd number of reds, if there is an even number of reds in front of me, I am red. Otherwise, I am black."
8.29.2005 3:30pm
Steve:
Yes, if you ignore the stipulation that no one can see the color of their own hat, it's very clever to suggest that they all look at the color of their own hat.
8.29.2005 3:31pm
Kristian (mail) (www):
Anyway, Start with a small number, say 2.

There are 4 possibilites:
rr
rb
br
bb

The top man see r or b. If he says the name in front, he has a 50% chance of living, the man in front a 100% chance. Thus the expected survivals over time is 1.5 out of 2, or 75%. This obviously could be exptrapolated for any even number. So lets call this the floor.

However, there is more information aviailible: the gunshots/lack of gunshots. Thus there should be a stragtegy that combines this, along with the accumulated bits of info, some sort of state machine?

So person 1 says red/black, then gets shot/not. That is 2 bits of info. There should be a way to ensure that 2 people guaranteed survive, with the third @ 50%.

Hmm...say the same color as the one behind you until you heat a shot?
Best case : everyone has the same color
Good Case : long runs of the same color
Bad case : short runs of the same color
Worst Case: alternating colors. (but, not if the even ones take one for the team...)

n-3 sees rrr, rrb, rbr, rbb, brr, brb, bbr, bbb says ?
n-2 sees rr, rb, br, bb, rr, rb, br, bb hears ? says ?
n-1 sees r b r b, r, b, r, b hears ? says ?
n hears ? says ?
8.29.2005 3:45pm
BevD:
Steve - you comment makes no sense. Nowhere is there a stipulation that you cannot take the hat off and look at it. If you take the stipulation that you cannot see the colour of your own hat literally, then you wouldn't be able to see the colour of the hat in front of you. You would be blind or in absolute darkness, in which case guessing is 50/50, just as it is without looking. The odds of choosing the right colour of hat are exactly the same as the odds in baccarat. You either beat the banker or you don't. A player can beat the banker 10 times in a row, but that doesn't mean the 11th time he will not beat the banker or for that matter beat the banker again.
8.29.2005 3:49pm
Jeffrey King (mail) (www):
The one bit of information... odd or even. Every one else adjusts their expectation based on results they have heard. 99 people are saved. Gotcha.

But to be accurate, the second part to the question was as to the number of people that can be guaranteed saved. Thus, the probability of the first's survival can not be added, so the answer to that is 99, not 99.5.

BevD, what if they put the hat on backwards? Or if the underside of the bill is green?
8.29.2005 3:51pm
Kevan Choset (mail):
The several people who suggested some sort of even/odd scheme are correct. Deweber describes the process using an even/odd count and Claritis explains it well using modular arithmetic. The two are equivalent.

What makes this interesting is that the first person does not provide all the information to everyone after him, but this information becomes enough when combined with the calls of everyone prior to the person whose turn it is. And, unlike schemes that have every other person saying what color the person in front of him has, this odd/even scheme does not require anyone other than the first person to state an incorrect color for himself. Thus, each person, by saying the correct color of his own hat, imparts important information to the following people.
8.29.2005 3:54pm
Mary Rosh:
There wouldn't be a problem if the people on the steps were armed as well.
8.29.2005 3:55pm
Michelle Dulak Thomson (mail):
BevD, which part of

Each person will not be able to see the color of his own hat

is unclear?
8.29.2005 3:56pm
David W (mail):
People don't need to know whether those behind them were shot or not. The following strategy guarantees that I will survive, provided that (a) everyone else follows the same strategy and (b) I am not at the very back of the line.

1. Immediately after the lineup, I count how many red hats I can see in front of me. If the number is even, my initial vote is black. If the number is odd, my initial vote is red. (I do this no matter where I am situated in the order).

2. Everytime someone behind me says red, I switch my vote.

3. When it is my turn to speak, I simply say my current vote, whatever it is.

Why is this strategy guaranteed to work for me (assuming I am not at the very back of the line)?

If my initial vote is the same as the person's behind me, my hat is black. Otherwise, my hat is red (if you don't see this, think a little more about how the initial votes were calculated).

Up until the person behind me speaks, whenever I switch my vote, the person behind me will also switch his vote.

So, when the person behind me says his vote, I know that if my vote (at the time) is the same as his, my hat is black, otherwise my hat is red.

Now suppose my hat is black. Consider the time when the person behind me votes. Then my vote, at that time, will be the same as the person behind me. There are two possibilities.

1. The person behind me says black. Then my vote stays the same and I say black.

2. The person behind me says red. Then my vote switches and I say black.

So I am correct both times. A similar argument shows that I am also correct if my hat is red. QED.
8.29.2005 4:05pm
Richa Avasthi (mail) (www):
Who says these hats have bills? They are not necessarily baseball caps. Maybe they're stocking caps.

Claritas is right: 99 people are guaranteed to be saved with his method.
8.29.2005 4:09pm
BevD:
To Michelle:

which part of taking the hat off and looking at it is confusing for you? Even if hysterical blindness overtakes you, the odds of guessing the correct colour hat are exactly the same - 50/50 that you'll guess correctly.
8.29.2005 4:26pm
Cody Hatch (mail) (www):
The problem is trivial if you have the luck (good or bad? I won't speculate) to be a telecoms engineer - the 100 people can be treated as a datagram. I'm far too late to contribute the first explanation, but I might as well try explaining it in my own terms.

Before hats are distributed, the people agree on color values and a parity scheme. For example: black = 0, red = 1, even parity.

The 1st person takes the role of the parity bit. He counts the number of red hats in front of him (which may be 0-99). If the result is odd, he announces red, thus making the total even. If the result is even, he announces black, thus keeping the total even. The 1st person has an unknown chance of survival, ranging from 0% to 100%, inclusive. Note that his survival conveys NO information, and thus the problems stipulation that gunshots are heard is not needed - a red herring to throw people off?

The 2nd person counts the number of red hats among the 98 hats in front of him, and adds the "parity bit" - the declared hat color of the 1st person. Since the 100 bits (ie, people) must be even, if the total is odd, then the 2nd person must have one of the red hats (since the 99 hats - of which his is one - plus the parity bit are even), and says red. If the total is even, then he must have one of the black hats, and says black. His survival is guarenteed, so again, the ability to hear gunshots isn't needed.

The Nth person counts the 100-N hats in front of him, looking for red hats. He then adds the parity bit plus all previous declared red hats. If the result is even, he says black (thus keeping the total even, as required by the even parity scheme). If the result is odd, he says red. Again his survival is guarenteed.

To know the color of your own hat, you need to know the color of all hats in front of you (trivial from visual observation), all hats behind you (trivial from listening), and some bit of information that lets you deduce your hat color from the color of all other hats. Parity allows this.
8.29.2005 4:31pm
Steve:
I cannot believe that people like BevD are so bored that they will troll a puzzle thread, of all things.
8.29.2005 4:47pm
Cityduck (mail):
Did I miss something? Did anyone read the rules?

"We know nothing about the total number of red or black hats."

So, that means that there could 99 red and 1 black, 50/50, 60/40, 70/30, 89/11, etc.

Which also means that the only bit of information discoverable and communicatable is which color is on more heads. And that bit of information is not sufficient to frame a strategy which guarantees you save everyone. All that can be guaranteed is that the first person guessing has the ability to save at least 50 lives. He just has to shout out the color that is the most predominant in the number of hats. And from then on, everyone else shouts out the same color. So if the break down is 70/30, and the person shouting first sees 70 black hats (or, if he's lucky, 69) he shouts out "Black." So does everyone else, end result: 70 saved. There is no way to guarantee that the other 30 are saved.
8.29.2005 5:23pm
Hayek:
I have another puzzle:

What kind of sick individual would set up a game where at least one participant has a 50/50 chance of death just to test the participants' ability to select the most efficient strategy??
8.29.2005 5:30pm
Kevan Choset (mail):
Cityduck,
Nothing in the two correct answers I point to above (here) relies on there being an equal number of red and black hats.
8.29.2005 5:30pm
Cityduck (mail):
Oops. I jumped the gun. The parity vote solutions are very convincing.
8.29.2005 5:31pm
Michelle Dulak Thomson (mail):
BevD, we are talking about a scenario in which trying to use a vocal inflection to convey information results in all 100 people being instantly shot. If the people setting up this thing say that I won't be able to see the color of my own hat, I think I'd take my word for it. If you'd take yours off to get a peek, I'd rather not be in the same line.

Cityduck,

Which also means that the only bit of information discoverable and communicatable is which color is on more heads.

Nope; you have the number of heads remaining and also the number black vs. red, which is why Claritis is right. And I think David W is also right, and his plan is a hell of a lot simpler to follow than Claritis'. It basically does the same thing, but without having to recalculate anything, just "switch" or "don't switch" each time untill they reach your place in line. Brilliant.
8.29.2005 5:43pm
Stephen Humphrey (mail) (www):
Notwithstanding BevD's trolling, the consensus solutions above are elegant and correct. So let's tweak the problem a bit. What is the strategy at the strategy meeting? Assume a typical distribution of intelligent/dumb, educated/uneducated, etc. How do you most simply explain the strategy to a common group of participants? How do you choose from among those participants which person to put at the top? What threshold do you set for resetting the initial even/odd information (what if, for example, the first five people are all shot?) The stipulation in the original problem that you can hear the result of each prior person's guess makes the problem highly deterministic, so what if it's changed to "you can hear what each person says but cannot hear if they are killed or not." That change makes you dependent on each person getting it right, so how does that change the way you pick the lineup? If you are the sadistic implementer of the game instead of one of its victims, would you consider putting everyone in the same color hat, just to tempt the first person to abandon the strategy? What would you promise the first person in order to encourage the right people to volunteer for that slot and to get the count right? What other questions or variations are interesting? Hmmmm? Please don't try to answer all these questions in one post, just pick a few and elucidate.
8.29.2005 5:46pm
BevD:
Why is it trolling to give the easiest and best solution to the problem? If people are too stupid to take the hat off and look at it, then they're too stupid to work out a mathmatical solution to the problem. Nowhere in the problem does it say you cannot take the hat off and look at it thus saving EVERYONE'S life.

To Michelle D.: you don't need vocal inflections, strategy or mathmatical formulas, you need one person to tell other people to take the hat off and look at it and stop trying to complicate the works. This is pretty much why I would prefer not to be in a line with you. Smart people know that the simplest solution is always the best. No doubt that's why the shooters probably prefer an AK 47 - it's so simple it always works.

p.s. Never take anyone's word for anything.
8.29.2005 6:32pm
irregular duty:
I think Cody Claritas and Deweber have the correct solution with one esception. As there solution is stated they can only be certain of saving 98 people, since their solutions all require the ability to see the colors of the hats in fron of you. The problem with the person in back has already been discussed, but the person in front cannot see any hats because there is no one in front of them. To save 99 people the person in front would need to remember to count the number of people saying either black or red. They could then extrapolate whether their own hat was red or black based on the information provided by the person at the top of the stadium steps and their own count.
8.29.2005 6:35pm
cathyf:
I think this thread needs this link: hatten ar din If you need an explanation, this will do: what the heck was that?


cathy :-)
8.29.2005 6:37pm
FlavaFlay:
Stephen,
I found this question interesting:

If you are the sadistic implementer of the game instead of one of its victims, would you consider putting everyone in the same color hat, just to tempt the first person to abandon the strategy?

Of course I would want the first person to betray the line up, but once the second person is killed, as long as the people in the line don't switch from thinking red is even to red is odd (or vice versa), the operation corrects itself. It doesn't matter if the first person lied or if the second person got it wrong. This reduces the problem to the first person deciding whether he dies or the next person dies. Still a sucky situation.

Things would be hairier if the people in line had no knowledge of the previous people's deaths.
8.29.2005 6:38pm
David Berke:
There is a potentially equally efficient solution to that imposed above, due to the manner in which the rules were proposed, depending on the import given to the word "immediately."
There was no rule that only one word could be said. Everyone could simply agree to say two words; the color of their hat, the color of the next hat. Assuming the first can say red-red or red-black faster than the other can pull the trigger (which is virtually guaranteed), the results are the same as the odd-even solution, and a lot easier to explain to a group of average citizens.
8.29.2005 6:40pm
FlavaFlay:
irregular duty,

The bottom person is guaranteed to live. Let me provide an example to illustrate why.

Suppose that the first person indicates that there are an even number of reds. If an even number of reds has been shouted by the previous line members, then the last person is black because if he is red, then there would be an odd number of reds at the end. If there is an odd number of reds, then the last person is red because if he was black, then there would be an odd number of reds at the end.

I hope that is a sufficient explanation.
8.29.2005 6:42pm
FlavaFlay:
Stephen,

Oops, I messed up. It is actually best for the other people in the line should update, based on the answer that the second person gave. It is irrelevant whether he was killed. I guess this means that you don't even need knowledge of anyone's death since the process will correct itself after a death.
8.29.2005 7:00pm
FlavaFlay:
... It is actually best for the other people in the line to update ...

Of course, assuming that the implementer has knowledge of the rule that the line up is going to use, it is still possible for the implementer to force the first person to choose whether he dies or the one in front of him.
8.29.2005 7:03pm
Matt Barr (mail) (www):
What strategy will guarantee saving the maximum number of people?


I think the word I emphasized from the question makes it harder than all that. In a mathematical world uninhabited by people, you could probably convince everyone that if they're the one in the back of the line, their chances will never improve over 50/50 no matter what, so they should say whatever color necessary to enable the strategy to save the other 99. But I doubt you could guarantee saving 99 people if you had to rely on the back of the line person to understand that and not grasp for divine intuition or other intervention when the gun's to his or her head. Maybe even more problematic is trying to get 99 people, especially the ones near the front of the line, to remember who's said what and who's been right and wrong while under extreme duress.

In our Lord of the Flies world, I think you could only guarantee saving more than 50 percent if you cheated. I know, you're not allowed to cheat. But let the person in back of the line say whatever he or she thinks is the color of their hat, but if they are going to say the same color as the hat in front of them, have them do it immediately; if they're going to say the other color, have them pause to "think about it" for a few seconds. I think you could count on the back person to do this more than you could count on them to give up their illusionary "control" over their guess in the odd/even scenario.

Proceeding, each person would say whatever color had been indicated by the person behind. If the color they're going to say is the same as the hat in front, do it immediately, if it's the other color, wait a few seconds first. If you get away with it (a big if), each person after the first is guaranteed to live, while no one has to try and calculate or remember anything other than what the person behind them says and when he said it.

This falls apart, of course, once it dawns on the executioner that everyone is guessing right, but under the "best" of circumstances I don't htink you could force anyone not to pause a few seconds to collect themselves before guessing, so I'm not sure this cheat could be detected, at least on the fly.
8.29.2005 7:22pm
Gil (mail) (www):
What's not clear to me is the best strategy to handle human error.

If the guy next-to-last (#99) guesses wrong, it could be because he screwed up, or it could be because the last guy (#100) screwed up (or decided to guess differently rather than cooperate, which is equivalent).

So, what should #98 do? Should he assume #99 got it wrong or should he assume #100 got it wrong? Or, should he assume the role of the last guy in line and start over, calling out a guess based purely on the hats in front of him? Or maybe they should wait until two (non-#100) guys get shot before assuming #100 was wrong and doing this?

In any case they should discuss this in advance so everyone will know how and when to reset their guesses.

What's the best error-correction strategy?
8.29.2005 7:51pm
Syd Henderson (mail):
The first person should say nothing at all, since that was not forbidden.
8.29.2005 7:54pm
Jack Jackson (mail):
One problem: How do we know whom the executioner will choose next? The executioner could choose any path, up or down a column, across a row, diagionally. Since we don't know the path of the executioner, we have a problem, because the problem doesn't say if we can see the color of the hats next to us, and we can't see the color of the hats behind us.

Also, why not have the first person call out the color of the majority of hats (and if an even number of both colors, take over the second person's function) and have the second person, wherever he is, call out the hat of the person in a particular spot (column A- row 6), and let others deduce outward from the centerpoint?

I think we have also ignored that each dead person gives us more information: the person who says black and is shot is a red spot (no pun intended). That fills in a blank. If the first person says black (meaning a majority of the hats are black) and is shot, we know he was red, and when thw second person tells us what the color of the center spot is (e.g., red) and is shot, we know he was black. Each remaining person's chance of survival increases as he plots out the map (i.e., as others die).
8.29.2005 10:11pm
Jack Jackson (mail):
Are the people arranged in a triangle with the last person as a point? Or is it a rhombus with the last person as one of the points? What if they are arranged elliptically?
8.29.2005 10:22pm
Cody Hatch (mail) (www):
"I think Cody Claritas and Deweber have the correct solution with one esception. As there solution is stated they can only be certain of saving 98 people, since their solutions all require the ability to see the colors of the hats in fron of you. The problem with the person in back has already been discussed, but the person in front cannot see any hats because there is no one in front of them. To save 99 people the person in front would need to remember to count the number of people saying either black or red. They could then extrapolate whether their own hat was red or black based on the information provided by the person at the top of the stadium steps and their own count."

This is incorrect; I believe you misunderstand the proposals. The system I described will ensure that N-1 people survive for any N > 0. For 100 people it will save 99 - however, every person so saved MUST count the calls from behind them. You imply that you can save 98 people without paying attention to calls from behind - this is untrue. If you only pay attention to the people in front, you will save no one - if you also count the number of times you've heard red (or black, depending on the system used), you will save 99. I can't think of any variation on the system that would work for persons 2 through N-1, but not for N. To put it another way, you must count the number of red hats on the people in front of you, but it's perfectly fine if the number of people in front of you happens to equal zero. This just ensures that the number of red hats in front of you will also equal zero. :-)

I also see people continue to claim that the first person in line has a 50% chance of living. This is NOT THE CASE, because we do not know the distribution of hats, nor do we know if they are randomly distributed. Smart experimenters could overhear the planning, and easily ensure that the first person in line would always die (or never die, if they were benevolent).

Finally, the questions about how to deal with hearing a gunshot are particularly interesting.

The systems being discussed are effectively analagous to parity check bits. This is an extremely basic form of error correction that ensures that a message can be recovered even after 1 single data bit is corrupted. In the context, the "corrupted" bit is the person currently be queried as to their hat color. They know the color of 98 of the 99 "data bits" (the 100th being the "parity bit"), and thus can use the parity bit to reconstruct the missing data bit. A single parity bit, however, cannot help if A.) Two or more data bits are corrupted, or B.) If the parity bit itself is corrupted.

In the case of A, the gunshots are the saving grace. Since one can hear both the stated hat color and immediate confirmation of the accuracy, it doesn't matter if people call out the wrong hat color - it will cause them to die, but all future people in line know to use the "other" color in their calculations. People in line making mistakes doesn't really impact the system - even if everyone failed to perform the parity calculation, any single person who counted correctly would live.

The case of B is far more difficult, however. If the first person calls out the wrong parity color, every single person will die if they follow the plan. Every single person will live if they say the opposite color than they would by following the plan. Hence, every gunshot behind you argues either that the 1st person and everyone NOT shot did the math wrong, or that every person shot has done the math wrong. Question - after how many gunshots would start assuming that the parity bit was wrong, rather than multiple data bits? Two? It also follows, incidentally, that the positions at the head of the line is the most important. A mistake by person 1 will cost several lives; a mistake by any other person will cost only one.

Also - if persons 2 and 3 make mistakes and are shot, person 4 might rationally conclude that the parity bit is wrong, and purposfully say the "wrong" color. This would save him if the parity bit was wrong - but since it isn't, he will die. Since the preceding three people have died, person 5 would be even more likely to "swap" colors - and so die. Since the preceding four people have died, person 6 would be even more likely again to "swap" colors - and so on.

Therefore, one final item in the plan should be to agree on the precise number of gunshots to wait before assuming the parity bit is incorrect. That way, people will be able to better tell if a gunshot is evidence for the parity bit being incorrect, or against.

Finally, if the number of people was high enough (and 100 might be high enough) the group should probably have 3 people act as parity bits. In the case of disagreement among the three parity bits, people would go with the two that agreed - this would lower the number certain to be saved if there are no mistakes from N-1 to N-3, but would greatly reduce the chance of a the most serious mistake, a corrupted parity bit.

(Hmm, perhaps I have overanalyzed this?)
8.29.2005 11:26pm
Jack Jackson:
(Hmm, perhaps I have overanalyzed this?)

No, I think you in part answered my questions. (Which I now realize were not dumb.)
8.30.2005 12:37am
FlavaFlay:
Cody,

I believe you are mistaken. A corrupted parity bit will result in an incorrect binary string, but it will not result in the death of every person.

I will just use a 5 person line up to give a few examples, since I feel I explained my point in a previous comment.

Suppose the line up is

R0 R1 B2 R3 R4

where R0 is the parity bit. Suppose the rule is to say red if there are an even number of reds in front of you. R0 should say black, but he says red (and saves himself). R1 looks and sees that there is an even number of reds in front of him, so he says black, yet he dies. R2 reasons that there must still be an even number of reds, since R1 did not say red. R2 sees two reds in front of him, so he says black. He survives. R3 reasons that there is still an even number of reds. He only sees one red (odd amount) in front of him, so he reasons that he must be red. The process continues, saving everyone else's life.

For any ordering of hats, this condition will hold: the second person will die, but the rest will live. The reason is that each person knows the correct state of all hats that come after him. This is a crucial condition. Of course, in a computer, a corrupt parity bit is no good because for any given bit, that bit does not know the correct state of bits that come after it.
8.30.2005 1:09am
Syd (mail):
My solution (that the first person should say nothing at all) would save everybody from being shot under the conditions of the problem. The first person only gets shot if he names the wrong color or if he or someone else conveys extra information. Nobody else gets shot because the game never proceeds beyond the first person.

If the executioners are stubborn enough, everyone will die of thirst, heatstroke or something else, but at least they won't be shot.
8.30.2005 1:11am
FlavaFlay:
Cody,

One other thing.

Suppose that the parity bit is correct, but someone in the line makes a mistake and is killed. That would mean that the next person would be killed also if he is following the proper calculations. But, the process would correct itself after that.

In fact, even if a couple people in a row incorrectly reason the answer, only the first person of those to give an incorrectly reasoned answer will die. Unfortunately, the first person to give a correctly reasoned answer given the previously incorrect information will die, but then the process will have corrected itself after that.

I suppose that a general rule in this hat scenario is that if a person dies for providing a properly calculated answer, the process can be assumed to have righted itself.
8.30.2005 1:25am
FlavaFlay:
Just so everyone is clear on the matter, in my examples, I assume that the only relevant information from the people that come before you is what they say not what the actual truth is.
8.30.2005 1:29am
Gil (mail) (www):
FlavaFlay,

I think you're wrong. If all of the hats were red, and the parity bit was wrong, then everyone (after the first person) following your procedure would say "Black" and die.

The pattern wouldn't correct itself until there was a black hat.

Since the worst-case-scenario is so bad, I think there needs to be a better solution to restart the process, and I think that everyone needs to agree in advance for it to work. But, I could be wrong about that, and I'm not sure when the best time to restart would be.
8.30.2005 2:12am
Gil (mail) (www):
Also,

I think that the 100 people should conspire to escape from their captors rather than go along with the scheme.

How can they trust that people who would shoot them for mis-identifying their hat color can be relied upon to not shoot them if they are correct?

They can't "guarantee" that anyone will survive!

But, better to die striving for liberty than to live as a hat-terrorist appeaser!
8.30.2005 2:27am
FlavaFlay:
Gil,

Let's see what happens if everyone is red.

R0 R1 R2 R3 R4

R0 is supposed to say red to indicate red is even. R0 says black. R1 thinks that there are an odd number of reds, and sees an odd number of reds in front of him. He says black and dies. R2, who hears black, continues to think that there is an odd number of reds. R2 sees an even number of reds in front of him. He says red and lives. Do you wish for me to continue the example to demonstrate that everyone else lives?
8.30.2005 2:37am
Gil (mail) (www):
No, I see. I had people switching their guess because of the shots that indicated that the person behind them was wrong. It seems odd (no pun intended) to guess based on the wrong declaration of your predecessor, but it does seem to correct the pattern.
8.30.2005 3:19am
treefroggy (mail):
Since I carry concealed, you just shoot the gremlin who is threatening to shoot those in line, thus saving everyone.
8.30.2005 12:39pm
Cody Hatch (mail) (www):
FlavaFlav: Hmm, you're right. I messed up my last calculation. I thought you'd need to hear gunfire to correct for a bad parity bit, but that isn't the case.

In fact, the ability to hear gunfire really doesn't seem to be very useful at all...
8.30.2005 4:32pm
duglmac (mail):

I think the real interesting question here is, after conference with the other 99, and deciding that 99 can be guaranteed life, how does the one poor sucker in the back of the line feel about climbing back up to take his place with the 50% chance?
8.30.2005 7:07pm
Dr.T (mail):
Too many of the commenters (and, apparently, Kevan himself) assume a 50:50 distribution of hat colors. No such assumption can be made based on the stated problem. This negates many of the proposed strategies. I make only one assumption based on the stated problem: the stadium has 100 rows of seats. Thus, the 50th person can only see the 50 persons below him.

In this scenario, I see no way to guarantee minimal deaths. There are too many hat distribution possibilities. For example, suppose person 1 notes that all 99 persons he sees below him are wearing black hats. He should say his hat is black, and so should every other person. That would result in at most one death (if #1's hat broke the pattern and was red). Suppose instead that he sees a pattern where only persons in odd numbered rows wear black hats. Again, he should say black, which will probably save him and, if everyone thinks just as logically, everyone else.

What happens if hat colors are randomly distributed? Initially, everyone has a 50:50 chance of being shot. If persons lower down recognize the pattern and keep a running tally, they may slightly improve their survival rate (and thus the survival rate of the group). However, this does not require a group-based strategy. What if there is a 2:1 ratio of black to red hats, and the distribution is random. Person 1 should say black, as should person 2, person 3, etc. One third of persons will be shot, although again, if the last few persons deduce the pattern (everyone choosing black, one third being shot), then they might improve their odds of surviving by keeping tally and changing their response to red in the unlikely case that there is a clustering of red hats at the end.

What about strange patterns of distribution such as 10 black hats, 10 red hats, 20 black hats, 20 red hats, and then a pattern of red-red-black for the last 20 persons. How does one guarantee minimal deaths when the pattern will not be obvious to the persons seated lower down? In this type of scenario, the 1st (highest) person may have better survival odds than the 100th person (who supposedly has the most information).

Thus, I can see no benefit from a group strategy except to tell everyone to base his hat color guess on any recognized distribution patterns and then on probability theory.
8.31.2005 12:01am
Syd (mail):
Kevan's not assuming there is a 50-50 distribution. Claritas's parity solution works with any distribution at all.
8.31.2005 1:25am
FlavaFlay:
Dr. T,

There are no distribution assumptions. There are a couple of mathematical facts that will help to understand the situation.

An odd number plus an odd number is an even number.
An even number plus an even number is an even number.
An odd number plus an even number is an odd number.

Include zero in the set of even numbers, even though it actually isn't.

There is either an odd amount of red hats, or there is an even amount in front of the first person. This is because there are 99 (an odd number) people.

The first person indicates whether there is an even number of red hats in front of him.

The rest of the people calculate how many times someone said red behind them (not counting the first person). They also count the number of reds in front of them.

Suppose the first person indicates red happens an even number (hereafter abbr. as E#) of times.

When it is my turn, if there were an odd number (O#) of reds behind me and an E# in front, I am red, since an O# plus an E# plus 1 (since I am red) is even (the even number of reds indicated by the first person).

If there were an O# behind me and an O# in front, I am black, because O# plus O# plus zero (since I am black) is even.

If there were an E# behind me and an E# in front, I am black, because E# plus E# plus zero (since I am black) is even.

If there were an E# behind me and an O# in front, I am red, because E# plus O# plus 1 (since I am red) is even.

There are four additional cases for when the first person indicates that there is an odd number of reds. I will only give one of the cases.

If there were an O# behind me and an E# in front, I am black, because O# plus #E plus zero is odd.

Hopefully, this explanation leaves little doubt that the solution indicated by claritas, deweber, and Kevan is the correct one.
8.31.2005 2:54am
J. Tooby (mail):
Here is the best I can think of, while dodging a paper I should be drafting.

Each person follows the following rule:

Here is a strategy that will save 66 for sure, with the first person and 33 others having a 50:50 chance of living (a mean of 17 dying). 83 live, on average.

Strategy: First person: If the next two people have the same colored hat, say the color of that hat. If the next two people have different colored hats, say a different color from the hat of the person two down from you. The next person in line can see the color of the next person's hat, and will know by the statement of the person behind him whether his hat is the same color as the next person. (That is, if he sees the next person's hat is red, but the person behind him says blue, that signals to him that the two hats are different colors, and his hat is different from red, i.e., he is wearing a blue hat. If the person behind him says red, and the next person is wearing red, then he must be wearing red, too.) This tells him the color of his hat. He then says his hat's color, and is not killed. This tells the next person the color of his hat -- because if person 1 says x, and person 2 says x, then this tells person 3 his hat is x. If person 1 says x, and person 2 says y, then this tells person 3 his hat is x.

Then person 4 is in the dark, with the same starting position as person 1. He restarts the cycle. So, 34 people are in the first position, with a 50% chance of dying. The other 66 people can deduce correctly the color of their own hats.

Motivationally, no individual is required to commit suicide to save others. Every 3rd person is in the dark, but by using their statement to communicate the color of the next two at no added cost to themselves, they save 2 lives.

Off the top of my head, I can't think of a better strategy.
8.31.2005 4:41am
J. Tooby (mail):
Oops, skimming too fast I misread: Adam's, Claritas's, et al.s solution does work, and better than mine by 16.5.
8.31.2005 4:52am
Paul doson (mail) (www):
Highly crafty and intriguing article. It highlights the intricate relationship between the subject and its essence. It is highly informative.
John
8.31.2005 6:09am
FlavaFlay:
Ack, comment spam. I hope it gets deleted.

Anyway, I was rereading my last post, and I realized that a factual error is there because of careless cutting of text.

See this paragraph:

"There is either an odd amount of red hats, or there is an even amount in front of the first person. This is because there are 99 (an odd number) people."

Whether there is an even or an odd amount of reds has nothing to do with there being an odd number of people in front of the first person.

The text that I cut out related to the fact that if there is an even number of reds, there is an odd number of blacks, or vice versa.
8.31.2005 6:47am
FlavaFlay:
J. Tooby,

I'm afraid that your scheme doesn't work. Let's just look at a three person long section. The first person doesn't matter, since he is only giving information to the next people. So, the next two can either be the same or different. I will stipulate that they can either be RR or RB, since the other situations are essentially the same.

Situation #1:
The first person looks at RR and says R, since he is supposed to say the same as both of their colors. The second person says R.

Situation #2:
The first person looks at RB and says R, since he is supposed to say the opposite of the color 2 down from him. The second person says R.

As you can see, there actually is no situation in which "person 1 says x, and person 2 says y."

You have unwittingly suggested a scheme that merely names the color of the hat in front of you.

In both situations, no helpful information is imparted to the person two down from the first person.
8.31.2005 7:02am
Ann (mail) (www):
You can save everyone, and you only need to say two words. The key is here:

"Before we begin this process, the 100 people may meet to discuss a strategy. They can plan whatever they want, but once the line-up begins, they may no longer confer."

In the beginning, when they confer, they are not lined up yet. So you simply point to one side and say "black" and the other side and say "red". Everyone then sorts eachother out into groups with the help of the others--they can either stay silent and point their neighbor in the right direction or tell them that they belong with the other color. With 100 people, it would take all of about 5 minutes to get everyone sorted.
9.1.2005 11:56am
David W (mail):
Suppose we change the rules so that there are three possible colors.

Specifically:

1. there are three possible colored hats: red, green and black. As before, we know nothing about the distribution of the hats. Any number of reds, greens and blacks are posible, as long as they add up to 100.

2. Each person can say "red", "green" or "black", or can say nothing. Anyone not saying the correct color of their hat gets shot (so if you choose to say nothing, you are guaranteeing that you die).

All the other rules are identical to the two-color problem.

Amazingly, there is still a way to guarantee 99 people out of 100 survive. Can anyone find it?
9.1.2005 1:51pm
David W (mail):
Ann, they have to meet to decide their strategy before they are given their hats.
9.1.2005 1:55pm
FlavaFlay:
David W,

I think i have the solution to if there are three hats. The key is that there must be either one color that has an odd number of hats, or all colors have an odd number of hats. This is because there is an odd number of hats in front of the first person.

In the event that all hats are odd numbered, the first person says nothing. In all other cases, the first person says the color that appears an odd number of times.
9.1.2005 9:48pm
FlavaFlay:
David W,

If there were, on the other hand, an even number of hats in front of the first person, there must either be one color that has an even number of hats, or all colors have an even number of hats. In this case, the first person either says nothing, or says the color that is the only one that is even.
9.1.2005 10:00pm