# Yet Another Puzzle with Hats

There is a great variety of puzzles where wise people sit in a circle seeing each other's hat but not their own. The task before each of them is to guess his own kind of hat.

The puzzle below has been communicated to me by Anany Levitin, an old classmate of mine. Later on I came across an article *A Dozen Hat Problems* by Ezra Brown and James Tanton (Math Horizons, v 16, nr 4, April 2009, pp. 22-25) in which is was problem #2, with #1 as a simplified, warm-up version. The problem is about hats and guessing, but does not assume equal wisdom of the participants nor does it require each of them to come up with the correct answer. Just one of them needs to hit on the right response. The puzzle is as follows:

*N* > 1 people sit in a circle clearly seeing all others. They are going to be blindfolded and, while in this state, hats are put on their heads - one per person, naturally. On each hat there is written a number from 0 to *N*-1. The numbers may be different or some may be equal. Nothing is known about that, except that each is picked up from the set *N*-1}.

This is the puzzle. But there is one more stipulation: before blindfolds were put on, the proceedings of the experiment were explained to the participants. At this point they were allowed to discuss the matter and devise a protocol, i.e., the manner in which they would be going to make their guesses. Subsequently, no communication would be possible.

Can you devise a protocol that will guarantee at least one right guess?

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1966-2016 Alexander Bogomolny

*N* > 1 people sit in a circle clearly seeing all others. They are going to be blindfolded and, while in this state, hats are put on their heads - one per person, naturally. On each hat there is written a number from 0 to *N*-1. The numbers may be different or some may be equal. Nothing is known about that, except that each is picked up from the set *N*-1}.

This is the puzzle. But there is one more stipulation: before blindfolds were put on, the proceedings of the experiment were explained to the participants. At this point they were to allowed to discuss the matter and devise a protocol, i.e., the manner in which they would be going to make their guesses. Subsequently, no communication would be possible?

Can you devise a protocol that will guarantee at least one right guess?

### Solution

Consider one of the participants. The fellow sees the numbers on all others' hats, but his own. Let his number be *x* and denote the sum of the numbers on all *N* hats as *S*. Summing up the numbers visible to him, the fellow can find *S* - *x*.

Here's a solution that makes use of the arithmetic modulo *N*. During the preliminary discussion each of the participants was assigned a unique number from the set of the *residues* *N*-1}.*a* is the number assigned to a generic participant. It was agreed that, when the time comes, each would write a residue (modulo *N*) *y* such that

*S* - *x* + *y* = *a* (mod *N*).

The reasoning for this behavior is simple enough. The unknown *S* is equivalent to some *s* from the set *N*-1}.

*s* - *x* + *y* = *a* (mod *N*).

Since all *a*'s assigned were different, one of them is necessarily equal to *s*. For this participant, the latter equation becomes

*s* - *x* + *y* = *s* (mod *N*),

or,

*x* - *y* = 0 (mod *N*).

Since both *x* and *y* are residues modulo *N*, this implies their equality: *x* = *y*,

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1966-2016 Alexander Bogomolny

64475279 |