【テトリス】パリティの彩色とベクトルの内積①

皆さん、こんにちは。初めましての方は初めまして。Ogonek:Macron と申します。🥖というハンドルネームで私のことを認知している方もいらっしゃると思います。

普段はパズルゲームのテトリスに関する計算や数学的考察を X（旧 Twitter）に投稿していますが、情報のアクセス性を高めるため note に登録してみました。

今回は投稿テストがてら、パリティの理論を拡張して、領域の敷き詰め方について考察する方法の一例をご紹介します。

目標

テトリスの分析に用いられるパリティの理論では、フィールドにあるマスを 2 色に塗り分け、それぞれの色のマスの個数について調べる方法がよく知られています。ここで、塗り分けに使う色を増やしたら、例えば 4 色にしたらどうなるだろう？ というのはごく自然な疑問です。

しかし、多くの色について同時に考えるのは少々大変です。

これから複数の記事に分けて、マスを色分けする代わりに整数を割り当てることで、考察を簡略化する方法をご紹介します。さらに、この方法がベクトルの内積の考え方と関連することを示します。

今回の記事でやること

いきなり一般論を述べるのではなく、具体例を通してパリティの考え方に触れてもらいます。

題材は「幅 2 マスの長方形をテトリミノで敷き詰める方法」です。なぜこの題材かと言うと、説明が楽だからです。

この記事では、2 色を使うパリティのうち、縦パリティについてまず一般的な考察の方法を復習します。続いて、マスに色ではなく整数を割り当てる方法を紹介します。

4 色への拡張は次回以降に行います。

さて、本題に入る前に、パリティを使わずに分かる前提条件を確認しておきましょう。

前提条件 1: 長方形の高さは偶数

テトリミノ 1 つあたりの面積は 4 ですから、長方形の面積は 4 の倍数でなければなりません。

幅が 2 マスなので、高さは偶数である必要があります。

前提条件 2: 使えないミノの確認

S, Z, T ミノは使えない

S, Z, T ミノは、横向きに置こうとすると幅 3 マスを占領するため、幅 2 マスの長方形からはみ出してしまいます。

また、縦向きに置いた場合、長方形を奇数マスの領域に分割することになります。すると、残りの領域をテトリミノで敷き詰めることが不可能になります。

よって、S, Z, T ミノを使用することは出来ません。

I, J, L ミノは横向きに出来ない

I, J, L ミノは、横向きに置こうとすると幅 3 マスないし 4 マスを占領するため、幅 2 マスの長方形からはみ出してしまいます。

よって、I, J, L ミノは横向きで使うことはできません。今後は縦向きの場合のみについて考慮すれば良いことになります。

【縦パリティ】J, L ミノの個数の偶奇を考察しよう

問. n を自然数とする。幅 2 マス、高さ 2n マスの長方形をテトリミノで敷き詰めるとき、J ミノと L ミノの個数は偶奇が一致することを示せ。

この問題は、縦パリティを使って解くことが出来ます。

縦パリティの塗り分け

通常の解き方では、フィールドを画像のように 2 色に塗り分けることで、それぞれの色が何マスあるかを考えることになります。

普通の解き方

証明の流れは以下の通りです。

• I, O ミノは各色を偶数マスずつ埋める

• J, L ミノは各色を奇数マスずつ埋める

• この長方形全体では各色が偶数マスずつある

• このため、J, L ミノは合わせて偶数個必要である

• よって、J ミノと L ミノの個数は偶奇が一致する

2 色の塗り分けならこの方法で良いのですが、使う色が増えてくると大変です。4 色に塗り分ける場合、4 つの値について同時に考えることになってしまいます。

一般に、この方法では k 種類の色を使うと k 個の値について同時に考える、つまり k 次元の値を考えることになります。これを 1 次元の値に簡略化できると嬉しいですね。

色分けの考え方を簡略化する

ここで発想の転換をしましょう。各マスに整数を割り当て、考えたい領域についてその総和を求めることにします。なお、割り当てる数字は、座標を元に決めるようにします。

例えば縦パリティなら、2 色で塗り分ける代わりに、図のように 0 と 1 を割り当てます。

