hats_intuition.md

Here is an intuition or visualization on the modulo solution for the hats problem.

These are the sources that have helped me understand it:

• http://www.cut-the-knot.org/blue/PuzzleWithHats.shtml#solution
• http://www.cs.cornell.edu/~rdk/papers/hats.pdf

Following the notation and reasoning used on cut-the-knot, the sum of all of the hats numbers is a unique number S. Let's call s_i to the sum of all the hats numbers except for the hat of player i, which is the sum of all hats player i can see.

There are n players and n types of hats and each hat is numbered from 0 to n - 1. Because the sum of the number of every player is needed to obtain S, then S - s_i <= n - 1 for all i.

For every pair of players, x and y, the maximum distance from s_x or s_y to S is n - 1 which is also the maximum distance between their most distant guesses and S. The range of possible guesses for this pair G_xy can't be longer than 2(n - 1) + 1 = 2n - 1. Note that this range will always include S.

Now go to https://en.wikipedia.org/wiki/Modular_arithmetic and take a look at the clock analogy for modular arightmetic.

Because the largest distance to S inside G_xy is at much n - 1 either from below or from above, S mod n will be unique in the range G_xy mod n. That is, when wrapping the range G_xy mod n around the modular clock S mod n is the only number that can't be wrapped twice.

I can't draw clocks in pseudo-markdown, but I will write a table to illustrate it. For illustrative purposes assume the extreme case in which the distance S - s_x = n - 1, the distance S - s_y = 0 and n = 6. Here is the flattened clock.

Gx	sx and gx,1	gx,2	gx,3	gx,4	gx,5	S and gx,6
Gy						sy, S and gy,1	gy,2	gy,3	gy,4	gy,5	gy,6
Rxy	a	b	c	d	e	f = S mod n	a	b	c	d	e

• g_i,j is the j^th guess of player i. The first guess g_i,1 = s_i + 0, the second g_i,2 = s_i + 1, ... where their answers are 0, 1, ... respectively.
• G_i is the set of guesses for player i
• In the last row R_xy = G_xy mod n, where G_xy is the union of set G_x and G_y. Each letter on R_xy represents a different remainder mod n.

S mod n = f in this case and it will be equal for every player because n and S, although unknown, are the same for every player. Also it will be unique because S - s_i <= n - 1, that is, guesses can't wrap around S mod n = f twice.

So if there are n players and every player is asigned a different remainder mod n, the one which was asigned S mod n will answer right which means that at least 1 person will always answer right. Note that for other remainders the guess could vary depending on the player's s_i but this will never happen for S mod n. In the illustration above, for remainder a, x would guess g_x,1 = s_x + 0 and answer 0 whereas y would guess g_y,2 = s_y + 1 and answer 1

Formatting

This isn't a regular markdown document, I have played around with Github formatting rules to achieve an acceptable result.