What's the Number on My Hat?


A goblin forewarns N gnomes as follows: "Tomorrow morning, I shall place one hat on each of you. Each hat shall be labeled with some number drawn from the range [0, N-1]. Duplicates are allowed, so two different hats might have the same label. Any gnome shall be able to see numbers on other hats but not his own! When a bell rings, all gnomes shall simultaneously announce one number each. If any gnome succeeds in announcing the number on his own hat, all gnomes shall be set free." The gnomes have assembled in the evening to discuss their predicament. Can you help them devise a strategy?


From a puzzle collection by K Rustan M Leino at Microsoft Research.


For N = 2, numbers are drawn from the range [0, 1]. The following strategy works: The first gnome announces the number on the second gnome's hat. The second gnome announces the number that's not on the first gnome's hat.

In general, let gnomes be numbered 0 thru N-1. The i-th gnome should announce (i - s) mod N, where s is the sum of numbers he sees. With this strategy, if the sum of all N numbers equals m mod N, then the m-th gnome is guaranteed to announce the number of his own hat!

Thanks to Sreeram Ramachandran for solving this puzzle and sharing his solution with me.

How many cuts are necessary to cut an n x n x n cube into 1 x 1 x 1 cubes? Existing cuboids may be stacked together for cutting. So one cut may go through multiple existing cuboids.

(A) An 8x8 chessboard has had two of its diagonally opposite squares removed, leaving it with sixty-two squares. Can we tile it with 31 non-overlapping 2x1 rectangles (dominoes) such that all squares are covered? (B) Under what circumstances would removal of two squares from an 8x8 chessboard allow such a tiling? For example, if we remove an arbitrary white square and an arbitrary black square, can the remaining board be tiled?

21 Aug 2009
© Copyright 2008—2017, Gurmeet Manku.