積の魔方陣は構成できるか？

※この記事は苫小牧高専アドベントカレンダー2020 10日目の記事です。

adventar.org

9日目の記事はまだ上がっていないようです。高専という感じがして好きですよ。

というわけで10日目はみみねこが担当します。Twitterをやっているので是非フォローしてください。
→みみねこ (@3_3_nk) | Twitter

高専といえば勉強ですね！勉強といえば数学！というわけで今日は数学の話をします。

はじめに：魔方陣とは
積魔方陣を定義する
和魔方陣から積魔方陣を構成する
サイズの小さい積魔方陣を構成したい
素因数が2つ存在する積魔方陣
ラテン方陣とオイラー方陣について
各要素が互いに素な集合を探す
他の次元の積魔方陣も構成してみる
結論
課題

はじめに：魔方陣とは

魔方陣って知ってますか？知らない人はWikipediaを読んでください。

魔方陣 - Wikipedia

簡単に言うと、異なる数字を正方形状に並べたとき、その各行・各列（・各対角線）の和がそれぞれ等しくなるようなものを魔方陣といいます。縦横にそれぞれ $N$ 個の正整数が並んでいる魔方陣を $N$ 次魔方陣と呼ぶことにします。
$3$ 次魔方陣は次のようなものが考えられます。縦横に並ぶ数の合計はどこも $15$ となっていますね。

$\begin{bmatrix} 8 & 1 & 6 \\ 3 & 5 & 7 \\ 4 & 9 & 2 \end{bmatrix}$

ところで、 $3$ 次以上の魔方陣は存在することが証明されています。では、魔方陣の積バージョンは存在するでしょうか？

積魔方陣を定義する

$N$ 次の積魔方陣を次のように定義します。

$N$ 次積魔方陣は、縦横にそれぞれ $N$ 個の正整数が並ぶ方陣である
どの2つの数も異なる
各行・各列の積がそれぞれ等しい

これらの条件をすべて満たす積魔方陣を構成してみましょう。

和魔方陣から積魔方陣を構成する

最初に説明した魔方陣を「和魔方陣」と呼ぶことにします。
実は、 $N$ 次の和魔方陣が一つ求まっていれば、そこから $N$ 次の積魔方陣を構成することができます。とりあえず構成アルゴリズムを示します。

元となる和魔方陣の各要素を $a$ としたとき、各要素を $a\to 2^a$ と置き換える

$3$ 次積魔方陣の構成方法を具体的に示すとこうです。

$\begin{bmatrix} 8 & 1 & 6 \\ 3 & 5 & 7 \\ 4 & 9 & 2 \end{bmatrix} \to \begin{bmatrix} 2^8 & 2^1 & 2^6 \\ 2^3 & 2^5 & 2^7 \\ 2^4 & 2^9 & 2^2 \end{bmatrix} = \begin{bmatrix} 256 & 2 & 64 \\ 8 & 32 & 128 \\ 16 & 512 & 4 \end{bmatrix}$

なぜこの方法で積魔方陣が構成できるかは一目瞭然ですね。 $2$ のべき乗の掛け算は、指数部分の足し算として計算できるからです。

以上より、この方法を使えば「 $3$ 次以上の積魔方陣は存在し、実際に和魔方陣から積魔方陣を構成できる」ということが証明できました！「積の魔方陣は構成できるか？」というタイトルは回収したので、これ以降は数学が好きな人だけ見てください。

サイズの小さい積魔方陣を構成したい

先ほどの方法ならいくらでも積の魔方陣を生成できます。しかし $2$ のべき乗しか使えないので、積魔方陣の次数が増えていくほど使われる整数もどんどん大きくなっていきます。もっと"サイズの小さい"積の魔方陣はないか、考えてみましょう。

ここで、魔方陣の大きさを比較するために「積の魔方陣のサイズ」をある一列の数の総積で定義します。たとえば、先ほどの方法で生成した $3$ 次の積魔方陣のサイズは $32768$ となります。このサイズがより小さくなるような積魔方陣を構成したいです。すぐに思いつくのは、すべての要素を $2$ で割る方法です。

