大阪大学 2015年度
理系数学 第5問

解答

(1)

各マスに入っている数を $a_{ij}$ と書く。ただし $a_{ij}$ は第 $i$ 行第 $j$ 列の数であり、$0$ または $1$ である。

隣り合う2行、第 $i$ 行と第 $i+1$ 行を固定する。第 $j$ 列にあるこの2つの数の和を $u_j=a_{ij}+a_{i+1,j}$ とおく。$u_j$ は $0,1,2$ のいずれかである。

条件 $p$ より、第 $i$ 行・第 $i+1$ 行と第 $j$ 列・第 $j+1$ 列で作る $2\times 2$ の4マスには、$1$ がちょうど2つ入る。したがって $u_j+u_{j+1}=2$ である。これがすべての $j=1,2,\dots ,n-1$ で成り立つ。

この関係から、$u_j$ の並びは次のどちらかである。

まず、ある $j$ で $u_j=1$ なら、$u_{j+1}=1$ であり、順にすべての $u_j$ が $1$ になる。この場合、第 $i$ 行と第 $i+1$ 行は各列で互いに反対の数をもつ。

一方、ある $j$ で $u_j=0$ または $2$ なら、関係式から $u_j$ は $0,2,0,2,\dots$ または $2,0,2,0,\dots$ と交互に並ぶ。この場合、各列で上下の2数は等しく、しかも列を移るごとに $0,1$ が交互に現れる。つまり第 $i$ 行と第 $i+1$ 行は、どちらも同じ交互行である。

したがって、任意の隣接2行について、次のどちらかが成り立つ。 $\text{(A) 2行は列ごとに互いに反対である}$ または $\text{(B) 2行はどちらも同じ交互行である。}$ もし、ある隣接2行について (B) が成り立つなら、そのうち一方の行は交互行である。その隣の行は、(A) なら交互行の反対なのでやはり交互行、(B) なら同じ交互行である。これを上下に繰り返すと、すべての行に $0$ と $1$ が交互に現れる。したがって特に第 $n$ 行に $0$ と $1$ が交互に現れる。

一方、どの隣接2行についても (B) が起こらず、すべて (A) であるとする。このとき、各列では行を1つ下がるごとに数が反対になる。したがってすべての列に $0$ と $1$ が交互に現れる。特に第 $n$ 列に $0$ と $1$ が交互に現れる。

以上より、条件 $p$ を満たすとき、第 $n$ 行と第 $n$ 列の少なくとも一方には $0$ と $1$ が交互に現れる。

(2)

(1)の議論から、条件 $p$ を満たす入れ方は次の2種類のどちらかである。 $\text{すべての行に }0\text{ と }1\text{ が交互に現れる入れ方}$ または $\text{すべての列に }0\text{ と }1\text{ が交互に現れる入れ方}$ である。逆に、このどちらかを満たす入れ方では、任意の隣接する $2\times 2$ の4マスに $0$ と $1$ が2つずつ入るので、条件 $p$ を満たす。

まず、すべての行が交互である入れ方を数える。各行について、左端の第1列の数を $0$ にするか $1$ にするかを決めれば、その行全体は一意に決まる。したがって $2^n$ 通りである。

同様に、すべての列が交互である入れ方も、各列の第1行の数を決めればその列全体が一意に決まるので $2^n$ 通りである。

ただし、この2つの種類に重複して数えられる入れ方がある。それは、すべての行もすべての列も交互である入れ方である。この場合、第1行第1列の数を決めれば盤面全体が市松模様として一意に決まるので、重複は $2$ 通りである。

よって求める総数は $\boxed{a_n=2^n+2^n-2=2^{n+1}-2}$ である。