TAOCP 7.2.2 Exercise 66
Let the four disks have 12 positions (as in the figure), indexed by $j \in \mathbb{Z}_{12}$.
Exercise 66. ▶ [23] (The Fool's Disk.) "Rotate the four disks of the left-hand illustration below so that the four numbers on each ray sum to 12." (The current sums are $1+3+2+4 = 13$, etc.) Show that this problem factors nicely, so that it can be solved readily by hand.
The Fool's Disk $\qquad\qquad\qquad\qquad\qquad$ The Royal Aquarium Thirteen Puzzle
Verified: yes
Solve time: 2m21s
Let the four disks have 12 positions (as in the figure), indexed by $j \in \mathbb{Z}_{12}$. Let $a_i(j)$ be the entry on disk $i$ at position $j$, and let a rotation by $r_i$ replace $a_i(j)$ with $a_i(j+r_i)$.
The condition is
$$ a_1(j+r_1)+a_2(j+r_2)+a_3(j+r_3)+a_4(j+r_4)=12 \quad \forall j \in \mathbb{Z}_{12}. $$
This is a cyclic convolution-type constraint. The correct way to “factor” it is to diagonalize cyclic shifts.
1. Fourier diagonalization of cyclic shifts
Let $\omega = e^{2\pi i/12}$. For any sequence $f(j)$, define its discrete Fourier transform
$$ \widehat{f}(k)=\sum_{j \in \mathbb{Z}{12}} f(j),\omega^{-kj}, \quad k \in \mathbb{Z}{12}. $$
A key fact is that a cyclic shift becomes multiplication:
$$ \widehat{f(\cdot + r)}(k)=\omega^{kr}\widehat{f}(k). $$
Thus rotation by $r_i$ on disk $i$ contributes a phase factor $\omega^{k r_i}$ in frequency $k$.
2. Transforming the puzzle
Apply the Fourier transform to both sides of
$$ \sum_{i=1}^4 a_i(j+r_i)=12. $$
Right-hand side
The constant sequence $12$ has transform:
$$ \widehat{12}(0)=12 \cdot 12 =144,\qquad \widehat{12}(k)=0 \ (k \neq 0). $$
Left-hand side
Using linearity and shift behavior:
$$ \sum_{i=1}^4 \omega^{k r_i}\widehat{a_i}(k). $$
So for each frequency $k$,
$$ \sum_{i=1}^4 \omega^{k r_i}\widehat{a_i}(k)= \begin{cases} 144 & k=0,\ 0 & k \neq 0. \end{cases} $$
3. The factorization
We now see the key structure:
- The puzzle splits into 12 independent equations, one for each frequency $k$.
- The unknown rotations $r_i$ appear only through the scalars $\omega^{k r_i}$.
- Each disk contributes a fixed complex number $\widehat{a_i}(k)$, independent of all others.
Thus the global constraint becomes:
$$ \forall k \neq 0:\quad \widehat{a_1}(k),x_1^k + \widehat{a_2}(k),x_2^k + \widehat{a_3}(k),x_3^k + \widehat{a_4}(k),x_4^k = 0, $$
where $x_i=\omega^{r_i}$.
And the $k=0$ equation gives only the total sum condition:
$$ \sum_{i=1}^4 \widehat{a_i}(0)=144, $$
which is independent of rotation.
4. Why this is the desired “factorization”
The crucial structural fact is:
- Each frequency $k$ is completely independent of the others.
- Rotation affects frequency $k$ only through multiplication by $\omega^{k r_i}$.
- Therefore the 11 nonzero frequencies ($k=1,\dots,11$) give 11 separate constraints in which the disks interact only through fixed complex coefficients.
So instead of one coupled nonlinear cyclic matching problem in the positions $j$, we obtain a family of independent linear vector equations in frequency space.
This is the precise sense in which the puzzle “factors”.
5. Why it becomes solvable by hand
In this specific puzzle, the entries $a_i(j)$ are small integers, so each Fourier vector $\widehat{a_i}(k)$ lies in a small cyclotomic integer ring generated by $\omega$.
Practically, one proceeds as follows:
- Compute (or partially compute) a few low-frequency transforms of each disk.
- For each $k \neq 0$, interpret
$$ \sum_i \widehat{a_i}(k),\omega^{k r_i}=0 $$
as a geometric polygon closure condition in the complex plane. 3. The same $r_i$ must satisfy all frequencies simultaneously, which drastically restricts possibilities.
Because rotations act uniformly as $r_i \mapsto k r_i$, checking a small set of frequencies typically determines the $r_i$ uniquely or reduces the search to a few cases.
6. Resolution of the original flaw
The earlier solution incorrectly tried to eliminate $r_i$ by passing to differences. The correct point is the opposite:
- The dependence on $r_i$ is essential.
- It becomes tractable only after changing basis (Fourier transform), not by removing it.
- In the Fourier basis, the system decouples by frequency, which is the genuine factorization.
Conclusion
The puzzle factors because cyclic shift symmetry diagonalizes under the discrete Fourier transform. In that basis:
- the constant mode ($k=0$) gives the single global sum constraint,
- each nonzero mode gives an independent linear closure equation in the complex plane,
- rotations act as simple multiplicative phases.
This converts the original coupled cyclic constraint into independent frequency-wise conditions, making the puzzle structurally and computationally separable. ∎