この解説では、\(H = W\) を仮定します。

また、\(N := H = W, M := HW + 1\) とします。

M が合成数の場合

\(M\) が ( \(10\) 以上の) 合成数であると仮定します。 このとき、ほとんどの \(N\) で構築不可能なことが示せます。

Lemma 1 : \(M\) は \(5\) 以上の素因数をもつ。

\(M = N^2 + 1\) は \(3\) の倍数になり得ない。また、 \(4\) の倍数にもなり得ない。 したがって、 \(M\) は \(\frac{10}{2} = 5\) 以上の素因数をもつ。 \(\square\)

Lemma 2 : \(N \geq 11\) または \(N\) が偶数のとき、条件を満たす書き込み方は存在しない。

Lemma 1 で存在が示された素因数を \(p \, (\geq 5)\) とおく。

このとき、 \(2 \times 2\) マスに含まれる \(4\) 要素の積は \(p\) の倍数でなければならないことに注目する。 \(1, 2, \ldots, N \times N\) のなかに \(p\) の倍数は \(\lfloor{ \frac{N \times N}{p} \rfloor} \leq \lfloor{ \frac{N \times N}{5} \rfloor} \) 個存在し、これらをどの \(2 \times 2\) マスにも含まれるように配置しなければならない。 しかし、これは基本的に不可能である。

• \(N\) が偶数のとき

上のように配置するためには、 \(p\) の倍数が最低でも \(\frac{N}{2} \times \frac{N}{2} = \frac{N \times N}{4}\) 個必要である。この値は常に \(\lfloor{ \frac{N \times N}{5} \rfloor}\) より大きいため、配置不可能。

• \(N\) が奇数のとき

上のように配置するためには、 \(p\) の倍数が最低でも \(\frac{N-1}{2} \times \frac{N-1}{2} = \frac{(N-1) \times (N-1)}{4}\) 個必要である。この値は \(N \geq 11\) のとき、 \(\lfloor{ \frac{N \times N}{5} \rfloor}\) よりも大きくなる。 \(\square\)

Lemma 2 より、 \(N = 3, 5, 7, 9\) のケースを個別に調べることにします。

• \(N = 3, M = 10\) のとき、 \(R = 0\) であれば下図のように構築可能。
• \(N = 5, M = 26\) のとき、 \(M\) の素因数 \(13\) に注目すると構築不可能。
• \(N = 7, M = 50\) のとき、構築可能な \(R\) は \(25\) の倍数に限られる。しかし、 \(1, 2, \ldots, N \times N\) には \(5\) の倍数が \(9\) 個しか存在しないため、構築不可能。
• \(N = 9, M = 82\) のとき、 \(M\) の素因数 \(41\) に注目すると構築不可能。

\(N = 3, R = 0\) の構築方法

{1, 2, 3}, 
{4, 5, 6},  
{7, 8, 9}

M が素数の場合

\(R = 0\) の場合は、明らかに No です。以後、 \(R \gt 0\) とします。

\(M\) の原始根 \(r\) を底とする離散対数をとると、次のような構築が可能か、という問題に置き換わります：

• \(0, 1, \ldots, M-2 = N \times N - 1\) がちょうど一度ずつ登場する
• どの \(2 \times 2\) 小行列をとっても、その中にある \(4\) 要素の和 \(\pmod{M-1}\) が \(\log_r{R} \pmod{M-1}\) に等しい。ただし、 \(\log_r{R}\) は \(r^{\log_r{R}} \equiv R \pmod{M-1}\) を満たす、 \(0\) 以上 \(M-2\) 以下の整数とする。

\(N\) は偶数のため、 \(4\) 要素の和を \(M-1 = N^2\) で割ったあまりを \(s\) とおくと、

\[ s \times \left( \frac{N}{2} \right)^2 \equiv \frac{N^2 \times (N^2-1)}{2} \equiv \frac{N^2}{2} \pmod{N^2} \]

が成り立たなくてはなりません。 つまり、 \(\log_r{R}\) は \(2, 6, 10, \ldots, N^2 - 2\) のいずれかである必要があります。

そして、この条件が構築可能性の十分条件になっています。 なぜならば、

{ 0, 15,  1, 14}, 
{13,  2, 12,  3}, 
{ 4, 11,  5, 10}, 
{ 9,  6,  8,  7}

のように、和が一定である適当な構築を与えたのち、すべてのマスの値を \(1\) 増やす操作を繰り返せばよいからです。

あとは、和のほうで \(a\) と書かれたマスに \(r^a \% M\) を対応させれば、目的の書き込み方が得られます。