3
$\begingroup$

Another twist to this question. I'll restate it here to avoid confusion

There are N perfect logicians arranged in a vertical row. They are allowed to strategize before the game, during the game they are barred from communicating. In the game, the lights are switched off, and a single hat, either red or blue, is placed on the heads of each of the logicians. The lights are turned on; each logician can see the hat colours of all the people in front of him, he can't see the colour of his own hat, or the people behind him. Start with the person at the back, each logician has to call out a colour (heard by all). If his own hat is of that colour, he is spared, otherwise, silently killed. The same is done by the next person, and so on, right till the first person. How many logicians can you guarantee to save, irrespective of the initial colours or any probability?

(Please see the answer to this on the same link.)

And now the twist....

Suppose there are 2 blind man among the logicians. Their lives are worth as much as anyone else, and are placed randomly in the queue. How many logicians can you guarantee to save?

The solution may still involve some sort of binary....

$\endgroup$
  • $\begingroup$ For others interested in this, the linked question is very similar (but not a duplicate) puzzling.stackexchange.com/questions/9536/… $\endgroup$ – kaine May 13 '15 at 12:48
  • 2
    $\begingroup$ Also can the logicians tell who the blind men are when they are in the vertical row? $\endgroup$ – kaine May 13 '15 at 12:50
  • $\begingroup$ The logicians are allowed to strategize before the game. Are they allowed to move position? $\endgroup$ – tfitzger May 13 '15 at 15:38
  • $\begingroup$ @tfitzger - since the blind men are placed randomly in the queue, I'm guessing they can't move position on their own. The question of whether they logicians know where the blind people are is important. Given that they can strategize before the game, I'm guessing they can know. $\endgroup$ – Duncan May 14 '15 at 18:17
  • $\begingroup$ Actually, the question linked on math.SE says: "Note: The blind person man knows where it is placed, but nobody else knows his position." So now I'm thinking they can't tell. $\endgroup$ – Duncan May 14 '15 at 18:23
4
$\begingroup$

The answer is to

Use the exactly same strategy. This gets a maximum of $5$ people killed, irrespective of $n$.


There are $c^N$ different arrangements of hats where $N$ is the number of logicians and $c$ is the number of colored hats ($c=2$ in this case but the explanation is easier without that). The positions are labelled $1,2,3,...,N$. The colors are also $1,2,3,...,c$ which in the case are $1$ and $2$ for red and blue.

The logician in position $1$ knows nothing about his hat and only knows about the others in front of him. Therefore, he always has a $\frac 1 c$ chance of surviving. He tries to save the others which means (in the traditional answer) he says a color which indicates what the sum of the hats in front of him is $\mod c$. Here he says red if there are an odd number of red hats in front of him and blue otherwise. This information is enough to allow all people in other positions to survive no matter what c is.

Effectively, there are $N$ pieces of information needed to be supplied to allow all players to survive as the system can be described as a system of $N$ equations. As each player (excluding the one in position N) can (and does) supply $1$ piece of information, $N-1$ are supplied so $N-1$ can be guarenteed to survive if the players are clever. The first person says a relevant color so on average $\frac{1}{c}$ die.

If there are 2 blind people and their positions are known, you still need $N$ pieces of information but you can only collect $N-3$. This means $\frac 3 c$ can survive on average. The easiest way to do this is by having all players ignore the blind ones while doing their summations and allowing the blind people to guess. This can also be done by having the summations end at the blind person and after the blind person start the pattern afresh. This results in a minimum of $N-3$ survivors with either strategy.

If there are 2 blind people and their positions are not known, the positions of the blind people at as additional required information so more than $\frac{3}{c}$ will die. When the blind person comes along he can say a colored hat which isn't in the game. This would reset the game after the blind person and kill him. Assuming the blind people's positions are unfavorable, this results in $2+\frac{3}{c}$ average deaths for a minimum of $N-5$ survivors.

If we can modify the color a little and have blind people guess crimson and azure instead of red and blue, the average number of survivors (for an infinite number of logicians to neglect end effects) is $\frac 5 c$.


Surprising Answer with the same average result!

I have surprisingly found a shocking fact; two wrongs do in fact make a right with the standard algorithm. Here red and blue are equivalent to $1$ and $0$.

We follow the standard algorithm where the back player states (correctly or incorrectly) that he is wearing a hat which matches the parity of all of the other hats he can see. All other player then know they are wearing the hat that has the parity equivalent to the sum of the hats that have been stated plus those they can see. If C is greater than 2, (white, black, or brown hats) the player should guess the parity equivalent to the hat color of the first person minus the sum of (all hat colors you heard and all the hat colors you see).

Blind people will randomly guess what their hat color is with no regard to whoever else is around them. If the blind person is incorrect, the player after him is also incorrect. While both die, this mathamagically corrects the parity of the summmation all players after them (besides blind people) use to determine their hat colors. This means without correction, exactly two people will die from an incorrect answer.

Lets define the following for a mathamatical explanation for $C$ colors. $S_o$ is equal to the first person's guess. $S_b$ is the sum before the blind person. $S_a$ is the sum starting with the 3rd people after the blind person. $H_b$ is the blind person's hat and $G_b$ is his guess. $H_v$ and $G_v$ refers to the person after the blind person. $H_l$ and $G_l$ refer to logician after that. $E$ refers to the error the blind person if off by and would be zero if he is correct. Note that if we reduce $C$ to $2$ this holds and the simpler equation is equivalent.

