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.

Improve this question
$\endgroup$
12
  • $\begingroup$ possible duplicate of Hats and Aliens $\endgroup$
    – user88
    Commented Feb 24, 2015 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
    Commented Feb 24, 2015 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
    Commented Feb 24, 2015 at 17:13
  • 1
    $\begingroup$ About Twist 2: Are the dead logicians resurrected at the end of round one? $\endgroup$
    – Gamow
    Commented Feb 24, 2015 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
    Commented Feb 24, 2015 at 20:43

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
9
  • $\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
    Commented Feb 25, 2015 at 9:53
  • $\begingroup$ Here's the link: math.stackexchange.com/questions/1105531/… $\endgroup$
    – ghosts_in_the_code
    Commented Feb 25, 2015 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
    Commented Feb 25, 2015 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
    Commented Feb 26, 2015 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
    Commented Feb 26, 2015 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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