88 Hats
Roger Hui
 

0. The Puzzle

The “88 Hats” puzzle was posed by Andrew Nikitin to the J Forum on 2007-06-05. The following is a slightly modified version.

The puzzle was solved by John Randall a day later.

Solution below.

1. A Winning Strategy

The strategy works for any number of hats m . Beforehand, the people number themselves from 0 to m-1 . Let h be the list of hat numbers, and s[n] be the sum of the numbers that person n sees. Then w[n] , the number that person n writes, is m|n-s[n] .

   m←13
   random←{⎕rl←7*5 ⋄ ?⍵}  ⍝ reproducible random numbers

   ⊢ h←random m⍴m
1 9 5 6 2 0 8 8 12 4 6 10 0

   ⊢ s←(∘.≠⍨⍳m)+.×h
70 62 66 65 69 71 63 63 59 67 65 61 71

   ⊢ w←m|(⍳m)-s
8 4 1 3 0 12 8 9 1 7 10 2 6

   w ,[¯0.5] h
8 4 1 3 0 12 8 9  1 7 10  2 6
1 9 5 6 2  0 8 8 12 4  6 10 0

   +/ w=h
1

Here’s why it works. Let t←m|+/h be the sum of all the hat numbers, modulo m . The following are equal:

t
m|s[t]+t-s[t]          ⍝ addition and subtraction
m|s[t]+m|t-s[t]        ⍝ modulo arithmetic
m|s[t]+w[t]            ⍝ definition of w

Moreover, since s[t] is the sum of all hats excluding h[t] , it must be that t=m|s[t]+h[t] . Therefore m|s[t]+w[t] and m|s[t]+h[t] are equal and so w[t] and h[t] are equal. That is, the written number w[t] for person t matches his hat number h[t] .

   ⊢ t←m|+/h
6
   w[6]
8
   h[6]
8

It is instructive to examine what the “winning strategy” does for 2 hats. The strategy calls for person n to write m|n-s[n] . When m←2 , this reduces to person 0 writing the hat number of person 1 and person 1 writing the negation of the hat number of person 0. The tabulation of all possible hat numberings and corresponding writings shows that in each scenario there is a written number that equals a hat number.

2. An Abstraction

Let G be an abelian group of size m with operation g and whose group members are items of u . Compute s←{g/(⍵≠⍳m)/u[h]}¨⍳m ; s[n] is the “sum” of hat numbers that person n sees. Then the written number w[n] is u⍳u[n] g gi s[n] where gi x is the inverse of x in the group. (In Section 1 G is the group of integers under addition modulo m ; the group elements u are ⍳m .)

Why does it work? Let t←u⍳g/u[h] be the index of the “sum” of all the hat numbers. The following are equal:

u[t]
u[t] g s[t] g gi s[t]  ⍝ group inverse and identity
s[t] g u[t] g gi s[t]  ⍝ associative and commutative
s[t] g u[w[t]]         ⍝ definition of w

Moreover, since s[t] is the sum of all hats excluding u[h[t]] and the group is abelian, it follows that u[t]=s[t] g u[h[t]] . Therefore s[t] g u[w[t]] and s[t] g u[h[t]] are equal, and so u[w[t]] and u[h[t]] are equal and consequently w[t] and h[t] are equal. That is, the written number w[t] for person t matches his hat number h[t] .
 

3. 88 Hats

The original puzzle has m←88 . Since

   I←{⍵/⍳⍴⍵}
   I 88 = {+/1=⍵∨⍳⍵}¨⍳1000
89 115 178 184 230 276

win←{   
 ⍝ winning strategy based on group table ⍺ for hat numbering ⍵
    assert ⍵∊⍳m←⍴⍵:
    ⍺←m|∘.+⍨⍳m       ⍝ default is + modulo m
    assert(⍴⍺)≡m,m:
    assert ⍺≡⍉⍺:     ⍝ must be abelian
    G←⍺[0;]⍳⍺        ⍝ standardize group table
    g←{G[⍺;⍵]}¨      ⍝ group operation
    gi←{G[⍵;]⍳0}¨    ⍝ inverses
    (⍳m) g gi (∘.≠⍨⍳m)g.×⍵
}

assert←{⍺←'assertion failure' ⋄ 0∊⍵:⍺ ⎕SIGNAL 8 ⋄ shy←0}

The left argument ⍺ of win is a group table. It is standardized by doing ⍺[0;]⍳⍺ , whence the group elements are ⍳m and the identity element is 0 . These properties permit the computation of the “all but” sums to be simplified from {g/(⍵≠⍳m)/u[h]}¨⍳m to (∘.≠⍨⍳m)g.×h .

mgrp←{⍵|∘.×⍨I 1=⍵∨⍳⍵}  ⍝ group table for × modulo ⍵

   mgrp 7
1 2 3 4 5 6
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
5 3 1 6 4 2
6 5 4 3 2 1

   mgrp 9
1 2 4 5 7 8
2 4 8 1 5 7
4 8 7 2 1 5
5 1 2 7 8 4
7 5 1 8 4 2
8 7 5 4 2 1

mgrp ⍵ computes the group table for the integers under multiplication modulo ⍵ . The group elements are the numbers co-prime to ⍵ .

   m←88
   h←random m⍴m

   I h = win h
58

   I h = (mgrp  89) win h
5
   I h = (mgrp 115) win h
87
   I h = (mgrp 178) win h
27
   I h = (mgrp 184) win h
77
   I h = (mgrp 230) win h
82
   I h = (mgrp 276) win h
58

Even though win h and (mgrp 276) win h result in the same person (58) writing his hat number, the lists of written numbers are different:

   win h
41 9 72 79 53 39 7 8 32 72 85 26 45 47 2 16 46 80 53 ...
   (mgrp 276) win h
70 39 78 9 47 11 47 52 48 20 70 32 26 60 2 76 46 16 ...

   (win h)[58]
5
   ((mgrp 276) win h)[58]
5
   h[58]
5

4. Collected Definitions

assert←{⍺←'assertion failure' ⋄ 0∊⍵:⍺ ⎕SIGNAL 8 ⋄ shy←0}

I←{⍵/⍳⍴⍵}

mgrp←{⍵|∘.×⍨I 1=⍵∨⍳⍵}  ⍝ group table for × modulo ⍵

random←{⎕rl←7*5 ⋄ ?⍵}  ⍝ reproducible random numbers

win←{
 ⍝ winning strategy based on group table ⍺ for hat numbering ⍵
    assert ⍵∊⍳m←⍴⍵:
    ⍺←m|∘.+⍨⍳m       ⍝ default is + modulo m
    assert(⍴⍺)≡m,m:
    assert ⍺≡⍉⍺:     ⍝ must be abelian
    G←⍺[0;]⍳⍺        ⍝ standardize group table
    g←{G[⍺;⍵]}¨      ⍝ group operation
    gi←{G[⍵;]⍳0}¨    ⍝ inverses
    (⍳m) g gi (∘.≠⍨⍳m)g.×⍵
}