5大阪大学 2015年 数学 第5問解答・解説

各マスの数字を $a_{ij}$ とする。$a_{ij}$ は0または1である。$s_{ij}=a_{ij}+a_{i,j+1}$ とおけば、条件pは $$s_{ij}+s_{i+1,j}=2\qquad(1\le i,j\le n-1)$$ と表せる。また、隣り合う二行の同じ列の和を $v_k=a_{i,k}+a_{i+1,k}$ とおくと $$v_k+v_{k+1}=s_{i,k}+s_{i+1,k}=2.$$

(1) 第n行が交互でないとする。すると、あるjで $a_{n,j}=a_{n,j+1}$ となり、$s_{n,j}=0$ または $s_{n,j}=2$ である。関係 $s_{i,j}=2-s_{i+1,j}$ を上の行へ順にたどると、全行でこの和は0または2となり、隣り合う行では0と2が入れ替わる。従って列j,j+1では、隣り合う二行の数はそれぞれ上下で異なり、$v_j=v_{j+1}=1$ となる。等式 $v_k+v_{k+1}=2$ を左と右へ順に用いると全てのkで $v_k=1$。特に第n列では隣り合う行の数字が異なるので、第n列は0と1が交互である。第n行が交互の場合も含め、(1)が示された。

(2) 第1行が交互でない場合、あるjで隣り合う二数字が等しい。上と同じ議論を使うと、任意の隣り合う二行について全てのkで $v_k=1$ となる。したがって各行は直前の行を全て反転したものに一意に定まる。第1行には交互な2通りを除く $2^n-2$ 通りあるから、この場合は $2^n-2$ 通り。

第1行が交互の場合は全てのjで $s_{1j}=1$。関係 $s_{i,j}+s_{i+1,j}=2$ により全ての行で $s_{ij}=1$ となり、各行は交互に並ぶ。各行ごとに先頭の数字を0または1から選べるので、この場合は $2^n$ 通りである。

二つの場合は互いに排反で、合わせると $$a_n=(2^n-2)+2^n=2^{n+1}-2.$$