$\begin{bmatrix} 256 & 2 & 64 \\ 8 & 32 & 128 \\ 16 & 512 & 4 \end{bmatrix} \to \begin{bmatrix} 128 & 1 & 32 \\ 4 & 16 & 64 \\ 8 & 256 & 2 \end{bmatrix}$

この場合サイズは $4096$ となりますが、まだまだ小さくなりそうです。もっと別のアプローチで積魔方陣を構成できないでしょうか？

素因数が2つ存在する積魔方陣

積魔方陣は整数の掛け算に関する問題なので、各要素を素因数分解して考えるとよさそうです。先ほどまでの方法だと各要素の素因数は $2$ だけでしたが、それ以外の素因数が含まれる場合を考えてみます。

積魔方陣に素因数が2種類含まれる場合、それぞれの素因数は互いに素なので、その素因数ごとに積の魔方陣を分解できます。たとえば、各要素が $2^x\times3^y$ と表せる積の魔方陣が存在すると仮定すると、各要素が $2^x$ である積魔方陣と $3^y$ である積魔方陣に分解して考えることができます。分解した後の積魔方陣は「どの2つの数も異なる」という条件を満たしていなくても構いません（合成した後に条件を満たしていれば十分）。条件が緩いので、分解してできる二つの積魔方陣のことは「準積魔方陣」と呼び分けることにしましょう。

素因数が1種類だけの積魔方陣の生成方法は先ほど説明しました。これを使って、実際に $2^x\times 3^y$ 型の $3$ 次積魔方陣を一つ構成してみましょう。

作成したい積魔方陣には $9$ 種類の相異なる正整数が必要です。 $2^x$ 型の準積魔方陣と $3^y$ 型の準積魔方陣に登場する正整数の種類をそれぞれ $3$ 種類ずつとすると、二つの準積魔方陣をうまく組み合わせることで合成後の積魔方陣に $9$ 種類の相異なる正整数を生成することが可能です。（行列の掛け算と違って、単純に同じ位置にある要素同士を掛け合わせています。）

$\begin{bmatrix} 2^0 & 2^1 & 2^2 \\ 2^1 & 2^2 & 2^0 \\ 2^2 & 2^0 & 2^1 \end{bmatrix} \times \begin{bmatrix} 3^0 & 3^1 & 3^2 \\ 3^2 & 3^0 & 3^1 \\ 3^1 & 3^2 & 3^0 \end{bmatrix} = \begin{bmatrix} 2^0 3^0 & 2^1 3^1 & 2^2 3^3 \\ 2^1 3^2 & 2^2 3^0 & 2^0 3^1 \\ 2^2 3^1 & 2^0 3^2 & 2^1 3^0 \end{bmatrix}$

ちょっと見づらいので、指数部分だけ抜き出して書いてみます。数字の並びがうまくずれているおかげで、合成後の指数の組に重複が無いというところに注目してみてください。

$\begin{bmatrix} 0 & 1 & 2 \\ 1 & 2 & 0 \\ 2 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} 0 & 1 & 2 \\ 2 & 0 & 1 \\ 1 & 2 & 0 \end{bmatrix} = \begin{bmatrix} (0, 0) & (1, 1) & (2, 2) \\ (1, 2) & (2, 0) & (0, 1) \\ (2, 1) & (0, 2) & (1, 0) \end{bmatrix}$

この方法で生成された積魔方陣は以下の通りで、そのサイズは $216$ となります。

$\begin{bmatrix} 1 & 6 & 36 \\ 18 & 4 & 3 \\ 12 & 9 & 2 \end{bmatrix}$

初めに生成したものと比べると、だいぶサイズが小さくなってきました！見た目もシンプルになってきましたね。ただ、 $2$ のべき乗と $3$ のべき乗しか使用していないので、積魔方陣の次数 $N$ が大きくなるとやはり指数的にサイズが大きくなってしまいます。どうやら、もっとサイズを小さくできそうですので、もう少し議論を続けることにしましょう。

ラテン方陣とオイラー 方陣について

先ほどの方法で出てきた「二つの準積魔方陣を"うまく"組み合わせる」というあいまいな部分を少し詳しく見てみましょう。

