Guess the colour or die

The solution

Only the first prisoner to answer is devoted to die because his mission is to give the essential information to the others. In this way at least $n-1$ prisoners will survive regardless the number of colours. It makes 2019 prisoners the right answer to the question.

Explanation

Let's assign the numbers to the colours, e.g. blue = 0, black = 1, purple = 2 and so on up to $k-1$ . The first person adds up all the numbers he sees and gets the sum $S_1$ and says the result of $S_1 \mod k$ operation . Denote the colour of $i$ th hat with $a_i$ .  The algorithm is the following:

1. First prisoner calculates $S_1 \mod k  = m_1$ and says the colour corresponding to $m_1$ .
2. The second prisoner sees the sum of all hats equal to $S_2$ . He must subtract the colour $a_1$ of the first prisoner $S_2' = S_2 - a_1$ . Then, he calculates: $S_2' \mod k  = m_2$ . The colour $a_2$ of his hat is the result of: $(m_1 - m_2) \mod k$ . He says the colour corresponding to $a_2$ .
3. The third prisoner sees the sum of all hats is equal to $S_3$ . He must subtract the colour of the first prisoner $S_3' = S_3 - a_1$ . Then, he calculates: $S_3' \mod k  = m_3$ . The color of his hat $a_3$ is the result of: $(m_1 - m_3) \mod k$ . He says the colour corresponding to $a_3$ .

It continues so as long as all prisoners say the colours. In this way $n-1$ prisoners will survive. It makes $2019$ prisoners the right answer to the question for $n = 2020$ .

Derivation

Assume the sum of all the colours is $S = a_1 + a_2 + \ldots + a_n$ . The first prisoner sees the sum $S_1 = a_2 + a_3 + \ldots + a_n = S - a_1$ . The $i$ th prisoner sees the sum $S_i = S - a_i$ . Note that $S_i = S - a_1 + a_1 - a_i = S_1 + a_1 - a_i$ . He wants to guess $a_i$ . He can calculate it from $a_i = S_1 - S_i + a_1 = S_1 - (S_i - a_1)$ . The prisoners are allowed only to say colors not the sums. One can notice that $a_i = a_i \mod k$ for each colour. We can use the modulo operation to extract the important information for us: $a_i = S_1 \mod k - (S_i - a_1) \mod k$ . This is exactly what happens in the listed algorithm steps.

Example

Let's check it for $k=3$ colours (blue = 0, black = 1, purple = 2) and $n=10$ prisoners. With the numbers assigned we would have e.g. the hats: $2,\; 0,\; 1,\; 0,\; 0,\; 2,\; 2,\; 1,\; 2,\; 1$ . Let's start from the left:

1. First prisoner (with purple $a_1 = 2$ hat) sees the sum $S_1 = 0+1+0+0+2+2+1+2+1 = 9$ and says "blue" ( $0$ ) because $m_1 = (0+1+0+0+2+2+1+2+1) \mod 3 = 9 \mod 3 = 0$
2. Second prisoner (with blue $a_2 = 0$ hat) sees the sum $S_2 = 2+1+0+0+2+2+1+2+1 = 11$ . He subtracts the colour of the first prisoner $11 - 2 = 9$ . He calculates $m_2 = 9 \mod 3 = 0$ . Now, he needs to calculate $(m_1 - m_2) \mod 3 = (0 - 0) \mod 3 = 0$ . This corresponds to the hat on his head. The colour is blue.
3. Third prisoner (with black $a_3= 1$ hat) uses the information from the first one: $m_1 = 0$ . He sees the sum $S_3 = 2+0+0+0+2+2+1+2+1 = 10$ . He subtracts the color of the first prisoner $10 - 2 = 8$ . He calculates $m_2 = 8 \mod 3 = 2$ . Now, he needs to calculate $(m_1 - m_2) \mod 3 = (0 - 2) \mod 3 = 1$ .

And so does each next prisoner until all prisoners say their colours.