$N$ perfect logicians wearing hats

I once came across the following riddle: (assume $N$ to be extremely large)

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?

The answer was simple. The first logician would sacrifice his life. He would call out red if there are an even number of red hats in front of him, and black if there an odd number of red hats. After him, each logician can correctly tell the colour of his own hat.

I decided to give the question a twist. Suppose there is a blind man among the logicians. His life is worth as much as anyone else, and he is placed randomly in the queue. How many logicians can you guarantee to save?

The same approach wouldn't work because, if the blind man gave the wrong colour, not only him, but all the people in front of him will give the wrong colour as they depend on his information also.

After a lot of thinking, I finally came up with this solution.

Find the smallest $n$ such that $3(n+1)+2^n \geq N$. The first $3(n+1)$ people (from the back) will be the ones sacrificing their lives (Group A), and the rest ($2^n$) will try to figure out their own hat colours (Group B). Starting with the back of Group B, assign each logician an ($n+1$)-digit binary number, starting with a string of zeroes, and adding $1$ to get the next logician's ID. Note that the first digit will always be a $0$.The first Group is divided into $n+1$ subgroups of $3$ logicians each. Each subgroup is assigned a normal decimal number $1,2,3,\cdots$ and so on (again starting from the back). Let the subgroup number of a logician be $k$

When the game starts, each Group A logician will look at all the people in Group B, whose $k^{th}$ binary digit is $1$. Of these people, if there are an even number of red hats, he will say red, otherwise he will say blue. The other $2$ logicians in his subgroup will give exactly the same information as the first one. This is necessary to confirm that he is saying the truth, if there is a discrepancy among the $3$ answers, the information given by $2$ is correct, and the third one is the blind one. The same is done by everyone in Group A.

The people of Group B only try to figure out their own hat colours. Each logician has $n+1$ ways of figuring out his own hat colour. If all of the given data doesn't lead to the same answer, he knows that the blind man is behind him and has already called out a lie. He can then use the first logician's info (first in Group A and the queue itself) to figure out his own colour, since the blind man has for sure been counted by that person.

Is my approach correct and is there a faster one? I hope my question is clear enough.

Note: The blind man knows where is placed, but nobody else knows his position.

Solution 1:

I think the Hamming code with extra parity provides a solution. If there are $2^n$ logcians, this requires sacrificing $n$ of them (each with chance $1/2$). Let the rear $n$ be the parity bits of the code, called out by those logicians. All the rest can run the error detection scheme. If no bits are wrong yet, either because the blind logician has not spoken or because he was right, each person can find the hat color that has no errors. If one bit is wrong already, one of the hat choices will make two errors, which are detectable by the code.

If the ones behind the blind man can see where he is, you can save all but maybe 2. The rear logician announces the color of the blind man's hat. The next one announces the parity of all the hats he can see. Everybody else is saved by the original solution. If the blind man is at the back, it is not a problem. If the blind man is second, the first announces the color he should say for the parity.

Your approach is correct but not optimal. For large $n$, it requires the sacrifice of $3 \log_2 n$ logicians, while my first paragraph requires the sacrifice of $\log_2 n$. As you say, you are repeating every bit three times, which guarantees the correct answer will be a majority if only one bit is flipped. This exploits the fact that the Hamming distance between $000$ and $111$ is three. Flipping one bit will leave you distance $1$ from the correct string and distance $2$ from the incorrect string. The code I cited at the start does the same thing with $n$ bit code words. All the acceptable ones are at least a distance $4$ from any other, so you can correct single bit errors and detect two bit errors.

Added: We can do it with at most three being sacrificed. You do the classic solution that does not involve the blind logician. The rear one guesses the color that would make the number of red hats even, and is sacrificed with probablity $1/2$. Each one in turn adds the number of red hats he sees to the number of red guesses he has heard. If even, he guesses blue. If odd, he guesses red. All (except maybe the first) will be right. Now we add in the blind logician, who guesses randomly. If the blind man is wrong, the next after him will be wrong, but that restores the parity and the rest are saved. We now lose at most three (the first, the blind man, and the next).

Solution 2:

This is the third version of this answer, giving an even more general solution than the previous two.

It appears that Saphrosit's solution is correct. Moreover, following Mercio's comments below, it can be considerably simplified, sacrificing no more than $2B+1$ logicians if $B$ of them are blind. Surprisingly, this is the case however many colours the hats may have.