$$
\def\arraystretch{1.2}
\begin{array}{|c|c|c|c|c}
\vdots & \vdots & \vdots & \vdots &  \\
\hline
0 & 1 & 0 & 1 & \cdots \\
\hline
0 & 1 & 0 & 1 & \cdots \\
\hline
0 & 1 & 0 & 1 & \cdots \\
\hline
0 & 1 & 0 & 1 & \cdots \\
\hline
\end{array}
$$

フィールドの最も左下にあるマスの座標を $${(0, 0)}$$ とし、$${x}$$ 軸を右向き、$${y}$$ 軸を上向きに取り、座標 $${(x, y)}$$ のマスに対して $${x \bmod 2}$$ を割り当てています。

もう一度同じ問題を解いてみる

先程の問題をこの考え方で解いてみましょう。

各テトリミノが埋める領域と、2 × 2n の長方形全体について、マスに割り当てた整数の合計を mod 2 した値を考えます。
（先程は各色の個数の偶奇を考えていたので、それに対応するよう、領域内の合計値に mod 2 を適用します。）

$$
\def\arraystretch{1.4}
\begin{array}{c|c}
& \text{合計 mod 2} \\
\hline
\text{I} & 0 \\
\text{J} & 1 \\
\text{L} & 1 \\
\text{O} & 0 \\
\hline
\text{全体} & 0
\end{array}
$$

さて、I, J, L, O ミノの個数をそれぞれ $${\mathcal{I}, \mathcal{J}, \mathcal{L}, \mathcal{O}}$$ で表すことにしましょう。個数の話をしていることがパッと見て分かるよう、筆記体にしておきます。

このとき、次の式が成り立つことが分かります。

$$
\begin{array}{} \mathcal{I}×0 + \mathcal{J}×1 + \mathcal{L}×1 + \mathcal{O}×0 \equiv 0 \quad (\bmod 2) \end{array}
$$

冗長なので簡潔に書くと、$${\mathcal{J} + \mathcal{L} \equiv 0 \enspace(\bmod 2)}$$ となります。よって、$${\mathcal{J} \equiv \mathcal{L} \enspace(\bmod 2)}$$ ということも分かります。

このようにして、塗り分けた 2 色それぞれの偶奇について考える場合と同じく、「J ミノと L ミノの個数は偶奇が一致する」ということが示せました。

片方の色を考えているだけだが……

皆さんはお気付きかもしれませんが、これは 2 色あるマスのうち、片方のみの色についてマス数の偶奇を考えていることに他なりません。テトリミノの単純な敷き詰め問題ではマスの数（= 2 色の合計）が常に偶数という制約があるため、片方の色だけ偶奇を考えれば十分なのです。

補足
ただし、「マスに 0 と 1 の数字を割り当て、領域内の合計値の mod 2 を求める」という見方はとても重要です。
この捉え方をしておくと、色の数を 4 色に増やす際に、「マスに 0, 1, 2, 3 を割り当て、領域内の合計値の mod 4 を求める」と考えることができるようになります。単に特定の色のみに注目しているというわけではないのです。

奇数ブロックのときは注意が必要

ただし、対戦テトリスではブロック数が奇数になる場合があります。ブロック数が奇数の場合、各マスに 0 と 1 を割り当てる方法では、2 色それぞれの偶奇を考える方法に比べて得られる情報の解像度が落ちてしまいます。

このため、ブロック数が奇数になりうる場面を考察したいときは、注意が必要です。

次回予告

今回の記事で 2 色の代わりに 2 つの整数を割り当てた方法を、次回は 4 色に拡張します。

今回と同じ「幅 2 の長方形」という題材で、今度は I, J, L ミノの個数に関する考察をしていきます。

次: 【テトリス】パリティの彩色とベクトルの内積②

参考文献

今回紹介した内容に関する、体系的な解説を含むドキュメントがあるので、ご紹介します。

Four-colour Parity Theory

X や Discord で私と交流がある LLY さんをはじめ、有志の皆さんが製作してくださいました。

英語の分かる方は是非お読みになってみてください。