18. 88 Hats
The Puzzle
The “88 Hats” puzzle was
posed by Andrew Nikitin
to the J Forum on 2007-06-05
[65].
The following is a slightly modified version.
88 people stand in a circle, each having a hat
with a number from 0 to 87 written on it.
Everyone can see the numbers on other people’s
hats but can not see his own number.
They simultaneously write a number on a piece
of paper and give it to the judge.
If at least one of them wrote a number that is
on his own hat then everyone wins, otherwise everyone loses.
What strategy should they use to guarantee victory?
(Numbers on the hats do not have to be all different.
People can not exchange any information during the procedure
but can agree on a strategy beforehand.)
The puzzle was solved by John Randall a day later
[66].
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 ⍪ ⍉⍪ 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.
| numbering | | writing |
| 0 0 | | 0 1 |
| 0 1 | | 1 1 |
| 1 0 | | 0 0 |
| 1 1 | | 1 0 |
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 the previous section 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] .
88 Hats
The original puzzle has m←88 . Since
⍸ 88 = {+/1=⍵∨⍳⍵}¨ ⍳1000
89 115 178 184 230 276
There are at least 7 different strategies,
derived from addition modulo 88 and multiplication
modulo each b of 89 115 178 184 230 276
on the numbers
co-prime to b . Thus:
assert←{⍺←'assertion failure' ⋄ 0∊⍵:⍺ ⎕signal 8 ⋄ shy←0}
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.×⍵
}
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←{⍵|∘.×⍨⍸ 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
⍸ h = win h
58
⍸ h = (mgrp 89) win h
5
⍸ h = (mgrp 115) win h
87
⍸ h = (mgrp 178) win h
27
⍸ h = (mgrp 184) win h
77
⍸ h = (mgrp 230) win h
82
⍸ 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
Appeared in J in
[67]
and in APL in
[68].
|