100 Hats Puzzle

1. They shall be lined up from shortest in front to tallest in back.
2. All shall face the person in front.
3. A black or white hat shall be placed on each man.
4. In order, starting with the man last in line, each shall be asked the color of his hat.
5. The king shall note each answer and execute everybody who got the wrong answer after all 100 prisoners have tendered their answers.
6. Exchanging of information outside of the white/black answers is strictly forbidden and will result in everybody being killed if anybody is caught.
7. The king shall give the prisoners some time to confer on a strategy before the line up.

Quote: BruceZ

Show Spoiler

All lives can be saved. The last prisoner says white if he sees an even number of white hats, and black if he sees an odd number. Then each successive prisoner can deduce the color of his own hat based on whether he sees an even or odd number along with the colors that were announced behind him. For example, if the second to the last prisoner sees the same parity (even/odd) as the last prisoner, then he knows his hat is black, otherwise it is white. His announcement then informs the next prisoner whether he sees an even or odd number, white meaning the parity flips from the last guy, and black meaning it stays the same. Each successive announcement of white flips the parity while black keeps it the same. Each prisoner then keeps track of the parity, and if he sees the same parity, he knows his hat is black, otherwise it is white.

Quote: Wizard

Quote: BruceZ

Show Spoiler

All lives can be saved. The last prisoner says white if he sees an even number of white hats, and black if he sees an odd number. Then each successive prisoner can deduce the color of his own hat based on whether he sees an even or odd number along with the colors that were announced behind him. For example, if the second to the last prisoner sees the same parity (even/odd) as the last prisoner, then he knows his hat is black, otherwise it is white. His announcement then informs the next prisoner whether he sees an even or odd number, white meaning the parity flips from the last guy, and black meaning it stays the same. Each successive announcement of white flips the parity while black keeps it the same. Each prisoner then keeps track of the parity, and if he sees the same parity, he knows his hat is black, otherwise it is white.

Response

You say 100 lives can be saved. However, isn't there only a 50/50 chance the first person to declare is right? Remember, he is stated the color of his own hat.

Quote: Wizard

Let me make a couple things clear.

1. The king will note what everybody said and whether it correctly matched the color of his own hat. After all 100 people are done, he will separate those who got it wrong and execute them. Alternatively, I could have said he silently kills people who made a wrong guess immediately.

2. It is correct I did not state any distribution of colors. They could each be determined by a coin flip, the whim of the king, or anything.

Quote: BleedingChipsSlowly

Show Spoiler

Maximum guaranteed saves is 31. Each man gives the majority color he can see in front of him or else repeats the color given by the man behind him.

Quote: andysif

Quote: BleedingChipsSlowly

Show Spoiler

Maximum guaranteed saves is 31. Each man gives the majority color he can see in front of him or else repeats the color given by the man behind him.

your number is obviously understated.

Show Spoiler

Under the worst case, you can make 50 groups of 2 and the first guy can call out the 2nd person's color. That would be 50 correct answers, plus those lucky groups that both persons happen to have the same color

Quote: BruceZ

Show Spoiler

In that case my method will save all 100 with probability 1/2, and 99 with probability 1/2, for an average of 99.5. The distribution of colors is irrelevant.

Quote: BleedingChipsSlowly

Quote: andysif

Quote: BleedingChipsSlowly

Show Spoiler

Maximum guaranteed saves is 31. Each man gives the majority color he can see in front of him or else repeats the color given by the man behind him.

your number is obviously understated.

Show Spoiler

Under the worst case, you can make 50 groups of 2 and the first guy can call out the 2nd person's color. That would be 50 correct answers, plus those lucky groups that both persons happen to have the same color

My number is based on a spreadsheet simulation, and my maximum guaranteed number is the lowest I saw after banging the recalc button for a while. Your solution is much better.

Quote: Wizard

Let it be known that BruceZ has claimed the prize but please keep trying for benefit of the honor of figuring it out.

Quote: Wizard

Wiz answer to 100 hat question #2

Here is what the plan could have been before the hint. Through this there is just one mass exodus. Once that happens, that is it, you don't need the rest of the time.
1. Everyone should agree that if you see all white hats, then leave and nobody else. This would work if the split were 1 black and 99 white.
2. If after a brief pause, nobody leaves, then there is at least 2 black hats.
3. After this pause, if you see exactly one black hat, then leave. This would work if the split were 2 black and 98 white.
4. If after another brief pause, nobody leaves, then there is at least 3 black hats.
5. After this pause, if you see exactly two black hats, then leave. This would work if the split were 3 black and 97 white.
...

You keep repeating this process until there is an exodus. It will require some method of marking how long a "pause" is. Where it breaks down is if everybody has a white hat. Everyone will leave and everyone will have been wrong.

