Another logic problem

[Lyhrrus]

I've always liked the sort of problems that DicemanX has posted up, and I enjoyed this problem especially.  If you already know the answer, please don't spoil it for others.


You are the ruler of a small country that has been
invaded.  The conquering army has decided to cull the
population.  The selection process is as follows:

A: The entire population is lined up from tallest to
shortest, so that the tallest may see everyone and the
shortest sees no one.

B: Each individual is randomly given a hat from a bag
containing an arbitrarily large number of both black
and white hats.

C: Starting from the tallest end, each individual must
state the color of the hat they are wearing.  They are
then led off.  If the color of the hat matches what they said, they
live, if not, they die.

D: Being the ruler, you are granted some privileges.
They are the following:

i. You are allowed to see the line after they have
received all their hats.

ii. You are allowed to choose the color of your own
hat.

iii. You are allowed to choose your position in the
line.

Prior to the selection beginning, you are allowed to
meet with your people to devise a system.

Outside of the meeting prior to the selection, you are not allowed to communicate anything else to anyone (no whispers, hand gestures, heavy breathing, etc.).  Everyone's answer to what hat you are wearing can be heard by all the other people in line.

What is the greatest number of people you can save
(this does not necessarily include yourself) and how?



Answer in white:

You can save 100% of the population.  When meeting with the people, you tell everyone that after reviewing everyone's hat color, you will choose a hat to make the total number of white hats even.  You will also stand at the very front of the line.  Thus, when the tallest person in back sees all the hats, s/he will count the total number of white hats seen.  If it is odd, then they know they are wearing a white hat, if it is even, then black.  Since the answer is heard by all, if a white hat was stated, then the rest of the population now knows there is an odd number of white hats remaining and will adjust their answers accordingly.




EDIT: Clarifications from Mr. Nightmare beating the system
EDIT #2:  Suggested answer

[Mr. Nightmare]

Why wouldn't you just stand in position 1, and have each person tell the person behind them what color hat they have on?

I know my own.  I tell 2 "Black" and tell the invader my own color.  2 tells 3 "white" and tells the invader "black."  3 tells 4 "White" and tells the invader "white," and so on.  Then everyone is safe.

[Lyhrrus]

Once in line you are not allowed to communicate anything else to anyone (no whispers, hand gestures, heavy breathing, etc.).  Your answer to what hat you are wearing can be heard by everyone else though.

[Mr. Nightmare]

Once in line you are not allowed to communicate anything else to anyone (no whispers, hand gestures, heavy breathing, etc.).  Your answer to what hat you are wearing can be heard by everyone else though.

Well now you've altered the constraints of the problem.  My answer was well within the original scope of the question.

Here, I'll beat the system again.  Prior to taking my own position in line, I will tap each person with a black hat on the left shoulder as I pass them to my position at the end of the line.

[Lyhrrus]

Fair enough, you've beaten the system yet again, though there is a solution within the now changed conditions still.

[Anusien]

You can definitely save at least yourself and one person.  Stand in the front and put on a hat to match #2, then call out your color.  They know now what color they have.

[LordHomerCat]

My answer follows in white:

I think you could save at least half of the population plus yourself.  You devise a system with your people so that, starting with you, every other person will say the color of the hat of the person in front of them (you should pick the same color as the tallest person, and stand so you are first in line).  Then, the next person (again every other person, but staggered) will say whatever the person behind them stated.  So, it would go like this:

You say the color of the tallest person's hat (person 1).  You have already picked the same color hat, so you live.  Person 1 says the same thing as you, and lives.  Person 2 then says the color of person 3's hat, and they may or may not die (assume they do to get the worst case).  Person 3 then says the same thing and lives.  Repeat for everyone, and if you have an even number of subjects, you have saved (# of subjects / 2) + 1 people including yourself.  If you have an odd number, you have saved ((number of subjects + 1) / 2) + 1 including yourself.  My gut tells me you can save more but this is the first idea I came up with.
Also, nice job by mr nightmare breaking the puzzle, that is always my favorite way to solve difficult problems =]

[Lyhrrus]

Good start by LordHomerCat

True, you can save at least 50% + 1 no matter what.  You can even decide previously to say that you'll look at everyone's hat beforehand, and choose the hat color of the greatest number of hats present and stand at the very front of the line and have everyone state that color.  There's still a way to save more people though.

I'll post a method on Monday sometime.

[emidln]

Answer in white:

It seems that you can save everyone (excepting for disabled people which would present the risk of up to one casualty per disabled person). You tell your people to yell their color if they have black and to speak it regularly if the have white. You know what color hat you have so you start first and control the volume of your voice appropriately. Assuming nobody is deaf, everyone lives. A deaf person could be instructed to make a guess and still follow the instructions by attempt to control their voice or scream as loud as possible. This would result in, at most, one casualty per deaf person. A blind person would present the same risk to the population (one casualty), but the person to potentially die would be the next person in line. Alternately, if raising the volume of your voice isn't allowed, you could vary the stress of syllables.

[Lyhrrus]

Answer edited into original post

[Harlequin]

Rather than black and white, conceptualize the entire population as a string of 0's and 1's with black being 1 and white being 0.  The sum of all 1's will either be odd or even.  If the rule is looking at an even number he simply stands in the front of the line.  If the number is odd, he inserts himself dirrectly behind the last person with a black hat.  so..  0010100100[king]100000 front. 

Everyone behind the king will know there is an even number of 1's to start.  And based on the information ahead of them (up to the king) they can deturmin if thier hat is black or not.  If thier hat is black, then the people behind the king know the number of black hats is now odd. 

Now it comes to the king.  You just name your hat.  And hopefully your voice is recognizable to everyone in front of you.  If it is, then the person dirrectly in front of you says "black" and everyone else says white.