前回の記事 で オリジナルのPool-Ball Trianglesのルールを少し変更したパズル? を紹介しました.

前と同じように, このパズルをGPT(Generic-like Pool-Ball Triangles)と書くことにします.

今回は それについて分かったことがあるので, その紹介です.

  • 10段以下の場合のGPTを計算した話
  • $(n, \frac{n(n+1)}{2})$型のGPTの$(1, 1)$成分(一番左上の成分)が0である証明
  • $(3, 6), (4, 10)$型のGPT について 対角成分の値が一定であることの説明

以下, $(n, \frac{n(n+1)}{2})$型のGPTを$n$型のLPTと呼ぶことにします.

10段以下の場合のGPTを計算した話

10段以下の場合のGPTを計算できました.

データ構造を横一列の列のリストではなく, 対角線ごとのリストにして, パズルを再帰的に計算するようにしました. これを見ると $n \ge 5$の時は LPTが存在しません. この方が早くなるっていうのは, 直感的にはそりゃそうです.

例えば, List(Vector(0), Vector(1, 5), Vector(4, 3, 2))という要素は

\[\begin{array}{c} 0\ 1\ 4 \\ 5\ 3\ \\ 2\ \end{array}\]

という要素を表します.

ソースコードの結果は こちら です. このソースコードの実行には 自分の環境では13時間ほどかかりました.

$(n, \frac{n(n+1)}{2})$型のGPTの$(1, 1)$成分(一番左上の成分)が0である証明

$n$型のLPT Aの$(1, 1)$成分が0でないと仮定します. Aの要素としては$0$から$n(n+1)/2 - 1$までの全ての値が使われるので, 値が0であるような場所が存在します. その場所に対して場合分けをして, それぞれに関して矛盾を示すことを考えます.

  • 対角線の一番最後の値でないとき
  • 対角線の一番最後の値であるとき

0がある対角線の一番最後の値でないとき:

0の左にはある値 $a$があり, $0$と$a$の間の数字は$a - 0 = a$となる. よって同じ数字$a$が二回出てくることになるので, これは矛盾である.

\[\begin{array}{c} a\ 0 \\ a \end{array}\]
  • 対角線の一番最後の値であるとき

この時, $0$の上の二つの値は同じ値$a$であるから, これも同じ値$a$が二回出てくることになるので, 同じ数字$a$が2回出てくることになり 矛盾します.

\[\begin{array}{c} a\ a \\ 0 \end{array}\]

以上によって, Aの$(1, 1)$成分は0です.

$(3, 6), (4, 10)$型のLPT について 対角成分の値が一定であることの説明

3 段のLPTは以下の4つです.

\[\begin{align*} \begin{array}{c} 0\ 1\ 4 \\ 5\ 3\ \\ 2\ \end{array}, \quad \begin{array}{c} 0\ 4\ 1 \\ 2\ 3\ \\ 5\ \end{array}, \quad \begin{array}{c} 0\ 2\ 5 \\ 4\ 3\ \\ 1\ \end{array}, \quad \begin{array}{c} 0\ 5\ 2 \\ 1\ 3\ \\ 4\ \end{array} \end{align*}\]

また, 4段のLPTは以下の8つです.

\[\begin{align*} \begin{array}{c} 0\ 4\ 9\ 2 \\ 6\ 5\ 7 \\ 1\ 8 \\ 3 \end{array}, \quad \begin{array}{c} 0\ 4\ 9\ 7 \\ 6\ 5\ 2 \\ 1\ 3 \\ 8 \end{array}, \quad \begin{array}{c} 0\ 8\ 3\ 9 \\ 2\ 5\ 4 \\ 7\ 1 \\ 6 \end{array}, \quad \begin{array}{c} 0\ 2\ 7\ 6 \\ 8\ 5\ 1 \\ 3\ 4 \\ 9 \end{array}, \\ \begin{array}{c} 0\ 2\ 7\ 1 \\ 8\ 5\ 6 \\ 3\ 9 \\ 4 \end{array}, \quad \begin{array}{c} 0\ 6\ 1\ 3 \\ 4\ 5\ 8 \\ 9\ 7 \\ 2 \end{array}, \quad \begin{array}{c} 0\ 8\ 3\ 4 \\ 2\ 5\ 9 \\ 7\ 6 \\ 1 \end{array}, \quad \begin{array}{c} 0\ 6\ 1\ 8 \\ 4\ 5\ 3 \\ 9\ 2 \\ 7 \end{array}. \end{align*}\]