So, the hint of at least one black hat removes that possibility and makes the challenge winnable.

I'd like to add that if I'm right I'd like to re-give my prize back to the next person to get this one correct.

Quote: Wizard

Quote: BruceZ

Show Spoiler

In that case my method will save all 100 with probability 1/2, and 99 with probability 1/2, for an average of 99.5. The distribution of colors is irrelevant.

Response

Correct!!! You win the prize.

Let it be known that BruceZ has claimed the prize but please keep trying for benefit of the honor of figuring it out.

Quote: Ayecarumba

But what if...

Using this strategy, if all the hats are black, doesn't everyone say "white" and subsequently die?

Quote: BruceZ

I specified that there were 50 black hats assigned. You may have read a version of my post where I left that out, but they cannot execute your algorithm even when they can each see black hats and still be logical. Yet they can execute it and be logical when the king tells them that there is at least 1 black hat, something that they already knew! Question 2 then is what specifically did the king tell them that they didn't already know?

Quote: MathExtremist

If each prisoner can actually see all 99 other hats, each prisoner therefore sees either 49 or 50 black hats and knows "at least one hat is black".

Quote: MathExtremist

However, if that solution is considered "communicating information about the color of a hat" then this approach won't work. If so, what kinds of actions do not constitute "communicating" and are permissible?

Quote: Wizard

Wiz answer to 100 hat question #2

Here is what the plan could have been before the hint. Through this there is just one mass exodus. Once that happens, that is it, you don't need the rest of the time.
1. Everyone should agree that if you see all white hats, then leave and nobody else. This would work if the split were 1 black and 99 white.
2. If after a brief pause, nobody leaves, then there is at least 2 black hats.
3. After this pause, if you see exactly one black hat, then leave. This would work if the split were 2 black and 98 white.
4. If after another brief pause, nobody leaves, then there is at least 3 black hats.
5. After this pause, if you see exactly two black hats, then leave. This would work if the split were 3 black and 97 white.
...

You keep repeating this process until there is an exodus. It will require some method of marking how long a "pause" is. Where it breaks down is if everybody has a white hat. Everyone will leave and everyone will have been wrong.

So, the hint of at least one black hat removes that possibility and makes the challenge winnable.

Quote: MathExtremist

If each prisoner can actually see all 99 other hats, each prisoner therefore sees either 49 or 50 black hats and knows "at least one hat is black". I'm not sure what the king told them they didn't already know, unless there's a language trick I'm missing in here somewhere because it's almost midnight and I've had a few drinks. But I don't think it's impossible without the added disclosure by the king:

Show Spoiler

Everyone stands in a circle, facing inward. One at a time starting with the shortest (or some other selected "first"), each prisoner goes to stand behind someone wearing a white hat if they can, otherwise just stand still. Keep going around the circle until it's been 101 prisoners since the last time someone moved. When everyone has stopped, there will be some short rows of people starting with N white hats and ending in one black hat, and other singleton black hats standing around. The singletons and the end of each row leave the room all at once, everyone else stays. This approach wouldn't work for the edge case of all white hats -- and that might be what the "at least one" hint would have provided if the prisoners hadn't already seen all the hats -- but because they can all see at least 49 black hats while they're conferring, everyone would agree that this approach would work and nobody would think it's impossible.

However, if that solution is considered "communicating information about the color of a hat" then this approach won't work. If so, what kinds of actions do not constitute "communicating" and are permissible?

Quote: andysif

Quote: Wizard

Wiz answer to 100 hat question #2

Here is what the plan could have been before the hint. Through this there is just one mass exodus. Once that happens, that is it, you don't need the rest of the time.
1. Everyone should agree that if you see all white hats, then leave and nobody else. This would work if the split were 1 black and 99 white.
2. If after a brief pause, nobody leaves, then there is at least 2 black hats.
3. After this pause, if you see exactly one black hat, then leave. This would work if the split were 2 black and 98 white.
4. If after another brief pause, nobody leaves, then there is at least 3 black hats.
5. After this pause, if you see exactly two black hats, then leave. This would work if the split were 3 black and 97 white.
...

You keep repeating this process until there is an exodus. It will require some method of marking how long a "pause" is. Where it breaks down is if everybody has a white hat. Everyone will leave and everyone will have been wrong.

So, the hint of at least one black hat removes that possibility and makes the challenge winnable.

Show Spoiler

This my work for small number of black, but when you got say 48 blacks, it may be difficult to decide after that "long pause" is it up to 47 or 48 or 49 that we are talking about. Way around it is to use an announcer, yelling 1,2,3 .... but if that is not allowed, then I think your method doesn't work

Quote: andysif

Quote: MathExtremist

