After surviving a plane crash, you and nine other people find yourselves on a wild and hostile island...

Question 3

After surviving a plane crash, you and nine other people find yourselves on a wild and hostile island. Despite your strong survival skills, a very territorial tribe captures you. They decide to let you go provided you solve their riddle. They put you in a line, all facing the same direction, and place a feather on each of your heads. Each feather can be black or white, and you are only able to see the feathers of the people in front of you (so if you're last, you can see everyone's feather except yours). They will then ask the ten of you, starting from the back, what color the feather on top of your head is. You, as a group, are allowed at most one mistake. You can also coordinate before the challenge to devise a strategy. How can you survive?

The first thing to realise is that the last person in the queue has simply no way to figure out the correct answer. Given that they will get it wrong \(50\)% of the time, you must devise a strategy where the second-to-last person in the queue can deduce their feather's color from the last person's answer.

Now, think of what information the second-to-last person has... They can count the number of black and white feathers they see among the \(8\) people in front. Imagine they see \(6\) black feathers and \(2\) white feathers. If the last person in the line could tell them how many black feathers they see, they could easily figure out their feather's color. For example, if the last person sees \(7\) black feathers, they automatically know they have a black feather (since they only see \(6\)).

What makes it difficult here is that the last person in the line must answer by "black" or "white". They cannot just shout a random answer. Now remember that you can devise a strategy beforehand, and therefore this "black" and "white" can mean anything. It turns out that if you decide, as a group, that if the last person in the line answers "black", it means that they see and even number of black feathers, odd otherwise, then the second-to-last person will have just enough information to figure out their feather's color. For example, re-using the same numbers as above, if the last person says they see an odd number of black feathers, then the next person knows their feather must be black (they only see \(6\) black feathers which is even).

The same argument can be extended to the next \(8\) persons in front. They can count how many black and white feathers there are in front of them and they can deduce those same numbers for the people behind, since the latter already gave their answers. Say the \(8\)^th person sees \(5\) black feathers and \(2\) white, that the \(9\)^th person has a black feather and that the last person said they see an odd number of black feathers, then they know they must have a black feather for parity to hold.

As you can see, everyone else will be able to figure out their feather's color, and so it doesn't matter if the first person gets it wrong, you will make at most one mistake. Lucky for you, you guys can escape this time!