Puzzles!

[Blizzard]

there are 100 prisoners standing in a line, facing front.  Each prisoner has either a white or a black hat on.  Since they are in the line, each prisoner can see the hat of every man in front of him (the person at the back can see 99 hats).  Starting from the back of the line, and going to the front, each is asked what color hat they have.  If they are right, they live, wrong, they die.  How many prisoners can be saved, and how should they do it?

They can save half the prisoners for sure. Each "odd" prisoner says the color of the hat of the person in front of him so that one can live while each "even" prisoner says the color he has just heard from the prisoner saying that before him.

That would be my first thought.

[winkio]

Nope, you can save more.

[Blizzard]

How about this:

You can save all for sure except for one. The first person counts how many people with the same hats in front of him there are in a row and adds one. If there are 5 people with black hats immediately in front of the first person to tell, then that person will say black 6 times. Now the next 5 people know that they have black hats and the one after them knows that he has a white hat. When its the white hat guy's turn, he has to count the white hats in front of him including his own (since he wants to live, lol). Let's say there are 2 more people with white hats, so he says 3 times white. So the next 2 people know that they have white hats and the one after has a black one. This can go on until the end. Only the first guy might not survive since he might have a different hat then the people after him.

Am I getting closer?

[winkio]

each person can only say black or white once.  But you are getting close...

[ShadowPierce]

->How about tapping the next person's right shoulder when the next one's wearing black, & the left shoulder when the next one's wearing white?


†

[Blizzard]

Does a prisoner know when the guy behind him gets killed or not?

EDIT: What about this:

The first person says white if the next two people have the same color and black if they have a different color. Now the second person knows their own color from that information because they can see the color of the person in front of them. The third person has heard the first and knows whether the person before them has the same or a different color. Now they only need to listen to what the person before them says and they will know their own color. This tactic would save 66 prisoners.

[winkio]

->How about tapping the next person's right shoulder when the next one's wearing black, & the left shoulder when the next one's wearing white?


†

no other communication is allowed

Does a prisoner know when the guy behind him gets killed or not?

EDIT: What about this:

The first person says white if the next two people have the same color and black if they have a different color. Now the second person knows their own color from that information because they can see the color of the person in front of them. The third person has heard the first and knows whether the person before them has the same or a different color. Now they only need to listen to what the person before them says and they will know their own color. This tactic would save 66 prisoners.

That is a decent tactic, but there is another strategy where you can save more.

[Blizzard]

Then what about the dying? Do they know whether the people before died or not?

EDIT: Right now I am considering a completely different perspective. If you put together all answers, you can regard them as 0 (black) and 1 (white). If you can compress 80 bits of information into 20 bits, then you would be able to describe the colors of the last 80 people using the first 20. That way you would save 80 people. Am I going into a good direction here or does it have nothing to do with information theory? xD

[winkio]

No, but you keep getting closer.  Here's a hint:  you can save 99 people.

[Blizzard]

Crap. D: I figured out a way to save 93 of them. 7 serve as binary counter for how many prisoners there are with black hats (since 2^7 can count up to 128). The rest is easy. The 8th person know how many black hats there are and since there are 93 people left, he also knows how many white hats there are. Then he just would have to count the hats he can see and do the math to see which hat he is wearing. Everybody else had to do the same thing That way 93 people would survive.

I guess I have to try harder if I want to save 99 of them. xD

EDIT: Ok, this is either the solution you are looking for or a clever alternative solution. The first person can't be saved as he has no previous information. But through his voice tone he can give a hint to the next person. The first person can simply tell the color of the next person so the second person knows their color. Now, the second person says their color in a normal manner if the next person has the same color. If the next person has a different color, they yell out their color. That's it. They tell the correct color at the same time as they transmit the information of the color of the next person's hat. 99 people will be saved.

[winkio]

nope, they are not allowed any other sort of communication like tone changing.

The solution is inside here, if you give up:

Spoiler: ShowHide

The person at the back can't be saved, and thus counts the number of each color hat in front of him.  Since he sees 99 hats, there must be an odd number of one color and an even color of another.  He says whichever color has an odd number.  After that, the next person looks up and sees 98 hats.  There will be either even numbers of both or odd numbers of both.  If even numbers, he knows that he had one of the hats that the first person saw as an odd number.  Otherwise, he knows he has the opposite color of what the first person said.  In this manner, the prisoners keep track of what the people before them have said, and whether the numbers of hats are odd or even, and each can guess his own color hat.

[Ryex]

*gasp* Winko! you evil person you! you contently left out that there are 50 hats of each color! that was key to solving this riddle!

[Aqua]

Um... You can do that with any number of hats of each color o.o
Doesn't have to be 50

[winkio]

Aqua is correct.  They could all have the same color hat and this strategy would still work.  Or any other combination.

[Ryex]

*facepalm*  nvm I see that now...

[Blizzard]

I give up, lol! I somehow knew that "odd" and "even" were the words why you told me that I kept getting closer, but I couldn't find a way to apply them. xD