13
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Will the spy act counter to the strategy, as well as passing it on? For example, if the strategy was 'everyone say white', would the spy say 'black'? $\endgroup$ – LogicianWithAHat Aug 27 '15 at 14:18
  • $\begingroup$ @LogicianWithAHat They would do whatever results in maximum deaths. If saying white will kill more people he will say white. If saying black will kill more people he will say black. $\endgroup$ – Rohcana Aug 27 '15 at 14:20
  • $\begingroup$ Are there equal numbers of hats? Does the colour of an abductee's hat get revealed to everyone after their guess and before the next guess? $\endgroup$ – Gordon K Aug 27 '15 at 14:32
  • $\begingroup$ @GordonK Assume nothing, if its not stated. $\endgroup$ – Rohcana Aug 27 '15 at 14:34
  • 1
    $\begingroup$ Why does the title sound so much like something taken from Team Fortress 2? $\endgroup$ – nine Aug 27 '15 at 16:50
9
$\begingroup$

To start:

Persons 1 and 2 count the number of white hats from person 3 to person N. They say 'white' if it's an even number, or 'black' if it is not. If they agree, proceed to the next step.
If not, one of them is the spy, and person 3 counts the number of white hats from person 4 to person N, again saying 'white' if even and 'black' if odd, then proceed. Thanks to @Arkku for that!

Then:

Starting from person 3 (or person 4, if 1 and 2 gave different answers), each person keeps track of how many people have said 'white', and uses this and the knowledge of the initial parity (I think that's the right term) of white hats to call out their own. The spy will inevitably call out the opposite, causing the next-in-line to also call out the incorrect colour. The system is parity-based, however, so this will put the group as a whole back on track (see example)

Total losses:

Two people in the line (the spy and the next person), and the 2 people at the beginning (since the aliens control the layout of the group), for a total of 4 incorrect guesses.
The spy won't be one of the first two people - if they are, a maximum of 3 people will call out incorrectly, if not, it will be 4.

Example:

X,X|W,B(spy),B,W - the first two don't matter, so are labelled as X. Each has a 50% chance of survival (or not, since the aliens will arrange them such that they all die, sadly)
1 and 2 have both said 'white'. Everyone knows that neither of them is the spy
Person 3 can see one white hat and knows there are an even number, so calls out 'white'. 3 lives. Persons 4,5 and 6 know that an odd number of white hats remain.
4 is a spy, and knows from this that they have a black hat. They call 'white', dooming the region of the earth that they represent. 4 dies
5 knows that there were an even number of white hats to start, that two have been called out, and can see one in front of them. They must also be white, they think, and thus sentence themselves and 1/6th of the population to death. 5 dies
6 also knows that there were an even number of white hats to start, and that three have been called. Therefore they must be white, to preserve parity. 6 lives

Same example, no spy:

4 knows that they have a black hat. They call 'black' 4 lives
5 knows that there were an even number of white hats to start, that one has been called out, and can see one in front of them. They call black 5 lives
6 also knows that there were an even number of white hats to start, and that three have been called. Therefore they must be white, to preserve parity. 6 lives

Either way, the spy only affects the outcome for themselves and the person after them in the line

This only works for N > 4 (though for N<8, random guessing will yield better results on average)

$\endgroup$
  • $\begingroup$ Note that, the spy may also tell the truth if he sees that it kills more people. Also, How do you correct if you don't know who is the spy. $\endgroup$ – Rohcana Aug 27 '15 at 14:49
  • $\begingroup$ This should work regardless of whether or not you know who the spy is. I'll try and edit to make that clearer. Also, the spy lying here guarantees more deaths $\endgroup$ – LogicianWithAHat Aug 27 '15 at 14:52
  • 2
    $\begingroup$ I don't think you need to have the first three people count the parity in every case: if the first two agree on 3–N, then the rest can trust that information already. If the first two disagree, then one of them is the spy, and the third person can be trusted to give the correct parity for 4–N. $\endgroup$ – Arkku Aug 27 '15 at 16:28
  • $\begingroup$ ...that is an excellent point! Thank you! $\endgroup$ – LogicianWithAHat Aug 27 '15 at 16:37
  • 3
    $\begingroup$ "Everyone knows that neither of them is the spy" I would write that as "Everyone can assume that neither of them is the spy". The spy is not required to disagree with the other one, it's just that if he does agree then he gains nothing. $\endgroup$ – Taemyr Aug 31 '15 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.