合成する前の準積魔方陣のうち、指数部分のみを抜き出してできる方陣のような、「 $0$ から $N-1$ までの整数が各列・各行に重複なく並ぶ」方陣のことをラテン方陣といいます。

ラテン方陣の例： $\begin{bmatrix} 0 & 1 & 2 \\ 1 & 2 & 0 \\ 2 & 0 & 1 \end{bmatrix} , \begin{bmatrix} 0 & 1 & 2 & 3 \\ 1 & 2 & 3 & 0 \\ 2 & 3 & 0 & 1 \\ 3 & 0 & 1 & 2 \end{bmatrix}$ など

また、ラテン方陣を二つ合成して、各要素が整数のペアであるような方陣を作ります。このとき、どの $2$ 要素も異なるようなものをオイラー方陣といいます。

オイラー方陣の例： $\begin{bmatrix} (0, 0) & (1, 1) & (2, 2) \\ (1, 2) & (2, 0) & (0, 1) \\ (2, 1) & (0, 2) & (1, 0) \end{bmatrix} , \begin{bmatrix} (0, 0) & (1, 1) & (2, 2) & (3, 3) \\ (1, 2) & (0, 3) & (3, 0) & (2, 1) \\ (2, 3) & (3, 2) & (0, 1) & (1, 0) \\ (3, 1) & (2, 0) & (1, 3) & (0, 2) \end{bmatrix}$ など

ここで、先ほどまでの議論より、ある正整数 $N$ に対して $N$ 次のオイラー方陣が存在すれば、サイズの小さい $N$ 次の積魔方陣を構成できると言えます。

話がそれるので証明や具体的な構成方法は省きますが、 $N=2, 6$ の時を除いて $N$ 次のオイラー方陣が存在することがわかっています。つまり、 $2$ 次と $6$ 次以外の積魔方陣は、オイラー方陣を用いる方法で構成することができるのです*1！

各要素が互いに素な集合を探す

ところで、合成する前の二つの準積魔方陣の各要素は、それぞれ $2^x$ 型と $3^y$ 型でした。このように異なる素因数で分解した理由は、二つの準積魔方陣の要素を掛け合わせた結果がすべて異なるように設定したからでしたね。つまり、二つの準積魔方陣に登場するどの2要素を取ってきても、互いに素になるように設定したということが言えます。

ここで、二つの準積魔方陣を $A, B$ と名付け、それぞれの $N$ 次準積魔方陣に登場する要素の集合を $a, b$ とします。集合 $a, b$ の要素数は $N$ に等しくなります。

例を挙げましょう。 $3$ 次の二つの準積魔方陣 $A, B$ を

$A=\begin{bmatrix} 2^0 & 2^1 & 2^2 \\ 2^1 & 2^2 & 2^0 \\ 2^2 & 2^0 & 2^1 \end{bmatrix}$

$B=\begin{bmatrix} 3^0 & 3^1 & 3^2 \\ 3^2 & 3^0 & 3^1 \\ 3^1 & 3^2 & 3^0 \end{bmatrix}$

と定義すると、準積魔方陣の各要素の集合 $a, b$ は以下のようになります。
$a=\{1, 2, 4\}$
$b=\{1, 3, 9\}$

確かに、集合 $a$ の要素と集合 $b$ の要素は互いに素であることがわかります。さらに、準積魔方陣 $A, B$ を合成してできる積魔方陣のサイズは、集合 $a, b$ の要素の総積と等しくなります（いままでの図を見れば理解できるはずです）。つまり、集合 $a, b$ の要素である正整数の値が小さくなればなるほど、完成する積魔方陣のサイズも小さくなるということです。

ここで、二つの集合の要素を眺めてみると、集合 $b$ の要素のうち $9$ が比較的大きいことに気が付きます。集合 $a$ の全要素と互いに素となる正整数のうち、まだ使われていない最小のものは $5$ です。なんと、集合 $b$ の要素を $9\to 5$ と置換しても、積魔方陣が正しく構成でき、サイズを小さくすることが可能です！

$a=\{1, 2, 4\}$
$b=\{1, 3, 5\}$

$A=\begin{bmatrix} 1 & 2 & 4 \\ 2 & 4 & 1 \\ 4 & 1 & 2 \end{bmatrix}$