これを見ると 3段のLPTの対角成分の和は0, 6, 9, 4段のLPTの対角成分の和は0, 10, 15, 20と 全て同じになっています.

この理由を考えてみました.

  • 三段の場合

以下のようにパズルの変数を置きます.

\[\begin{array}{c} 0\ a_{11}\ a_{21} \\ a_{12}\ a_{22}\ \\ a_{23}\ \end{array}\]

対角線一列目の和は明らかに0です.

また, $a_{11} + a_{12} \equiv 0 \pmod{6}$です.

最後に

\[\begin{align*} a_{21} + a_{22} \equiv a_{11} \pmod{6}, \\ a_{22} + a_{23} \equiv a_{12} \pmod{6} \end{align*}\]

より

\[\begin{align*} a_{21} + 2a_{22} + a_{23} &\equiv a_{11} + a_{12} \equiv 0 \pmod{6}, \\ a_{21} + a_{22} + a_{23} &\equiv -a_{22} \pmod{6}. \\ \end{align*}\]

ここで, このパズルは$0$から$5$までの数字の入れ替えなので

\[\begin{align*} 0 + (a_{11} + a_{12}) + (a_{21} + a_{22} + a_{23}) &\equiv 0 + 0 - a_{22} \pmod{6} \\ &= -a_{22} \equiv \frac{5 \cdot 6}{2} \equiv 3 \pmod{6} \end{align*}\]

よって $a_{22} \equiv 3 \pmod{6}$が成り立つ.

以上によって 三段の対角成分の和は

\[a_{21} + a_{22} + a_{23} \equiv -3 \equiv 3 \pmod{6}\]

を満たす.

  • 四段の場合

三段の場合とほぼ同様です.

以下のようにパズルの変数を置きます.

\[\begin{array}{c} 0\ a_{11}\ a_{21}\ a_{31} \\ a_{12}\ a_{22}\ a_{32} \\ a_{23}\ a_{33} \\ a_{34} \end{array}\]

対角線一列目の和は明らかに0です.

また, $a_{11} + a_{12} \equiv 0 \pmod{10}$です.

また,

\[\begin{align*} a_{21} + a_{22} \equiv a_{11} \pmod{10}, \\ a_{22} + a_{23} \equiv a_{12} \pmod{10} \end{align*}\]

より

\[\begin{align*} a_{21} + 2a_{22} + a_{23} &\equiv a_{11} + a_{12} \equiv 0 \pmod{10} \\ a_{21} + a_{22} + a_{23} &\equiv -a_{22} \pmod{10} \end{align*}\]

が成り立つ.

さらに

\[\begin{align*} a_{31} + a_{32} &\equiv a_{21} \pmod{10}, \\ a_{32} + a_{33} &\equiv a_{22} \pmod{10}, \\ a_{33} + a_{34} &\equiv a_{23} \pmod{10} \end{align*}\]

より

\[\begin{align*} a_{31} + 2(a_{32} + a_{33}) + a_{34} &\equiv a_{21} + a_{22} + a_{23} \equiv -a_{22} \pmod{10} \\ a_{31} + a_{32} + a_{33} + a_{34} &\equiv -a_{22} - (a_{32} + a_{33}) \\ &\equiv -2a_{22} \pmod{10} \end{align*}\]

また, このパズルは$0$から$9$までの数字の入れ替えなので

\[\begin{align*} 0 + (a_{11} + a_{12}) + (a_{21} + a_{22} + a_{23}) + (a_{31} + a_{32} + a_{33} + a_{34}) &\equiv 0 + (-a_{22}) + (-2a_{22}) \\ &= -3a_{22} \equiv \frac{9 \cdot 10}{2} \equiv 5 \pmod{10} \\ 3a_{22} &\equiv 5 \pmod{10} \\ a_{22} &\equiv 5 \cdot 7 \equiv 5 \pmod{10}. \end{align*}\]

よって, 三段目は

\[a_{21} + a_{22} + a_{23} \equiv 5 \pmod{10}.\]

また 四段目は

\[a_{31} + a_{32} + a_{33} + a_{34} = -2 \cdot 5 \equiv 0 \pmod{10}\]

が成り立ちます. ☐

ちなみに $n=5$の場合は対角線の和を考える前に 二つの変数が残ってしまって この方法ではうまくいきません.