トップ› 大阪大学› 2015年› 理系第5問

大阪大学 2015年理系第5問解説

方針・初手

マス目の各位置を座標で表し、隣接するマスの関係を数式で定式化する。 $2 \times 2$ の 4 マスの和が常に 2 であるという条件から、ある行（または列）で隣り合う 2 マスに同じ数字が入っている場合、その上下（または左右）の行（または列）でも同じ関係が連鎖していくことに着目する。（1）はこの連鎖の性質を用いて、背理法により「すべての行が交互になる」か「すべての列が交互になる」ことを示す。（2）は（1）で得られた性質を利用し、行が交互になる場合と列が交互になる場合の和集合の要素数を求める。

解法1

(1)

第 $i$ 行、第 $j$ 列のマスに入る数字を $a_{i,j}$ と表す（$1 \le i \le n, 1 \le j \le n$）。数字は 0 または 1 であるから、$a_{i,j} \in \{0, 1\}$ である。条件 $p$ より、任意の $i, j \in \{1, \dots, n-1\}$ について以下の式が成り立つ。

$$ a_{i,j} + a_{i,j+1} + a_{i+1,j} + a_{i+1,j+1} = 2 $$

これを、行ごとの隣接 2 マスの和として次のようにまとめる。

$$ (a_{i,j} + a_{i,j+1}) + (a_{i+1,j} + a_{i+1,j+1}) = 2 $$

$a_{i,j} \in \{0, 1\}$ であるから、$a_{i,j} + a_{i,j+1}$ の値は 0, 1, 2 のいずれかである。もし $a_{i,j} = a_{i,j+1}$ であるならば、$a_{i,j} + a_{i,j+1}$ の値は 0 または 2 となる。上式の和が 2 であることから、このとき $a_{i+1,j} + a_{i+1,j+1}$ の値はそれぞれ 2 または 0 でなければならない。これは、$a_{i+1,j} = a_{i+1,j+1}$ であり、かつ $a_{i+1,j} = 1 - a_{i,j}$ であることを意味する。すなわち、ある行で横に隣り合う 2 マスが同じ数字であれば、その一つ下の行の同じ位置の 2 マスも同じ数字であり、かつ数字が反転する。

これを帰納的に適用すると、ある $j$ に対して $a_{i_0,j} = a_{i_0,j+1}$ となるような $i_0$ が 1 つでも存在すれば、すべての $k \ (1 \le k \le n)$ について以下のことが成り立つ。

$$ a_{k,j} = a_{k,j+1} $$

同様に、列方向の隣接 2 マスの和として式をまとめる。

$$ (a_{i,j} + a_{i+1,j}) + (a_{i,j+1} + a_{i+1,j+1}) = 2 $$

これより、ある $i$ に対して $a_{i,j_0} = a_{i+1,j_0}$ となるような $j_0$ が 1 つでも存在すれば、すべての $l \ (1 \le l \le n)$ について以下のことが成り立つ。

$$ a_{i,l} = a_{i+1,l} $$

ここで、「すべての行において0と1が交互に現れる」か「すべての列において0と1が交互に現れる」のいずれかが成り立つことを背理法で示す。これを否定し、「0と1が交互に現れない行が存在し、かつ、0と1が交互に現れない列が存在する」と仮定する。

交互に現れない行が存在するということは、ある $j_0$ が存在して、任意の $k$ について $a_{k, j_0} = a_{k, j_0+1}$ が成り立つということである。交互に現れない列が存在するということは、ある $i_1$ が存在して、任意の $l$ について $a_{i_1, l} = a_{i_1+1, l}$ が成り立つということである。

このとき、$2 \times 2$ の 4 マス $(i_1, j_0), (i_1, j_0+1), (i_1+1, j_0), (i_1+1, j_0+1)$ に着目する。先の性質 $a_{k, j_0} = a_{k, j_0+1}$ に $k = i_1$ および $k = i_1+1$ を代入すると、以下の 2 式を得る。