If each prisoner can actually see all 99 other hats, each prisoner therefore sees either 49 or 50 black hats and knows "at least one hat is black". I'm not sure what the king told them they didn't already know, unless there's a language trick I'm missing in here somewhere because it's almost midnight and I've had a few drinks. But I don't think it's impossible without the added disclosure by the king:

Show Spoiler

Everyone stands in a circle, facing inward. One at a time starting with the shortest (or some other selected "first"), each prisoner goes to stand behind someone wearing a white hat if they can, otherwise just stand still. Keep going around the circle until it's been 101 prisoners since the last time someone moved. When everyone has stopped, there will be some short rows of people starting with N white hats and ending in one black hat, and other singleton black hats standing around. The singletons and the end of each row leave the room all at once, everyone else stays. This approach wouldn't work for the edge case of all white hats -- and that might be what the "at least one" hint would have provided if the prisoners hadn't already seen all the hats -- but because they can all see at least 49 black hats while they're conferring, everyone would agree that this approach would work and nobody would think it's impossible.

However, if that solution is considered "communicating information about the color of a hat" then this approach won't work. If so, what kinds of actions do not constitute "communicating" and are permissible?

I have that concern too. I have kind of figure out a way but it essentially boils down to "communicating information about the color of a hat"

Show Spoiler

everyone do this in turn
1. if you see other blacks, leave the group.

Quote: BruceZ

Quote: andysif

Quote: Wizard

Wiz answer to 100 hat question #2

Here is what the plan could have been before the hint. Through this there is just one mass exodus. Once that happens, that is it, you don't need the rest of the time.
1. Everyone should agree that if you see all white hats, then leave and nobody else. This would work if the split were 1 black and 99 white.
2. If after a brief pause, nobody leaves, then there is at least 2 black hats.
3. After this pause, if you see exactly one black hat, then leave. This would work if the split were 2 black and 98 white.
4. If after another brief pause, nobody leaves, then there is at least 3 black hats.
5. After this pause, if you see exactly two black hats, then leave. This would work if the split were 3 black and 97 white.
...

You keep repeating this process until there is an exodus. It will require some method of marking how long a "pause" is. Where it breaks down is if everybody has a white hat. Everyone will leave and everyone will have been wrong.

So, the hint of at least one black hat removes that possibility and makes the challenge winnable.

Show Spoiler

This my work for small number of black, but when you got say 48 blacks, it may be difficult to decide after that "long pause" is it up to 47 or 48 or 49 that we are talking about. Way around it is to use an announcer, yelling 1,2,3 .... but if that is not allowed, then I think your method doesn't work

Show Spoiler

That's not a problem as they could make the time limit say 1 minute to act, but don't make a decision on the action of others until after 5 minutes. So there's some "hysteresis" between acting and deciding so we don't need to be able to measure time intervals precisely. Anyone can tell the difference between 1 minute and 5 minutes. You'd have to make those time intervals get progressively longer though so you can know when the decision phase stops and the next action phase starts. That wasn't the point of the problem, and I could just as easily said there was a clock in the room, but that would have given things away too much, or they could allow someone to be the official time keeper by counting, but then that's an action. The Wizard's algorithm is right for question 1, it's just that it can't start logically until after the hint.

Quote: MathExtremist

If each prisoner can actually see all 99 other hats, each prisoner therefore sees either 49 or 50 black hats and knows "at least one hat is black". I'm not sure what the king told them they didn't already know, unless there's a language trick I'm missing in here somewhere because it's almost midnight and I've had a few drinks. But I don't think it's impossible without the added disclosure by the king:

Show Spoiler

Everyone stands in a circle, facing inward. One at a time starting with the shortest (or some other selected "first"), each prisoner goes to stand behind someone wearing a white hat if they can, otherwise just stand still. Keep going around the circle until it's been 101 prisoners since the last time someone moved. When everyone has stopped, there will be some short rows of people starting with N white hats and ending in one black hat, and other singleton black hats standing around. The singletons and the end of each row leave the room all at once, everyone else stays. This approach wouldn't work for the edge case of all white hats -- and that might be what the "at least one" hint would have provided if the prisoners hadn't already seen all the hats -- but because they can all see at least 49 black hats while they're conferring, everyone would agree that this approach would work and nobody would think it's impossible.

However, if that solution is considered "communicating information about the color of a hat" then this approach won't work. If so, what kinds of actions do not constitute "communicating" and are permissible?

I have that concern too. I have kind of figure out a way but it essentially boils down to "communicating information about the color of a hat"

Show Spoiler

everyone do this in turn
1. if you see other blacks, leave the group.

Quote: andysif

If you leave and you're white, everyone dies.

Quote: beachbumbabs

If you leave and you're white, everyone dies.

