\(n\) を \(2\) 以上の整数とする. 正方形の形に並んだ \(n \times n\) のマスに \(0\) または \(1\) のいずれかの数字を入れる. マスは上から第 \(1\) 行, 第 \(2\) 行, … , 左から第 \(1\) 列, 第 \(2\) 列, … , と数える. 数字の入れ方についての次の条件 \(p\) を考える.
- 条件 \(p\) ： \(1\) から \(n-1\) までのどの整数 \(i , j\) についても, 第 \(i\) 行, 第 \(i+1\) 行と第 \(j\) 列, 第 \(j+1\) 列とが作る \(2 \times 2\) の \(4\) マスには \(0\) と \(1\) が \(2\) つずつ入る.
(1) 条件 \(p\) を満たすとき, 第 \(n\) 行と第 \(n\) 列の少なくとも一方には \(0\) と \(1\) が交互に現れることを示せ.
(2) 条件 \(p\) を満たすような数字の入れ方の総数 \(a _ n\) を求めよ.
【 解 答 】
条件 \(p\) をみたす数字の入れ方について, \(2 \times 2\) の \(4\) マスのうち
- [1] ： \(3\) マスの数字が決まっていれば（すべて同じ数字の場合は除く）, 残り \(1\) マスに入る数字は, 一意に決まる.
- [2] ： 隣り合う \(2\) マスに同じ数字が入っていれば, 残り \(2\) マスに入る数字は, これと異なる数字に一意に決まる.
また, 第 \(n\) 行（列）に \(0 , 1\) が交互に現れていることを, 「第 \(n\) 行（列）が交互である」とよぶこととする.
(1)
背理法を用いて示す.
第 \(n\) 行 , 第 \(n\) 列ともに 交互でない, と仮定する.
- [3] ： 第 \(n\) 列の第 \(i\) 行, 第 \(i+1\) 行が同じ数字であれば, 第 \(i\) 行と第 \(i+1\) 行はともに交互である.
- [4] ： 第 \(n\) 行の第 \(j\) 列, 第 \(j+1\) 列が同じ数字であれば, 第 \(j\) 列と第 \(j+1\) 列はともに交互である.
しかし, 第 \(i\) 行, 第 \(i+1\) 行と, 第 \(j\) 列, 第 \(j+1\) 列が交差する \(2 \times 2\) の \(4\) マスに着目すれば, [3] と [4] が同時に成立することはないので, 矛盾する.
よって, 題意は示された.
(2)
\(n \times n\) のマスのうち, 第 \(n\) 行と第 \(n\) 列がともに交互であるものを両交互, 一方のみが交互であるものを片交互とよぶこととする.
\(n \times n\) のマスのうち, 両交互である個数を \(b _ n\) , 片交互である個数を \(c _ n\) とおくと
\[
b _ 2 = 2 , \ c _ 2 = 4 \quad ... [5] \ .
\]
第 \(n\) 行の隣りに第 \(n+1\) 行を追加するとき, [1] [2] に注意すれば
- [6] ： 第 \(n\) 行が交互であれば, 第 \(n+1\) 行の数字の入れ方は \(2\) 通り（第 \(n\) 行と同じ数字かと異なる数字を入れる）あり, どちらも交互である.
- [7] ： 第 \(n\) 行が交互でなければ, 第 \(n+1\) 行の数字の入れ方は \(1\) 通りのみ（第 \(n\) 行と異なる数字を入れる）で, 交互ではない.
（ [6] [7] は「行」を「列」に言い換えても同様に成り立つ. ）
\(n \times n\) のマスに, 第 \(n+1\) 行と第 \(n+1\) 列を加えて, \((n+1) \times (n+1)\) のマスを作ることを考える.
このとき
1* \(n \times n\) のマスが片交互のとき（第 \(n\) 行が交互とする）
第 \(n+1\) 列の第 \(1, 2, \cdots , n\) 行の数字の入れ方は, [7] より \(1\) 通りのみ.
その後, 第 \(n+1\) 行の第 \(1, 2, \cdots , n+1\) 列の数字の入れ方は, [6] より \(2\) 通り.
したがって, \((n+1) \times (n+1)\) のマスは \(2\) 通りあり, いずれも片交互である.2* \(n \times n\) のマスが両交互のとき
第 \(n+1\) 行（列）の第 \(1, 2, \cdots , n\) 列（行）の数字の入れ方は, [6] よりそれぞれ \(2\) 通りずつ.
最後に, 第 \(n+1\) 行の第 \(n+1\) 列が [1] によって決まり, 第 \(n+1\) 行（列）を第 \(n\) 行（列）と同じ数字あるいは異なる数字にするかに応じて, \((n+1) \times (n+1)\) のマスは, 下表のように \(3\) 通りあり, \(1\) つは両交互, \(2\) つは片交互である.
\[ \begin{array}{c|c|c} \text{行＼列} & \text{同じ数字} & \text{異なる数字} \\ \hline \text{同じ数字} & \text{両交互} & \text{片交互} \\ \hline \text{異なる数字} & \text{片交互} & \text{×} \end{array} \] （ここで, ともに同じ数字を入れた場合は, 条件 \(p\) に反する点に注意する. ）
以上より \[ \left\{ \begin{array}{ll} b _ {n+1} = b _ n & ... [8] \\ c _ {n+1} = 2 c _ n +2 b _ n & ... [9] \end{array} \right. \ . \] [5] [8] より \[ b _ n = 2 \ . \] [9] に代入すれば \[\begin{align} c _ {n+1} & = 2 c _ n +4 \\ \text{∴} \quad c _ {n+1} +4 & = 2 ( c _ n +4 ) \ . \end{align}\] したがって, [5] も用いて \[\begin{align} c _ n +4 & = (4+4) \cdot 2^{n-2} = 2^{n+1} \\ \text{∴} & \quad c _ n = 2^{n+1} -4 \ . \end{align}\] よって \[ a _ n = b _ n +c _ n = \underline{2^{n+1} -2} \ . \]