How High Can You Count With Menorah Math?

The Riddler for December 11, 2020. The Express encodes nights on a menorah readable from either side, and the Classic finds a hat-guessing strategy that guarantees a survivor.

Riddler Express

A menorah has eight candle positions (besides the central shamash), each lit or unlit. You want to encode as many distinct “nights” as possible, but the menorah is viewed from both the front and the back, so a pattern and its left–right reversal must indicate the same night. What is the greatest number of nights you can represent?

The Riddler, FiveThirtyEight, December 11, 2020(original post)

Solution

Each of the $8$ positions is a bit, giving $2^8 = 256$ patterns. A front viewer sees a pattern $p$; a back viewer sees its reversal. To make the night unambiguous from either side, assign each night either a symmetric pattern (equal to its own reversal, so both sides agree) or a mirror pair of asymmetric patterns (front sees one, back sees the other, both decoding to the same night).

Symmetric patterns are fixed by their left half: $2^4 = 16$ of them. The remaining $256 - 16 = 240$ are asymmetric, forming $240/2 = 120$ mirror pairs. Each symmetric pattern and each mirror pair encodes one night, so $$16 + 120 = \boxed{136}$$ distinguishable nights, far more than ternary pair-coding ($3^4 = 81$) and beating a naive palindromes-only scheme ($16$).

The computation

Encode every $8$-bit pattern, group each with its reversal, and count the distinct unordered groups.

groups = set()
for p in range(256):
    bits = format(p, '08b')
    rev = bits[::-1]
    groups.add(frozenset({bits, rev}))   # a symmetric pattern pairs with itself
print(len(groups))                       # 136

The menorah can track $136$ nights.

Riddler Classic

Five citizens each get a red, green, or blue hat. They are split into a row of two ($A, B$) and a row of three ($C, D, E$); each row sees the other row but not itself, and each knows their own position. With no communication, all guess their own hat colour simultaneously. What strategy guarantees at least one correct guess?

The Riddler, FiveThirtyEight, December 11, 2020(original post)

Solution

Code the colours $0, 1, 2$ and let the hat values be $a, b$ (row of two) and $c, d, e$ (row of three). The row of three sees $a, b$; the row of two sees $c, d, e$. A guaranteed strategy:

• $C$ guesses $a$, $D$ guesses $b$, $E$ guesses $(a + b) \bmod 3$.

If any of $C, D, E$ is right, the group survives. So $A$ and $B$ may assume all three are wrong, which means $a \neq c$, $b \neq d$, and $(a + b) \not\equiv e \pmod 3$. Under those three constraints, with $s = (e - c - d) \bmod 3$:

• $A$ guesses $c + 1$ if $s \in \{0, 1\}$, else $c + 2$ (mod $3$);

• $B$ guesses $d + 2$ if $s \in \{0, 2\}$, else $d + 1$ (mod $3$).

Working through the three cases of $s$, the two-to-four surviving $(a, b)$ possibilities are always covered by $A$ or $B$, so whenever $C, D, E$ all fail, at least one of $A, B$ succeeds. Either way, $$\boxed{\text{at least one citizen always guesses correctly.}}$$

The computation

Encode the strategy and check all $3^5 = 243$ hat assignments: in every case at least one guess is right.

import itertools
def survives(a, b, c, d, e):
    gC, gD, gE = a, b, (a + b) % 3            # row of three see A, B
    s = (e - c - d) % 3
    gA = (c + 1) % 3 if s in (0, 1) else (c + 2) % 3
    gB = (d + 2) % 3 if s in (0, 2) else (d + 1) % 3
    return gC == c or gD == d or gE == e or gA == a or gB == b
print(sum(survives(*t) for t in itertools.product(range(3), repeat=5)))  # 243

All $243$ colourings survive, so the strategy is guaranteed.