Suppose the hats take colours from $\mathbb{Z}_c$ and let the hat colours be $h_1,\ldots,h_N$, each $h_i\in\mathbb{Z}_c$, and let $s_k=\sum_{i=k+1}^N h_i\pmod c$ be the modular sum of the hats in front of logician $k$.

We define $g_k$, the colour "guessed" by the $k$th logician, as follows:

• A blind logician may guess arbitrarily.

• If the first logician is not blind, $g_1=s_1$.

• For other non-blind logicians, $g_k = g_1 - s_k - \sum_{i=2}^{k-1} g_i \pmod c$, for all $k\geqslant2$. If $g_1=s_1$ and, for each $i$ in the range $2\leqslant i<k$, we have $g_i=h_i$, then $g_k=h_k$.

If the first logician is blind and guesses a colour different from $s_1$, then $g_2=h_2+(g_1-s_1)\neq h_2$, but subsequent logicians guess correctly because it is still the case that $g_1-g_2=s_1-h_1$.

If logician $b>1$ is blind and guesses incorrectly, then $g_{b+1}=h_{b+1}+(h_b-g_b)\neq h_{b+1}$, but again subsequent logicians guess correctly.

Thus, if $\mathcal{B}$ is the set of indexes of blind logicians, $$ \{k:g_k\neq h_k\} \;\subseteq\; \{1\} \:\cup\: \{b:b\in\mathcal{B}\} \:\cup\: \{b+1:b\in\mathcal{B}\}. $$

A question: Can we do better than $2B+1$ if $B$ is large compared to $N$ (i.e. if $B>\log N$ or $B>\sqrt{N}$ or something)?

Solution 3:

I am not an expert in coding theory, so please bear with me if my solution is not formally stated, but I think I found a solution that requires a constant number of sacrifices: $6$ (in the worst case). The idea is the following:

The blind logician is taught to say $0$ in every case.
The firsts $4$ logicians are responsible for providing parity informations: the firsts $2$ give a parity bit for the whole queue of $N-4$ logicians, while the seconds $2$ give a parity bit for the logicians in even position. It is necessary that each bit is repeated twice in case the blind guy is among the firsts $4$ (redundancy will allow everybody to understand which is the correct bit). Clearly the parity bit of the logicians in odd position can be deduced.

All the others logicians will reason in the following way: assume everyone who already talked was correct. If what you see is coherent with the initial parity signaling (i.e. if deducing your bit using the total parity bit you get the same result as deducing your bit using only the even/odd parity bit) then just say the bit you deduced. Otherwise you will deduce that the blind guy was right before you, so by flipping his bit you can understand his, and as a consequence your bit. Just say the correct one.

To show that the maximum number of sacrifices is actually $6$ there are a couple of claims that need to be proved:

• why a conflict between parity bits and following bits allows to conclude that the blind logician is exactly the one before the current one?

• why, after detecting the error and identifying the blind guy, we can be sure no others clashes will occur?

To answer, let's use a partially formal language: let $A$ be the set of the firsts $4$ logicians and $B$ the set of the subsequent $N-4$ logicians. We can give $B$ the speech order (the first one is the one that speaks first). Let $hat: B \to \{0,1\}$ be the "color" of the hat of logician $x \in B$.
Let $b$ be the blind logician. Let's assume $b \in B$ (otherwise all logicians in $B$ will provide the correct answer) and $hat(b) = 1$ (otherwise he will guess his color and no error is generated). W.l.o.g. we can assume $b = x_0 \in B$ as, if $b=x_i$, for all $j < i$, logician $x_j$ will provide the correct answer.
Finally, let $p_t$ be the total parity bit and $p_e$ the parity bit considering only even positions.

Logician $x_1$ will detect a conflict using $p_e$ ($x_0$ and $x_1$ see the same number of "even" logicians) so he can deduce that $x_0 = b$ and $hat(b)=1$. Using then $p_t$ can deduce his color.

The claim is that no other logician will detect a clash.
Indeed the answer of $x_0$ is in conflict with both $p_t$ and $p_e$ and $x_1$ is able to provide the correct answer; as a result $p_t$ and $p_e$ can be seen as "disparity" bits (i.e. bits added so that the overall number of $1$s is odd). Using these bits $x_2$ will always deduce the wrong color, actually correcting the error, as a second error will make $p_t$ and $p_e$ be again parity bits. All subsequent logicians will not notice any clash and will be able to provide the correct answer.

Of course this solution makes sense only if $N>>6$ but it has the advantage of requiring a constant number of sacrifices.

Sorry for the way the solution is formulated, I'm sure a coding theorist will be able to state it in a more compact and elegant way (assuming I didn't make any mistake).