Five elders are sitting around a large bonfire. They know that Oluf will put a hat of one of four colours (red, green, blue or yellow) on each elder’s head, and after a short time for silent reflection each elder will have to write down one of the four colours on a piece of paper. Each elder will only be able to see the colour of their two neighbours’ hats, not that of their own nor that of the remaining two elders’ hats, and they also cannot communicate after Oluf starts putting the hats on. Show that the elders can devise a strategy ahead of time so that at most two elders will end up writing down the colour of their own hat
Problem
Source: 2022 Baltic Way p9
Tags: combinatorics, Coloring
ERR0R400
13.11.2022 10:54
it is obvious that you need 2 adjacent elders to guess correctly to have more than 2 elders write their own color, making that impossible would be sufficient.
we describe the colors as the numbers 1 through 4, and define an operation x (found by setting up criteria and solving a sudoku-like system) such that
1 x 1 = 2, 1 x 2 = 3, 1 x 3 = 3, 1 x 4 = 2
2 x 1 = 2, 2 x 2 = 3, 2 x 3 = 3, 2 x 4 = 2
3 x 1 = 1, 3 x 2 = 4, 3 x 3 = 4, 3 x 4 = 1
4 x 1 = 1, 4 x 2 = 4, 4 x 3 = 4, 4 x 4 = 1
and make the elders guess 'hat to the left x hat to the right'
we now look at all sequences of 3 hats that give a correct guess
{121, 132, 133, 124, 221, 232, 233, 224, 311, 342, 343, 314, 411, 442, 443, 414}
and see that no 2 leading digits match up with 2 ending digits, or in other terms
{12, 13, 22, 23, 31, 34, 41, 44} and {21, 32, 33, 24, 11, 42, 43, 14} share no elements, making 2 adjacent correct guesses impossible so you can't have more than 3 correct guesses, which was what we needed.