7
$\begingroup$

Pre-game: There are 1000 logicians in a line, each wearing a black or a red hat, completely at random. No one knows the color of their own hat. Each can see the hats on the next 10 people. The logicians are allowed to communicate before the game, but not once the hats have been placed.

Game: Starting with the back, each logician must call out loudly, a color, red, black, or white. White is obviously always wrong. This calling is, however, the only communication in the game. Every person who fails to say his own hat color is silently killed.

What is the best strategy for the logicians?

Twist 1:

Suppose there is exactly one blind man in the line. His location is not known to anyone, but he can hear and speak.

$\endgroup$
  • $\begingroup$ possible duplicate of Hats and Aliens $\endgroup$ – Joe Z. Feb 24 '15 at 17:00
  • 2
    $\begingroup$ @Joe Z: Both problems are hat problems, but I do not see why this should be a duplicate. There are three colors (instead of two colors), and there are 1000 guys with look-ahead of 10 (instead 10 guys with full look-ahead). With these hat-problems, small differences in the formulation can lead to very different solutions. $\endgroup$ – Gamow Feb 24 '15 at 17:07
  • $\begingroup$ For the main version (without twists), it is not hard to design a strategy where 909 logicians survive. Divide them into groups of size 11. The first guy in the group sacrifices himself and announces the parity of the red hats in the group. But this does not even use the white color, and I do not see how to argue optimality. $\endgroup$ – Gamow Feb 24 '15 at 17:13
  • 1
    $\begingroup$ About Twist 2: Are the dead logicians resurrected at the end of round one? $\endgroup$ – Gamow Feb 24 '15 at 18:30
  • 1
    $\begingroup$ I don't understand Twist 2. Are the hat colors changed in between rounds? If not, everyone alive gets a free pass. If so, I don't see how the existence of a first round affects anything in round 2. $\endgroup$ – Lopsy Feb 24 '15 at 20:43
3
$\begingroup$

The person in the back looks at the next $10$ people and adds $1$ for each black hat and $0$ for every red hat. If the sum is odd then he says "black". Otherwise he says "red". This gives him a 50% chance of survival.

The next 10 people can sum the 9 people they can see or have heard the color of from their block of 10 people. If their sum is the same parity (even or odd) as the one the back person had, they yell "red". Otherwise they yell "black".

The result of the limitation that each peson can only see 10 people ahead of them is that no information from the back person will continue to person 12. This means he will behave as a new back person. This means that the people in positions $1,12,23,etc$ labeled from the back are forced to act as "back" people and therefore have a 50% chance of survival. On average 45.5 people will die each game.

Twist 1:

The effect of a blind person will depend on his position $\mod 11$. If he is in positions $1,12,23, etc$, ($1 \mod 11$) guessing means there is a 50% chance he will die and there is an independent 50% chance everyone in the next 10 will die. He should say "white" which will kill him, result in the person in front of him having a 50% survival rate and the next 10 people after the person in front of him a 100% survival chance. If this occurs, on average 46.5 will die.

If he is in position 1000, he should just guess; everyone else has already gone.

If he is in position $11,22,etc$ ($0 \mod 11$) he has a 100% chance of survival because he could hear what everyone said.

If he is in position $10,21,32,43,54,65,76,87,etc$, ($10 \mod 11$) when he guesses if he is correct, both him and the person in front of him survive. If he is wrong they both die. If he says white, he dies and the person in front of him acts as a back person. If he guesses, on average 46.5 people will die. If he does not guess, 47 people will die on average. This means he should guess.

If he is in position $9,20.31,42,53,64,75,86,etc$, ($9 \mod 11$) when he guesses if he is correct, both him and the 2 people in front of him survive. If he is wrong they all die. If he says white, he dies and the person in front of him acts as a back person. If he guesses, on average 47 people will die. If he does not guess, 47 people will die on average. It doesn't matter if he guesses.

If he is in any other position, he should say "white". This means the person in front of him will act as a back person and, on average, 47 people die.

This means if the blind man is moral and randomly placed on average 46.8 people will die.

$\endgroup$
  • $\begingroup$ There was an error in twist 2, I've deleted it. As for the solution to twist 1, are you sure that it is right? I had asked a similar question regarding a blind man being added, on Math SE; and they gave a completely different answer. P.S: There are 1000 logicians, not 100. $\endgroup$ – ghosts_in_the_code Feb 25 '15 at 9:53
  • $\begingroup$ Here's the link: math.stackexchange.com/questions/1105531/… $\endgroup$ – ghosts_in_the_code Feb 25 '15 at 9:56
  • $\begingroup$ Consider that in that question, everyone can see all people in front of him except the one blind man. This puzzle has basically 9 sections and one of the sections has 1 blind person. That answer is in two parts: one using info i not familiar with and one that assumes we know where the blind man is (not ok). I dont know enough off hand to convert that answer to fit this optimumly. I highly suspect, however, that if it is directly ported to this answer more will die in the sections with no blind men than in my answer. $\endgroup$ – kaine Feb 25 '15 at 12:26
  • $\begingroup$ @kaine In twist 1, since the 'front' people (i.e. not 1 mod 11) know their own hat colour by looking at the hats in front of them after hearing the back person's shout, they should ignore any incorrect shouts from the other 'front' people. Then a blind 'front' person can always guess without penalising anyone else. $\endgroup$ – Lawrence Feb 26 '15 at 14:41
  • $\begingroup$ @Lawrence The don't know if any such shouts are incorrect as the kills are silent. Consider the case where there are three people in a line (a,b,c) with a in the back with the colors (r,r,r). a will say "black" and die as $1+1=0 \mod 2$. b is blind so randomly guesses "black" and dies. c thinks b lived so calculates that $0-0=0 \mod 2$ and confidently says "black" which kills him too. $\endgroup$ – kaine Feb 26 '15 at 14:48

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.