Evolton

大阪大学 2015年度 前期日程 第2次学力試験理系数学 第5問

nを2以上の整数とする.
正方形の形に並んだn×nのマスに0または1のいずれかの数字を入れる.
マスは上から第1行,第2行,…,左から第1列,第2列,…,と数える.
数字の入れ方についての次の条件pを考える.

条件p:1からn−1までのどの整数i,jについても,
第i行,第i+1行と第j列,第j+1列とが作る2×2の4個のマスには
0と1が2つずつ入る.

問題の図

(1) 条件pを満たすとき,第n行と第n列の少なくとも一方には0と1が交互に現れることを示せ.

(2) 条件pを満たすような数字の入れ方の総数anを求めよ.

難易度8/ 10計算量7/ 10目安30分

場合の数、論証・証明 数え上げ、場合分け、一意性証明

方針

隣り合う2行を固定し、各列で上下2マスの和 uj を見る。条件 p は隣接する uj,uj+1 に対して uj+uj+1=2 と言い換えられるので、uj はすべて 1 であるか、0,2 が交互に並ぶかのどちらかである。前者は隣接2行が列ごとに反対、後者はその2行が同じ交互行であることを意味する。これを全ての隣接行に伝播させ、全行交互型または全列交互型に分類する。(1) はこの分類から従い、(2) は2種類を数えて重複する市松模様2通りを引く。

解答

(1)

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

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

条件 p より、第 i 行・第 i+1 行と第 j 列・第 j+1 列で作る 2×2 の4マスには、1 がちょうど2つ入る。したがって uj+uj+1=2 である。これがすべての j=1,2,…,n−1 で成り立つ。

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

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

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

したがって、任意の隣接2行について、次のどちらかが成り立つ。 (A) 2行は列ごとに互いに反対である または (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種類のどちらかである。 すべての行に 0 と 1 が交互に現れる入れ方 または すべての列に 0 と 1 が交互に現れる入れ方 である。逆に、このどちらかを満たす入れ方では、任意の隣接する 2×2 の4マスに 0 と 1 が2つずつ入るので、条件 p を満たす。

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

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

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

よって求める総数は an=2n+2n−2=2n+1−2 である。

総評

難度8、計算量7。目安時間は30分。局所的な 2×2 条件を、隣接2行の列ごとの和 uj に変換するのが核心である。uj+uj+1=2 から「列ごとに反対」または「同じ交互行」の2型に分かれ、それを上下へ伝播させると全行交互型・全列交互型の分類が得られる。(1) は分類の帰結であり、(2) は分類が必要十分であることを確認してから数える。最後に両方に属する市松模様2通りを引き忘れないことが、最も起こりやすいミスである。 原典の4×4配置例を復元し、第2行・第3列・中央の2×2ブロックを色分けした。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る阪大の場合の数の問題で問題集を作る

出典: 大阪大学 2015年度 前期 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。