CLR cover
Previous problem

Problem 3: Magic Squares and the Thue-Morse Word

Next problem
\( \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \)

The goal of the problem is to build magic squares with the help of the infinite Thue-Morse word $\mathbf{t}$ on the binary alphabet $\{\sa{0},\sa{1}\}$ (instead of $\{\sa{a},\sa{b}\}$). The word $\mathbf{t}$ is $\mu^\infty(0)$ obtained by iterating the morphism $\mu$ defined by $\mu(0)=\sa{01}$ and $\mu(1)=\sa{10}$: $$\mathbf{t}=\sa{01101001100101101001}\cdots.$$ The $n\times n$ array $S_n$, where $n=2^m$ for a positive natural number $m$, is defined, for $0\leq i,j \le n$, by $$S_n[i,j] = \mathbf{t}[k](k+1) + (1-\mathbf{t}[k])(n^2-k),$$ where $k=i.n+j$. The generated array $S_4$ is

$\mathbf{16}$ $2$ $3$ $\mathbf{13}$
$5$ $\mathbf{11}$ $\mathbf{10}$ $8$
$9$ $\mathbf{7}$ $\mathbf{6}$ $12$
$\mathbf{4}$ $14$ $15$ $\mathbf{1}$
The array is a magic square because it contains all the integers from $1$ to $16$ and the sum of elements on each row is $34$, as well as the sums on each column and on each diagonal.

Show the $n\times n$ array $S_n$ is a magic square for any natural number $n$ power of $2$.

References

  • Magic squares on Wikipedia