2015大阪大学理系5番

2015 阪大理系
問題 5
n を 2 以上の整数とする。正方形の形に並んだ n × n のマスに 0 または 1 のい
ずれかの数字を入れる。マスは上から第 1 行、第２行、. . . 左から第１列、第２
列、. . . と数える。数字の入れ方についての次の条件 p を考える。
条件 p：1 から n − 1 までのどの整数 i, j についても第 i 行、第 i + 1
行と第 j 列、第 j + 1 列とが作る 2 × 2 の 4 個のマスにが 0 と 1 が
２つずつ入る。
第
１
列
第
２
列
第
３
列
第
４
列
第1行
0
1
0
0
第2行
1
0
1
1
第3行
0
1
0
0
第4行
1
0
1
1
第2行
第３列
2 × 2 の 4 個のマス
（n = 4 の場合の入れ方の例）
(1) 条件 p を満たすとき、第 n 行、第 n 列の少なくとも一方には 0 と 1 が交互
に現れることを示せ。
(2) 条件 p を満たすような数字の入れ方の総数 an を求めよ。
解答行と列を入れ替えても、0 と 1 を入れ替えても議論の本質は変わらないことに
注意しておく。行と列での双対性が成立しているのである。別の言い方をすれば、対
角線に関して対称移動しても条件 p は成り立つのである。
(1) 命題を数学的帰納法で示す。
(i) n = 2 のときは、
1
0
0
1
0
0
1
1
または
または
c
Darumafactory
0
1
1
0
1
0
1
0
または
または
1
1
0
0
0
1
0
1
-1-
または
RadicalMath
の 6 通りでどれも適している。
(ii) n = k のとき、命題が成り立つと仮定する。このとき、k 行目が 0 と 1 が交
互に現れるとしてもよい。さらに、k 行目の左が 0 であるとしてもよい。つ
まり、
0
1
0
1
0
···
0
1
0
1
0
1
0
···
1
0
または
である。いま、前者の場合を考える。このとき、k + 1 行目に条件 p を満た
すように 0,1 を並べると、(a, b, c, d は k + 1 列目の数字)
0
0
1
1
0
0
1
1
0
0
···
···
0
0
1
1
a
1
······
b
0
1
1
0
0
1
1
0
0
1
···
···
0
1
1
0
c
2
······
d
または
1 の場合は、a = 0, b = 0 となるから、k + 1 列目は確かに 0 と 1 が交互に
2 の場合は、d = 1 とすると、c = 0 となり、k + 1 列目は確かに 0
現れる。
と 1 が交互に現れる。d = 0 とすると c = 1 となる。このときは。k + 1 列
目に 0 と 1 が交互に現れない。
∗
0
1
∗
1
0
∗
0
1
∗
1
0
∗
0
1
···
···
···
∗
0
1
e
1
0
f
3
1 ······
0
もしこのような場合があるならば、k − 1 行目の e, f は (0, 0) になり、その上
の k − 2 行目の２数は (1, 1) になる。これが１行目まで繰り返されて、k + 1
列目が 0 と 1 が交互に現れることになる。以上より、命題は成立。
【別証明】いま、１列目の i, i + 1 行目が同じ数 a であるとすると２列目の i, i + 1
行目 a と異なる b になる。したがって、i, i + 1 行目の列は下のようになる。
a
a
b
b
a
a
b
b
a
a
···
···
a
a
b
b
···
···
この議論は行と列を言い換えても成立する。この性質を用いて、背理法により、
命題を証明する。すなわち命題を否定して、矛盾を導く。
第 n 行にも第 n 列にも 0 と 1 が交互に現れないとする。すると、第 n 行で第 i, i+1
列目に同じ数字 a が並び、第 n 列で第 i, i + 1 行目に同じ数字 b が並ぶ (a = b で
もよい)。このとき、下図の表において、x = y かつ x = z であるがこれは 2 × 2
c
Darumafactory
-2-
RadicalMath
のマスに同じ数字が３個以上はいることになり、矛盾である。よって示せた。
···
···
···
···
···
···
···
···
x
z
y
w
b
a
a
a
···
···
···
···
···
···
···
···
a
a
b
b
···
···
(2) 条件 p によれば、ある i 行の数字の列とその下の i + 1 行の数字の列については、
同じ数字の列か、反転をして数字の列かである。この性質は列に関しても成り
立つ。
0
1
1
1
0
0
0
1
0
1
1
1
0
0
0
1
0
1
1
1
0
0
0
1
1
0
0
0
1
1
1
0
に現れる列を A 列と呼び、そうでない列を B 列と
0
1
1
1
0
0
0
1
呼ぶ。いま、1 行目が B 列ならば、２行目も B 列
1
0
0
0
1
1
1
0
になり、· · · · · · 、n 行目も B 列になる。このとき、
0
1
1
1
0
0
0
1
n 列目は縦に 0 と 1 が交互に現れなければならな
いから、どの i 行の列と i + 1 行の列は反転してい
1
0
0
0
1
1
1
0
0
1
1
1
0
0
0
1
なければならない。したがって、1 行目が B 列で
1
0
0
0
1
1
1
0
ある場合を数えて、
0
1
1
1
0
0
0
1
1
0
0
0
1
1
1
0
以下では行の数字列について考える。0 と 1 が交互
2n − 2 通り
一方、1 行目が A 列ならば、n 行目の A 列になるから、１列目を決めて、２列目、
· · · · · · と反転した数字決めていけばよいから、やはり、
2n − 2 通り
さらに、１行目の１列目も 0 と 1 が交互に現れる場合は 2 通りあるから、
an = (2n − 2) × 2 + 2 = 2n+1 − 2
である。
c
Darumafactory
-3-
RadicalMath

Download Report