数学A 場合の数 問題 47 解説

方針・初手

条件 $p$ は、隣り合う $2$ 行と隣り合う $2$ 列でできるすべての $2\times 2$ マスに、$0,1$ がちょうど $2$ 個ずつ入るという条件である。

まず、隣り合う $2$ 行だけに注目する。各列における縦方向の和を考えると、隣り合う列でその和の合計が常に $2$ になる。このことから、隣り合う $2$ 行の関係はかなり強く制限される。

解法1

第 $i$ 行第 $j$ 列の数を $x_{ij}$ とする。ただし $x_{ij}$ は $0$ または $1$ である。

条件 $p$ より、任意の $1\leq i,j\leq n-1$ について

$$ x_{ij}+x_{i+1,j}+x_{i,j+1}+x_{i+1,j+1}=2 $$

が成り立つ。

まず、固定した隣り合う $2$ 行、第 $i$ 行と第 $i+1$ 行を考える。各列 $j$ について

$$ s_j=x_{ij}+x_{i+1,j} $$

とおく。このとき $s_j$ は $0,1,2$ のいずれかであり、上の条件から

$$ s_j+s_{j+1}=2 $$

が成り立つ。

したがって、次のいずれかが起こる。

（i） ある $j$ で $s_j=1$ となる場合。

このとき $s_j+s_{j+1}=2$ より $s_{j+1}=1$ である。また逆向きにも同様に考えられるので、すべての列で

$$ s_1=s_2=\cdots=s_n=1 $$

となる。すなわち、第 $i$ 行と第 $i+1$ 行は各列で互いに異なる。

（ii） どの $j$ についても $s_j\neq 1$ である場合。

このとき $s_j$ は $0$ または $2$ であり、$s_j+s_{j+1}=2$ だから、$s_j$ と $s_{j+1}$ は $0,2$ が交互に現れる。したがって第 $i$ 行と第 $i+1$ 行は各列で等しく、しかも各行には $0,1$ が交互に現れる。

つまり、隣り合う $2$ 行については、

$$ \text{互いに各列で異なる} $$

または

$$ \text{同じ交互列である} $$

のどちらかである。

(1) の証明

第 $n$ 行に $0,1$ が交互に現れていないとする。このとき、ある $j$ について

$$ x_{n,j}=x_{n,j+1} $$

である。

第 $n-1$ 行と第 $n$ 行、さらに第 $j$ 列と第 $j+1$ 列でできる $2\times 2$ マスを考える。下段の $2$ 個が等しいので、条件 $p$ を満たすためには、上段の $2$ 個も等しく、しかも下段とは反対の値でなければならない。

よって第 $n-1$ 行と第 $n$ 行は、少なくともこの列において縦方向の和が $1$ である。先ほどの考察より、第 $n-1$ 行と第 $n$ 行はすべての列で互いに異なる。

したがって、第 $n-1$ 行も第 $n$ 行と同じ位置で隣り合う成分が等しく、交互にはなっていない。

同じ議論を第 $n-2$ 行と第 $n-1$ 行、第 $n-3$ 行と第 $n-2$ 行、$\ldots$ と繰り返すと、任意の隣り合う $2$ 行はすべての列で互いに異なることがわかる。

よって、各列では上から下に進むごとに $0,1$ が交互に現れる。特に第 $n$ 列には $0,1$ が交互に現れる。

したがって、第 $n$ 行に $0,1$ が交互に現れないならば、第 $n$ 列には $0,1$ が交互に現れる。

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

(2) の計数

まず、条件 $p$ を満たす入れ方は、次の $2$ 種類の少なくとも一方に属することを示す。

（ア） すべての行に $0,1$ が交互に現れる。

（イ） すべての列に $0,1$ が交互に現れる。

(1) より、第 $n$ 行または第 $n$ 列の少なくとも一方には $0,1$ が交互に現れる。

第 $n$ 行に $0,1$ が交互に現れるとする。このとき、第 $n-1$ 行と第 $n$ 行でできる任意の隣り合う $2$ 列の $2\times 2$ マスを考えると、下段には $0$ と $1$ が $1$ 個ずつある。条件 $p$ より、上段にも $0$ と $1$ が $1$ 個ずつなければならない。したがって第 $n-1$ 行にも $0,1$ が交互に現れる。

これを上へ繰り返せば、すべての行に $0,1$ が交互に現れる。

同様に、第 $n$ 列に $0,1$ が交互に現れるならば、すべての列に $0,1$ が交互に現れる。

よって、条件 $p$ を満たす入れ方は、必ず （ア） または （イ） に含まれる。

次に、それぞれの個数を数える。

すべての行に $0,1$ が交互に現れる場合、各行は

$$ 0101\cdots $$

または

$$ 1010\cdots $$

の $2$ 通りである。各行は独立に選べるので、その個数は

$$ 2^n $$

である。このとき、任意の $2\times 2$ マスでは各行に $0,1$ が $1$ 個ずつあるため、条件 $p$ は確かに満たされる。

同様に、すべての列に $0,1$ が交互に現れる場合も、その個数は

$$ 2^n $$

である。

ただし、両方に含まれる入れ方を重複して数えている。すべての行にも列にも $0,1$ が交互に現れる場合、左上のマスを決めると全体が一意に定まる。左上のマスは $0$ または $1$ の $2$ 通りなので、重複部分は

$$ 2 $$

通りである。

したがって、求める総数 $a_n$ は

$$ a_n=2^n+2^n-2=2^{n+1}-2 $$

である。

解説

この問題の核心は、隣り合う $2$ 行だけ、または隣り合う $2$ 列だけに注目して、局所条件を一次元の条件に落とすことである。

隣り合う $2$ 行について、各列の縦方向の和を $s_j$ とおくと、条件 $p$ は $s_j+s_{j+1}=2$ という単純な形になる。ここから、隣り合う $2$ 行は「完全に反対」か「同じ交互列」のどちらかに限られる。

(1) は、この制約を下から上へ伝播させる問題である。第 $n$ 行が交互でなければ、すべての隣り合う行が互いに反対になり、その結果、第 $n$ 列が交互になる。

(2) では、(1) によって全体が「すべての行が交互」または「すべての列が交互」に分類される。この分類ができれば、あとは重複を引く包除原理で数えられる。

答え

(1)

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

(2)

$$ a_n=2^{n+1}-2 $$