$$ a_{i_1, j_0} = a_{i_1, j_0+1} $$

$$ a_{i_1+1, j_0} = a_{i_1+1, j_0+1} $$

これらと条件 $p$ を用いると、先述の通り値が反転するため、以下の関係が成り立つ。

$$ a_{i_1+1, j_0} = 1 - a_{i_1, j_0} $$

一方で、性質 $a_{i_1, l} = a_{i_1+1, l}$ に $l = j_0$ を代入すると、以下の式を得る。

$$ a_{i_1, j_0} = a_{i_1+1, j_0} $$

これらを組み合わせると、$a_{i_1, j_0} = 1 - a_{i_1, j_0}$ すなわち $2 a_{i_1, j_0} = 1$ となるが、$a_{i_1, j_0}$ は整数であるため矛盾する。したがって仮定は誤りであり、「すべての行において0と1が交互に現れる」または「すべての列において0と1が交互に現れる」の少なくとも一方が成り立つ。

前者が成り立てば第 $n$ 行には 0 と 1 が交互に現れ、後者が成り立てば第 $n$ 列には 0 と 1 が交互に現れるため、題意は示された。

(2)

（1）の結果より、条件 $p$ を満たす数字の入れ方は、以下の 2 つの集合 $A, B$ の和集合 $A \cup B$ に含まれる。 $A$: すべての行において 0 と 1 が交互に現れるような入れ方の集合 $B$: すべての列において 0 と 1 が交互に現れるような入れ方の集合

集合 $A$ に属する入れ方について考える。各行が交互であるため、第 1 列の各要素 $a_{1,1}, a_{2,1}, \dots, a_{n,1}$ をそれぞれ 0 または 1 に決めれば、残りのすべてのマスの数字は一意に定まる。第 1 列の決め方は $2^n$ 通りである。この $2^n$ 通りの入れ方すべてにおいて、任意の $i, j$ について $a_{i,j} + a_{i,j+1} = 1$ かつ $a_{i+1,j} + a_{i+1,j+1} = 1$ が成り立つ。したがって、任意の $2 \times 2$ の 4 マスの和は常に 2 となり、条件 $p$ を満たす。よって、集合 $A$ の要素数は $n(A) = 2^n$ である。

同様に、集合 $B$ に属する入れ方について考える。各列が交互であるため、第 1 行の各要素 $a_{1,1}, a_{1,2}, \dots, a_{1,n}$ を 0 または 1 に決めればすべての数字が定まり、これらもすべて条件 $p$ を満たす。よって、集合 $B$ の要素数は $n(B) = 2^n$ である。

次に、共通部分 $A \cap B$ に属する入れ方を考える。これはすべての行とすべての列が交互になる場合であり、盤面全体が市松模様になる配置である。左上のマス $a_{1,1}$ の数字を 0 または 1 のどちらにするか決めれば、隣接するマスがすべて異なる数字となるため、盤面全体のマスの数字が一意に定まる。よって、共通部分の要素数は $n(A \cap B) = 2$ である。

求める総数 $a_n$ は、和集合 $A \cup B$ の要素数に等しい。包除原理より、以下のように計算できる。

$$ a_n = n(A \cup B) = n(A) + n(B) - n(A \cap B) $$

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

解説

局所的な条件（$2 \times 2$ のマスの和が 2）から大域的な性質（すべての行または列が交互に現れる）を導き出す論証問題である。マス目に関する問題では、隣り合う要素の和や差分に注目し、その性質が縦横にどのように伝播していくかを捉えるのが定石である。本問は行と列に対して対称な条件が与えられているため、「行に〜という性質がないなら、列に〜という性質がある」といった背理法の構成が非常に有効に働く。（1）の結論を正しく解釈すれば、（2）は集合の包含関係を利用した極めて平易な数え上げに帰着する。