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

皆さん、こんにちは。引き続き、テトリスを数学で分析してみよう、という話題をお送りします。

前回の復習

前回の記事では、「幅 2 の長方形をテトリミノで敷き詰める」ことを題材に、縦パリティについて扱いました。

その中で、マスを 2 色に塗り分ける代わりに、0 と 1 の数字を割り振る方法を紹介しましたね。

各色の個数をそれぞれ考えるやり方では、塗り分けに使う色の数が増えると計算が大変になります。そこで、マスに色ではなく数字を割り振ると分析が楽になるよ、というお話でした。

今回の記事でやること

引き続き「幅 2 の長方形の敷き詰め」を題材として、前回 2 色の塗り分けで行った方法を 4 色にも適用してみます。

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

この問題の解き方はいくつかあります。ここでは、フィールドを次の図のように塗り分ける方法をご紹介しましょう。

フィールドにあるマスを「空色・緑・黄色・赤」の 4 色に分類しています。それぞれの色に注目すると、同じ色のマスが左上から右下へ、斜めに連なっていることが分かりますね。

この塗り方は「四色パリティ」の一種です。

色の代わりに整数を割り当てると

4 色それぞれのマスの数を考察することもできますが、楽をしましょう。

各マスに対し、図のように整数を割り当てます。

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

先ほどの色分けと同様、同じ数字のマスが左上から右下へと、斜めに並ぶようになっています。「空色・緑・黄色・赤」がそれぞれ「0, 1, 2, 3」に変わっただけですね。

ちょっと観察すると、4 × 4 マスのパターンが縦横に繰り返されていることが分かります。

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

さて、数字の割り当て方を式で表してみましょう。

まず、フィールドの最も左下にあるマスの座標を $${(0, 0)}$$ とし、$${x}$$ 軸を右向き、$${y}$$ 軸を上向きに取ります。ここまでは前回と同様です。そして今回は、座標 $${(x, y)}$$ のマスに対して $${(x+y) \bmod 4}$$ を割り当てています。

なお、前回と違うところがもう一点あります。前回の縦パリティでは、各テトリミノが覆う領域や敷き詰める領域全体について、マスに割り当てた数字の合計を求め、その合計値を mod 2 していました。しかし今回は、合計値の mod 2 ではなく、mod 4 を考えます。

問題を解いてみる

お待たせしました。いよいよ問題を解いていきます。2 × 2n の長方形をテトリミノで敷き詰めると、I ミノと J ミノの個数の偶奇が一致するよ、という話でしたね。

S, Z, T ミノや、横向きの I, J, L ミノは使えないので、これらを除いて考えましょう。

各テトリミノが埋める領域と、2 × 2n の長方形全体について、マスに割り当てた整数の合計を mod 4 した値を求めます。

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

各テトリミノは、平行移動しても値が変わりません。当然この長方形についても、平行移動で値は変わりません。

気になる方は、ご自身でこれらの値を確認してみてください。

さて、I（縦）、J（縦）、L（縦）、O の各ミノの個数を $${\mathcal{I}^v, \mathcal{J}^v, \mathcal{L}^v, \mathcal{O}}$$ で表すことにしましょう。右上に付いているのは、“vertical” の “v” です。

このとき、次の式が成り立ちます。

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

簡潔に書くと $${2\mathcal{I}^v + 2\mathcal{J}^v \equiv 0 \enspace(\bmod 4)}$$ となります。これは $${\mathcal{I}^v + \mathcal{J}^v \equiv 0 \enspace(\bmod 2)}$$ と同じことです。よって、$${\mathcal{I}^v \equiv \mathcal{J}^v \enspace(\bmod 2)}$$ であることが分かります。

ここでは横向きの I, J ミノは使わないため、以上で「2 × 2n の長方形をテトリミノで敷き詰めるとき、I ミノと J ミノの個数は偶奇が一致する」ということが示せました。

【おまけ】その他のミノではどうなる？

今回の色分けの方法は、見慣れない方が多いと思います。そこで、先ほど使わなかったテトリミノも含めて、同様に値を求めてみました。

ミノの向きの表示方法

テトリミノを回転すると値が変わる場合があるので、向きの表し方を決めておきましょう。

私の周囲では、うめぼしさんという方が定めた記法（リンク）が使われているので、当記事でもそれに従います。概略は次の通りです。

• スポーン時の向きから何回右回転するかを、0 から 3 の整数で表す

• 0, 2 はまとめて h と書ける（horizontal の h）

• 1, 3 はまとめて v と書ける（vertical の v）

• 向きを問わない場合は表記しなくてよい

各ミノの値

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

座標 $${(x, y)}$$ のマスに $${(x+y) \bmod 4}$$ を割り当て、各ミノが覆う領域の総和を mod 4 すると、次のようになります。

$$
\def\arraystretch{1.4}
\begin{array}{c|c}
& \text{合計 mod 4} \\
\hline
\text{J}^\text{h}, \text{L}^\text{v}, \text{O} & 0 \\
\text{T}^0, \text{T}^1 & 1 \\
\text{I}, \text{J}^\text{v}, \text{L}^\text{h}, \text{S}, \text{Z} & 2 \\
\text{T}^2, \text{T}^3 & 3 \\
\end{array}
$$

各テトリミノは、やはり平行移動しても値が変わりません。

なぜ平行移動しても値が変わらないのか、意欲のある方は考えてみると面白いかもしれません。
（今後の記事でこの点に触れるので、各々で考察していただかなくても問題なく読み進められます。）

次回予告

様々なパリティの彩色方法とベクトルの内積を結びつけるにあたり、次回はその準備をします。というわけで、恐らくまだ内積は登場しません。

今回登場した $${(x+y) \bmod 4}$$ を具体例として、もう少し四色パリティに慣れていただこうと思います。