$$H_b=S_o-S_b-S_a-H_l-H_v \mod C$$ $$G_b=H_b+E \mod C$$ $$H_v=S_o-S_b-S_a-H_b-H_l \mod C$$ $$G_v=S_o-S_b-S_a-G_b-H_l \mod C$$ $$G_v = H_v-E \mod C $$ $$H_l=S_o-S_b-S_a-H_b-H_v \mod C$$ $$G_l=S_o-S_b-S_a-G_b-G_v \mod C$$ $$G_l=H_l \mod C$$

If two blind people are adjacent or a blind person it at the start, this autocorrecting behavior of the equation still holds. Usually this means fewer people die and never means more. Therefore, no more than 2 people per blind person die so this basic strategy means that there are a maximum of $1+2B$ deaths where $B$ is the number of blind people. On average $\frac{1+2B}{C}$ survive assuming pessimal original positions. This is all independant of $C$. For $B=2$ there are $N-5$ guarenteed survivors.

$\endgroup$
  • $\begingroup$ Actually, if the positions of the blind people are known to all, then the blind people wouldn't have to guess. You can partition the line into pieces, each piece ending in a blind person. The first person still might get unlucky, but the blind person, being at the end of that section, would know what his hat was based on the previous responses. You'd then start with the next "section" - the person following the first blind person up to and including the second blind person. Though you still end up with a maximum of 3 people guessing, it might be lower if one blind person is at the end. $\endgroup$ – Duncan May 14 '15 at 18:12
  • $\begingroup$ @Duncan that is the second strategy i was refering to in that paragraph. Sorry if i wasnt clear but i didnt want to work too hard on the explanation as it was also the strategy JontheMon posted when i was halfway through this answer. $\endgroup$ – kaine May 14 '15 at 18:59
  • $\begingroup$ See here for another statement of the solution. $\endgroup$ – David Bevan Sep 29 '15 at 18:15
2
$\begingroup$

Assuming the logicians can tell who the blind men are (behind and in front), they could essentially have

3 (outside chance of 2) groups that behave like the originating question and end with a blind man.

So, first guy gives parity bit, all the next seeing guys give their guess, then the blind guy knows his bit. Next seeing guy gives parity bit, etc. You can get down to 2 groups if one of the blind guys is at the end.

$\endgroup$
  • $\begingroup$ Actually, you could get one group if the blind men are at either end (either both in the front or both in the back, or one of each). Though if they're at the back, and therefore first to speak, there might be logical issues. $\endgroup$ – Duncan May 14 '15 at 16:59
  • $\begingroup$ No, the blind men are placed at random. $\endgroup$ – ghosts_in_the_code May 15 '15 at 16:39
0
$\begingroup$

Let's get some values out of the way.

First off, we have to assume the most pessimal option, because that gives us the worst case scenario for who we can save. In that situation the first two logicians to guess are the blind members. The reason this is the worst case is because they cannot set up the rest of the group as they need to.

Now, a single person cannot know the color of their own hat or of the hats behind them. This means that there are three unaccounted for hats by the time we reach the first sighted person. This means there are 97 visible hats in front of the sighted person. Now, this person, unfortunately, has a 50% chance of making the sacrifice play.

The first sighted person looks down the line and counts the red hats. They now know there are N red hats and 97-N blue hats. They then call out which ever of those numbers is higher. Since the numbers are inversely proportional, one will always be higher. From this view, the closest breakdown can be 43 to 44, so our best case in the pessimal option is 44. Now, it's possible that this is the same color as the current logician's hat, but we are going for the pessimal option, so we pretend it isn't. We also pretend that the two blind gents before him also guessed wrong.

Now, this is the pessimal option. This is the value that we are guaranteed to save with this process. But it isn't the most likely option. There is a 2% chance that one of the blind men will end up at the beginning. This means there is a 98% chance the first person in line is sighted. How does this change the field?

Now, there are 99 other people in front of the first person. This means that the minimum number of hats of a given color that he can see in front of him is 49. That is assuming a close to even distribution. If, however, there is a disproportionate number of red or blue, this automatically saves the population represented by the largest number of the same color hat.

Using this method, it is technically possible for all the logicians to be saved, if they all have the same colored hat. This is very, very, very unlikely however.

TL;DR - minimum saved of 44, most likely amount saved around 49


Another alternative would be to slightly bend the rules in our favor.

First, we have to adjust the way the logicians speak. We will assign three choices: no stutter, single stutter, double stutter.

No stutter sounds like blue or red Single stutter sounds like b-blue or r-red Double stutter sounds like b-b-blue or r-r-red

No stutter indicates that the hat in front of me is the same color as color I am saying.

Single stutter indicates that the hat in front of me is the opposite color as what I am saying.

Double stutter is assigned to the blind men. This is a way to indicate to the person directly in front of them that they are the blind person, thus the color they are saying has no known connection the hat in front of them.

To illustrate how this would work:

R B B R R R B R B B B R B ...

The first person clearly states BLUE. They are killed, but the second person also clearly states BLUE. He is safe. The third person stutters B-BLUE. She is also safe. The fourth person, hearing the stutter, clearly states RED. She knows that her hat is the opposite of the given color, so she is safe. The fifth person is blind, so he states R-R-RED, saving himself and telling the next person that he is blind. The sixth person then clearly states BLUE. Unfortunately, her hat was red, so she died, but the seventh person can live and carry on the chain.

In our pessimal situation, we can save 97 people using this tactic. This is because the first two people cannot give the next color and the third has to guess. In our pessimal setting, he guesses wrong.

Most likely scenario saves 98 people, as two in front of the blind folks have no way of knowing their actual hat color and are risking their chance of safety.

$\endgroup$
  • $\begingroup$ This answer taught me the word "pessimal". $\endgroup$ – Rand al'Thor May 13 '15 at 19:12

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.