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?
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.
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.
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.
Simple... Elegant... Well done.
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 :-)
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.
Nice work.
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.
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.
What do you think this is? Math class?
I vote that 99 people live (going with Zubon and informer).
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.
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.
The solution above saves an expected 99.5 people, regardless of the distribution.
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.
Good job. And thanks for the puzzle, Kevan.
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."
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 ?
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?
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.
Each person will not be able to see the color of his own hat
is unclear?
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.
Claritas is right: 99 people are guaranteed to be saved with his method.
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.
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.
"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.
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??
Nothing in the two correct answers I point to above (here) relies on there being an equal number of red and black hats.
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.
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.
cathy :-)
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.
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.
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.
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.
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.
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.
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?
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).
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?)
No, I think you in part answered my questions. (Which I now realize were not dumb.)
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.
If the executioners are stubborn enough, everyone will die of thirst, heatstroke or something else, but at least they won't be shot.
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.
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.
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!
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?
In fact, the ability to hear gunfire really doesn't seem to be very useful at all...
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?
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.
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.
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.
John
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.
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.
"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.
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?
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.
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.