88 Hats 0. The Puzzle The “88 Hats” puzzle was posed by Andrew Nikitin to the J Forum on 20070605. The following is a slightly modified version.
The puzzle was solved by John Randall a day later. 1. A Winning Strategy The strategy works for any number of hats m . Beforehand, the people number themselves from 0 to m1 . 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 mns[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 ms[t]+ts[t] ⍝ addition and subtraction ms[t]+mts[t] ⍝ modulo arithmetic ms[t]+w[t] ⍝ definition of w Moreover, since s[t] is the sum of all hats excluding h[t] , it must be that t=ms[t]+h[t] . Therefore ms[t]+w[t] and ms[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 mns[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 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 3. 88 Hats The original puzzle has m←88 . Since I←{⍵/⍳⍴⍵} I 88 = {+/1=⍵∨⍳⍵}¨⍳1000 89 115 178 184 230 276There 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 coprime to b . Thus: 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 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 coprime 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.×⍵ } Originally appeared as a Jwiki essay on 20070608; also in Vector, Volume 25, Number 4, 201211.
