After failing to destroy the human race, Aliens have returned to make another attempt. This time they have planned a wicked strategy. They have again abducted $N$ people, but one of these people is actually an alien spy disguised as human. Each person (including the spy) represents equal portions of the human race.
The aliens give each abductee either a black or a white hat. The people are lined up in a single line, each facing forward, such that each person sees the hats of all persons in front of him. The aliens then proceed, starting from the last person, to ask each of the abductees what the color of their hat is. If they guess incorrectly, the human population they represent is killed. The others don't learn of this incorrect guess.
The abductees are given a chance to develop a strategy before they are lined up. However, whatever strategy they plan, it is known to the alien spy (and hence the aliens). The spy's task is to ensure as many deaths as possible. The aliens, knowing the strategy can rearrange the line any way they like.
However, the humans have figured out that one of them is a spy, but they do not know which one. What strategy should they utilize to minimize the number of deaths?
Alternate formulation
$N$ people are standing in a line. Each of them wears a black or white hat and can see the hats of all people in front. Starting with the last person, they guess the color of their hat. They want to maximize the number of correct guesses. However, they know that there is one person, whose identity is unknown, who wishes the opposite. What strategy should they follow to maximize the number of correct guesses in the worst case?
Notes
- The humans cannot communicate in any way once they are lined up.
- The Aliens are serious this time; Do any thing funny and they will blow the whole earth.