$B=\begin{bmatrix} 1 & 3 & 5 \\ 5 & 1 & 3 \\ 3 & 5 & 1 \end{bmatrix}$

この方法で生成された積魔方陣は以下の通りとなります。サイズは $120$ で、先ほどの積魔方陣よりさらにサイズが小さくなっていることがわかります！

$\begin{bmatrix} 1 & 6 & 20 \\ 10 & 4 & 3 \\ 12 & 5 & 2 \end{bmatrix}$

ちなみに、この積魔方陣は $3$ 次積魔方陣のなかでサイズが最小です。美しい…

他の次元の積魔方陣も構成してみる

今までの議論のおさらいとして、他の次元の積魔方陣を構成してみます。

1次の積魔方陣

$1$ 次の方陣とはつまり、整数が $1$ 個しか使われていない方陣です。なので当然、各列・各行の積は等しくなります。よって、すべての $1$ 次方陣は積魔方陣であるといえます！
$1$ 次の最小の積魔方陣は以下の通りで、そのサイズは $1$ です。

$\begin{bmatrix} 1 \end{bmatrix}$

2次の積魔方陣

$2$ 次の積魔方陣は存在しません。証明を記します。

【証明】
$\begin{bmatrix} a & b \\ c & d \end{bmatrix}$
と表せる $2$ 次の積魔方陣が存在すると仮定します。積魔方陣の定義より、以下の等式が成り立ちます。

$a\times b=a\times c$

$a\neq 0$ より両辺を $a$ で割って、 $b=c$ が得られます。しかしこれは、積魔方陣の定義である「どの2つの数も異なる」に矛盾します。よって仮定が誤りで、 $2$ 次の積魔方陣は存在しません。

4次の積魔方陣

オイラー方陣を用いて構成してみます。準積魔方陣 $A, B$ を構成する要素の集合 $a, b$ の値をどう決めるかが重要です。とりあえず、集合 $a$ に $2$ のべき乗を、集合 $b$ に $3$ のべき乗をそれぞれ入れてみましょう。集合 $a, b$ の要素数は $4$ なので、小さい順に並べます。

$a=\{1, 2, 4, 8\}$
$b=\{1, 3, 9, 27\}$

明らかに集合 $b$ の値が大きいですね。集合 $a$ には素因数 $2$ が含まれているので、集合 $b$ には $2$ の倍数を含むことができません。 $2$ の倍数でない正整数、つまり奇数は必ず集合 $a$ の全ての要素と互いに素になります。よって、集合 $a, b$ は最終的に次のようになります。

$a=\{1, 2, 4, 8\}$
$b=\{1, 3, 5, 7\}$

これらの集合の各要素を $4$ 次のオイラー方陣に適用させると、 $4$ 次の積魔方陣が完成します。

$\begin{bmatrix} (0, 0) & (1, 1) & (2, 2) & (3, 3) \\ (1, 2) & (0, 3) & (3, 0) & (2, 1) \\ (2, 3) & (3, 2) & (0, 1) & (1, 0) \\ (3, 1) & (2, 0) & (1, 3) & (0, 2) \end{bmatrix} \to \begin{bmatrix} 1 & 6 & 20 & 56 \\ 10 & 7 & 8 & 12 \\ 28 & 40 & 3 & 2 \\ 24 & 4 & 14 & 5 \end{bmatrix}$

この積魔方陣のサイズは $6720$ です。この積魔方陣が $4$ 次の積魔方陣の中で最小のサイズである証明はできませんでしたが、おそらく最小と思われます。

5次の積魔方陣

先ほどと同様にして、 $5$ 次の積魔方陣を構成してみます。集合 $a$ の要素は $2$ のべき乗、集合 $b$ の要素は奇数、と仮定すると以下のようになります。

$a=\{1, 2, 4, 8, 16\}$
$b=\{1, 3, 5, 7, 9\}$

よくみると、今度は集合 $a$ の要素のうち $16$ が大きく見えます。ここで、「素数は自分自身の倍数を除いてどんな整数とも必ず互いに素となる」という性質を使うと、 $16\to 11$ と置き換えることができますね。よって、最終的な集合 $a, b$ は次のようになります。

