Logic/math problem

Factual Questions
1

This is something a friend gave me and I’m still stuck.
There are eighteen people in a line. Each one is given a black or white hat randomly, there is no limit to the number of hats of each color so the whole crowd could end up with all white hats, all blacks hats, half white half black or 13 white and 5 black hats. And they are in a random order. A person cannot see their own hat but they can see the hat of all of the people in front of them in line. If one says the color of their own hat they make keep it, but if they get the wrong color they must return it. They start at the back of the line (the person who can see everybody else’s hats) and start asking. There is one way where there is a 50% chance that everybody can keep their hats and there is a way to ensure 100% that 17 out of the 18 people keep their hats.
-The people are allowed to discuss a strategy before they line up

  • each person may only say one word, either “white” or “black”
    How is this possible?
2

Well, given that you didn’t restrict them in any way other than speech…

When it’s person number N’s turn, he taps person N-1 (who is standing in front of him) on the left shoulder if person N-1 is wearing a white hat, but taps him/her on the right shoulder otherwise.

3

Think parity. The person at the end of the line says, “white” if there are an even number of white hats, and says, “black” if there are an even number of black hats. Since there are 17 people in line, there cannot be an even number of both.

The next people in line simply need to count and keep count of what each of the other people say. There is a 50/50 chance the last person will guess right, but they are not guessing to keep their own hat, they are simply relaying information. If it happens to match up, great.

4

The person at the back of the line says “black” if the number of black hats in front of him is odd and “white” if the number is even. There’s a 50% chance he’ll be right and get to keep his hat.

The next person in line counts the black hats he can see. If he sees an odd number but the person behind him saw an even number his hat must be black. If he sees an even number and the person behind him also saw an even number his hat must be white. There are four possible cases odd-odd, odd-even, even-odd, or even-even, all of which tell him the color of his hat.

The next person in line repeats the process, switching odd and even if the person behind him had a black hat.

Everyone is line except the last person is guaranteed to get his hat.

5

I KNOW there was a thread about this some time ago, but durn if I can find it. The upshot, I believe, was that you treat black hats as having a value of 1, and white hats as having a value 0. The last person in line totals up the value of the hats in front of him and divides by 2. The remainder will be 1 (black) or 0 (white) (this is known as modulo arithmetic - dividing and taking the remainder instead of the quotient). The person says that color. The next person in line counts up the value of the hats he can see and performs the same arithmetic. If the value is the same, he knows he’s wearing a white hat. If the totals are different, he’s got a black hat on, and he can call it out appropriately. Lather, rinse, repeat.

6

I typed up a similar answer as Pochacco, but it took so long it’s obsolete. I’ll keep my example. The only difference is I’m counting white hats instead of black hats…

Just in case it’s still not clear, here’s an example, with only six people, to make it easier. The front of the line is on the left, and Person One is on the right:

W W B W B W

Person One sees three white hats, so she says black (since three is odd). She loses her hat, but too bad. She had a 50-50 chance. We now completely forget that Person One ever had a hat; deal only with the front five.

Person Two sees three white hats. He also knows (because of Person One’s answer) that the number of white hats on the front five people is odd. If Person Two had a white hat, that would make the total four, which is even. So Person Two must have a black hat. He says black. Everyone knows he got it right, because they’ve thought this through.

Person Three sees two white hats. He knows that there are an odd number of whites on the front five. He also knows that Person Two had a black hat; he just said so. So if Person Three has a black hat, that makes the total (on the front five) two, and if he has a white one, that makes the total three. Since three is odd and two is even, he must have a white hat. He says white and gets it right too.

Person Four, by this point, knows there are two whites in front of her and one white behind her, so she says black.

Person Five knows there is one white in front, and one behind, so she says white, to make the total odd.

And so on. Everybody else gets to keep their hat. This is an optimal solution, because Person One gets no information about her own hat, ever, so the best she can do is 50%.