This post contains my proposed solution to Problem #018 - circle of hats. Please do not read this solution before making a serious attempt at the problem.

Solution

The answer is really interesting and can be formulated in mathematical terms in a rather simple way; after that I will walk you through what the mathematical formulation means with some doodles I drew.

Let \(a_i\) be the number in the hat of the \(i\)th mathematician and \(g_i\) be the guess the \(i\)th mathematician writes down. Then \(g_i\) satisfies the equation

\(g_i + \sum_{j \neq i} a_j \equiv i \hspace{0.5cm} \text{mod } n\)

What follows from here is that if \(k \equiv \sum_i a_i \text{ mod } n\), then the \(k\)th mathematician will get its guess right and all other mathematicians will fail.

Why it works (mathematically)

Let \(a_i, g_i\) be as above and let \(k = \sum_i a_i \text{ mod } n\). Notice how

\(g_k + \sum_{j \neq k} a_j \equiv k \iff g_k \equiv k - \sum_{j \neq k} a_j.\)

Of course, we defined \(k = \sum_i a_i\) so the above becomes

\(g_k = \sum_{j} a_j - \sum_{j \neq k} a_j = a_k \hspace{0.5cm} \text{mod } n,\)

hence the \(k\)th mathematician will guess correctly.

Explanation of the solution

Let us take \(n = 5\) and number the mathematicians from \(0\) to \(4\), starting from the top and going in the clockwise direction. The numbers inside the circles represent the numbers in the hats, that I distributed randomly.

hat-configuration.png

Now we pretend we are the mathematician number \(0\), and so we see the numbers \(0\), \(3\), \(0\) and \(1\), which give \(4\) when added up. Now, we are the mathematician \(0\) so our guess \(g_0\) is how much is left to go from \(4\) to \(0\) which is... \(1\), so that is our guess.

In case you are not familiar with modular arithmetics, adding and subtracting is just like you are used to, but numbers wrap around the modulus that in this case is \(5\). This is like the hours in a day wrapping around \(24\)! To do additions and subtractions modulo \(5\), just look at the small numbers next to the mathematicians and count clockwise when adding, counter-clockwise when subtracting. For example, \(3 + 3\) is \(1\) because if you start at mathematician \(3\) and you count \(3\) mathematicians starting from that one, you end up at mathematician \(1\).

To recap, mathematician \(0\) guessed \(1\) because the other mathematicians' hats added up to \(4\) and \(4 + 1 \equiv 0\) modulo \(5\). Unfortunately, the mathematician got it wrong because its hat had a \(3\) on it...

hat-0.png

Mathematician \(1\) sees \(3\), \(0\), \(1\) and \(3\), which add up to \(3 + 0 + 1 + 3 \equiv 2\) mudulo \(5\) and to get to \(1\) we must add \(4\), so mathematician \(1\) guesses \(4\), which is also wrong...

hat-1.png

Then came mathematician \(2\) who sees \(0\), \(1\), \(3\) and \(0\), adding up to \(4\). Now, to get from \(4\) to \(2\) modulo \(5\) we need to add \(3\), which is what our mathematician guesses... and it is correct!

hat-2.png

Just for the sake of completeness, can you tell what mathematicians \(3\) and \(4\) will write down as their guesses..? Hint: none of them will get it right.

all-hats.png

A piece of code for you to play with

I wrote a small piece of APL code so you can check for yourself which mathematician writes down its number correctly, just follow this link and change the numbers in the last line to whatever you like, then hit the arrow on the top to run the code:

HatSolver ← {
    ⎕IO ← 0  ⍝ IO delenda est
    n ← ≢⍵
    s ← ⍵ - ⍨ +/⍵
    ⍵ = n| s -⍨ ⍳n
}

⎕← HatSolver 3 0 3 0 1

I included the example from this blog post in the code, the 3 0 3 0 1 you can see above. The numbers that get printed show a \(0\) for every mathematician that fails and shows a \(1\) for the mathematician that guesses correctly.

If you have any questions about my solution, found any mistakes (whoops!) or would like to share your solution, be sure to leave a comment below.

Previous Post Next Post

Blog Comments powered by Disqus.