Well, your last caveat kills my solution. I figured you could go in and out as much as you wanted during the 24 hours as long as, when the 24 hours were up, you were in the correct area by color, which your original rules implied could be done. If so, it becomes a "goose and fox" rowboat problem. But apparently not.

Quote: beachbumbabs

Quote: andysif

Just don't leave the room. go to the east side or the back or whatever.

Quote: beachbumbabs

My alternate solution to the Wiz's problem is:

Show Spoiler

The last man in line says the color of the hat immediately in front of him. He has a 50% chance of being right. The man in front of him now knows what color his hat is. If that color matches the one he sees in front of him, he says the same color immediately. If it is the opposite color, he pauses a beat or two before he says his own color, given him by the man behind. The pause tells the person in front of him to say the opposite.

Again, if the color the man behind him names matches what he sees in front of him, he repeats it immediately. If it doesn't, he pauses, then repeats the color. The pause is what tells each man ahead whether to speak immediately or pause a moment before speaking.

This will give the same 99.5% chance of success as BruceZ's solution while conforming to the rules.

Quote: beachbumbabs

A pause is an absence of communication, significant only to the prisoners who arranged it ahead of time, not to the king. The rules say nothing about a time interval between the colors being named.

Quote: BruceZ

So no forming of circles or what not. The Wizard has the right solution. It just isn't logically valid until the hint is given, and the reason for that is the real problem. I might as well give this hint that will probably give it away, but I have to be up in an hour to catch a plane and won't be back for a couple days.

Show Spoiler

Think about what happens if there were only 2 total people in the room and both their hats are black.

Quote: BruceZ

Your algorithm is correct for question 1; however, they already know that there is at least 1 black hat before the hint. In fact, they all know that there are at least 49 black hats because they each see at least that many. I specified that there were 50 black hats assigned. You may have read a version of my post where I left that out, but they cannot execute your algorithm even when they can each see black hats and still be logical. Yet they can execute it and be logical when the king tells them that there is at least 1 black hat, something that they already knew! Question 2 then is what specifically did the king tell them that they didn't already know?

Quote: Wizard

RE: BruceZ question #2

reply

This is going to be hard to explain:

1. Given that there are 50 black hats, those with a black hat will see 49 black hats.
2. So, given 50 black hats, those with a black hat can infer there are either 49 or 50 black hats.
3. If, there were 49 black hats, then those with black hats would see 48 black hats, and think there were 48 or 49 black hats.
4. If there were 48 black hats then those with a black hat would see 47 black hats and think there are either 47 or 48 black hats.
5. You keep peeling back this logic to the point that if somebody saw zero black hats he wouldn't know if his hat was black or white. So, when the king says there is at least one black hat it eliminates this problem.

So, while the king's statement may seem obvious, by using 50 layers of recursive logic, it does convey necessary information.

What bothers me about this response is I feel that I implied this in my original solution. Maybe I'm overlooking something that doesn't require 50 levels of recursive logic. Argh.

Quote: RS

Show Spoiler

But wouldn't the recursive solution require some form of communication, even if it's by delay?

Quote: Wizard

Quote: RS

Show Spoiler

But wouldn't the recursive solution require some form of communication, even if it's by delay?

Response

Yeah. However Bruce never said my method was wrong, he just didn't like my explanation of why the hint was necessary.

I will say that measuring the length of a pause is definitely not allowed in my problem.

Quote: beachbumbabs

Sure. Add more rules after I met all of yours. That's what I get for thinking outside the box. Grrrr....lol!

Quote: Wizard

I thought it was implied when I said that no communication was allowed besides "white" and "black." If the time to submit a guess means something, then that is conveying information.

My problem has nothing to do with "thinking outside the box." There is a logical solution and it is not any kind of trick.

Quote: Wizard

RE: BruceZ question #2

reply

This is going to be hard to explain:

1. Given that there are 50 black hats, those with a black hat will see 49 black hats.
2. So, given 50 black hats, those with a black hat can infer there are either 49 or 50 black hats.
3. If, there were 49 black hats, then those with black hats would see 48 black hats, and think there were 48 or 49 black hats.
4. If there were 48 black hats then those with a black hat would see 47 black hats and think there are either 47 or 48 black hats.
5. You keep peeling back this logic to the point that if somebody saw zero black hats he wouldn't know if his hat was black or white. So, when the king says there is at least one black hat it eliminates this problem.

So, while the king's statement may seem obvious, by using 50 layers of recursive logic, it does convey necessary information.

What bothers me about this response is I feel that I implied this in my original solution. Maybe I'm overlooking something that doesn't require 50 levels of recursive logic. Argh.

Quote: BruceZ

I'll let the Wizard overrule me if he feels it shouldn't be sufficient.