$a=\{1, 2, 4, 8, 11\}$
$b=\{1, 3, 5, 7, 9\}$

これらの集合をもとに積魔方陣を構成すると、以下のようになります。

$\begin{bmatrix} (0,0) & (1,1) & (2,2) & (3,3) & (4,4) \\ (3,2) & (4,3) & (0,4) & (1,0) & (2,1) \\ (1,4) & (2,0) & (3,1) & (4,2) & (0,3) \\ (4,1) & (0,2) & (1,3) & (2,4) & (3,0) \\ (2,3) & (3,4) & (4,0) & (0,1) & (1,2) \end{bmatrix} \to \begin{bmatrix} 1 & 6 & 20 & 56 & 99 \\ 40 & 77 & 9 & 2 & 12 \\ 18 & 4 & 24 & 55 & 7 \\ 33 & 5 & 14 & 36 & 8 \\ 28 & 72 & 11 & 3 & 10 \end{bmatrix}$

この積魔方陣のサイズは $665280$ となります。 $5$ 次の積魔方陣が $2$ 桁以下の整数だけで構成されている美しい姿には、もはや感動すら覚えます。素晴らしい…

6次の積魔方陣

先ほど、 $6$ 次のオイラー方陣は存在しないことを書きました。しかし、 $6$ 次の和魔方陣は存在するので、 $6$ 次の積魔方陣も存在するということになります。実際に構成したものを書いてみると以下のようになります。

$\begin{bmatrix} 1 & 2 & 4 & 8589934592 & 17179869184 & 34359738368 \\ 1073741824 & 2147483648 & 16384 & 8 & 4194304 & 32 \\ 536870912 & 268435456 & 134217728 & 256 & 128 & 64 \\ 2048 & 1024 & 512 & 67108864 & 33554432 & 16777216 \\ 8388608 & 524288 & 2097152 & 1048576 & 16 & 262144 \\ 4096 & 65536 & 4294967296 & 32768 & 8192 & 131072 \end{bmatrix}$

いやいや、デカすぎますね！！一番大きい要素は $2^{35}$ で、なんと $11$ 桁もあります。でもこれが $6$ 次の最小サイズの積魔方陣とは考えにくいですよね。もっとサイズが小さくなるような数の組み合わせはあるのでしょうか…。

さらに高次の積魔方陣の構成について

$7$ 次以上の積魔方陣は、オイラー方陣を用いて構成することが可能です。よりサイズの小さな積魔方陣を構成するためには、集合 $a, b$ の要素の選び方が重要になってくることがわかると思います。しかし、最適な数字の選び方はまだわかっていません。素数が絡む問題は、いつも難しくなりがちです。

結論

積の魔方陣は、 $2$ 次のものを除いて存在します。今回は、

和魔方陣から構成する方法
オイラー方陣から構成する方法

の2種類を紹介しました。前者の方法はかなり有名ですが、後者の方法はあまり知られていないと思います。積の魔方陣を作って友達に自慢しましょう！

課題

この中では議論できなかった課題を並べておきます。「これ解けたよ！」ってのがあったら教えてください。

$6$ 次の最小サイズの積魔方陣は求められるでしょうか？
集合 $a, b$ の適切な要素の選び方はあるでしょうか？　もし素数のリストが与えられている場合に、効率よく構成することはできないでしょうか？
さらっと条件から外していましたが、今回の議論では方陣の各対角線の積は考慮しませんでした。各対角線の積も等しくするためには、今回紹介したオイラー方陣を用いる構成方法は使えません。どんな方法が考えられるでしょうか？
今回は数学の問題として手作業で構成することを想定していましたが、もし $N$ 次の最小の積魔方陣を構成するプログラムを組むとしたらどんなアルゴリズムが考えられるでしょうか？　そのアルゴリズムの計算量はどうなるでしょうか？

以上です。ここまでで約10000文字らしいです！400字詰めのレポートが25枚書けます。高専生の皆さんは、ちゃんとレポートを書きましょうね！！！

苫小牧高専アドベントカレンダー、明日はあやさんの担当です。それでは！