論理問題には背理法で挑め – 2001年東大 数学 第5問
2001年東大 数学 第5問 は、一見してどの分野の問題かわかりません。問題文も長く、捨て問オーラ全開です。問題文は以下の通りです。
容量 1 リットルの m 個のビーカー（ガラス容器）に水が入っている。m ≧ 4 で空のビーカーは無い。入っている水の総量は 1 リットルである。また x リットルの水が入っているビーカーがただ一つあり，その他のビーカーには x リットル未満の水しか入っていない。
このとき，水の入っているビーカーが 2 個になるまで，次の (a) から (c) までの操作を，順に繰り返し行う。
(a) 入っている水の量が最も少ないビーカーを一つ選ぶ。
(b) さらに，残りのビーカーの中から，入っている水の量が最も少ないものを一つ選ぶ。
(c) 次に，(a) で選んだビーカーの水を (b) で選んだビーカーにすべて移し，空になったビーカーを取り除く。
この操作の過程で，入っている水の量が最も少ないビーカーの選び方が一通りに決まらないときは，そのうちのいずれも選ばれる可能性があるものとする。
(1) x < \frac{1}{3} のとき，最初に x リットルの水の入っていたビーカーは，操作の途中で空になって取り除かれるか，または 最後まで残って水の量が増えていることを証明せよ。
(2) x > \frac{2}{5} のとき，最初に x リットルの水の入っていたビーカーは，最後まで x リットルの水が入ったままで残ることを証明せよ。
本問には、微積分や三角関数のような、高校で習う数学の単元がほとんど出てきません。その点では世紀の難問1998年後期第3問に似ていますが、あちらでは剰余類が出てきた（解法によっては行列や数学的帰納法を使う場合もある）のにもかかわらず、本問ではそれすら出てきません。
本問で唯一出てくるのは、背理法です。これを武器に、論理的思考力でもって一気に調伏します。パズル好きの人向けの問題と言えるでしょう。
それでは早速、見ていきます。
2001年東大 数学 第5問 題意の整理
問題文に描かれたオペレーションは、以下の通りです。
- 各ビーカーを水量の昇順に並べ、1番から順に番号を振る。同水量のビーカーが複数あった場合の並べ方は、任意
- 1番のビーカーの水を、2番のビーカーに入れる
- 空になった1番のビーカーは除ける
- 1～3の手順を、残りビーカーが2つになるまで繰り返す
水量の少ないビーカーから、じわじわと集約を掛けていくイメージです（図1）。
2001年東大 数学 第5問 小問1の解法
題意が把握できたところで、小問1に取り掛かります。小問1は思いのほか簡単です。背理法を使って証明します。
最初に x リットルの水が入っていたビーカーおよびその水量を、 b_0 と表記します。初期状態では b_0 = x です。
x < \frac{1}{3} のとき，最後まで b_0 = x であったと仮定します。
すると、最終状況において b_0 は最大か、2番目に多いかのどちらかですが、 b_0 = x < \frac{1}{3} なので、 b_0 が最大と言うことはあり得ません。
したがって、2番目に水が多いということになります。
ここで、最後から1つ前の、ビーカーが3つある状況を考察します。 b_0 の他のビーカーおよびその水量を b_1, b_2 と置き、 b_1 \leqq b_2 であるとします。
このとき、 b_0 は最後まで変化しないのですから、ビーカーの水量に
b_1 \leqq b_2 \leqq b_0 = x < \frac{1}{3}の関係が成り立っているはずです。ところがこれは、 b_1 + b_2 + b_0 = 1 であることに矛盾します。
ゆえに、 b_0 の水量が最後まで変化しないということはあり得ない、すなわち b_0 = 0 か、または b_0 > x のいずれかであることが証明できました。
2001年東大 数学 第5問 小問2の解法
以下、 b_k,k=0,1,2,\cdots は、ビーカー及びその水量を表すものとします。また、 b_0 を最初に x リットルの水が入っていたビーカーであるとします。
オペレーションの性質から、 x が十分大きい、たとえば x > \frac{1}{2} ならば、 b_0 = x は最後まで最強なので、水量は増減しません。小問2は、 b_0 が最後まで水量が変化しない x の十分条件を求める問題です。
小問2もまた、背理法で攻めます。
ビーカーが途中で空にならないことの証明
b_0 には最初からそこそこの水量が入っていますので、途中で比較水量が最小になって空になる、などと言うことはありそうにありません。
そこでまずこれを証明します。
もしあるタイミングで b_0 = 0 になったとすると、その1回前のオペレーションで、 b_0 以外に少なくとも2つのビーカー b_1,b_2 が存在して、ビーカーの水量に
b_0 \leqq b_1 \leqq b_2
の関係が成り立つはずです。ところが、 b_0 > \frac{2}{5} なので、 b_1,b_2 > \frac{2}{5} であり、これは b_0 + b_1 + b_2 \leqq 1 であることに矛盾します。
したがって、 b_0 は最後まで空になることはありません。
ビーカーの水量が増えないことの証明
つぎに、 b_0 の水量が途中で増えないことの証明です。
もしあるタイミングで b_0 > x になったとすると、その1回前のオペレーションで、 b_0 は水量の昇順に並べた時の2番であり、 b_0 より水量の多いビーカーが少なくとも1つ存在しています。すなわち、このタイミングでビーカーは3個以上存在しています。
そこで、 b_0 より水量の多いビーカーが初めて生成された時の状況を考えます。このタイミングは、 b_0 の水量が増える直前の状態（ビーカー3個以上）よりさらに前なので、ビーカーの総数は4個以上です。
このとき、 b_0 が最も大きく、かつ、小さいほうから2つのビーカーの水量の合計が b_0 以上になります。
すなわち、3つのビーカー b_1,b_2,b_3 (b_1 \leqq b_2 \leqq b_3) が存在して、ビーカーの水量に
b_1 \leqq b_2 \leqq b_3 \leqq b_0 \\
\text{かつ} \\
b_1 + b_2 \geqq b_0の関係が成り立つはずです。ここで b_1 は最少ビーカーであり、 ビーカーを水量の昇順に並べた時、 b_1 と b_2 の間にはビーカーはありません。また、 b_2 と b_0 の間には、 b_3 以外のビーカーが存在している場合もあります。
b_1 + b_2 \geqq b_0
かつ
b_2 \geqq b_1
なので、
2b_2 \geqq b_1 + b_2\geqq b_0
すなわち
b_2 \geqq \frac{1}{2}b_0です。したがって、
b_3 \geqq b_2 \geqq \frac{1}{2}b_0です。ところが、
b_1+b_2 +b_3 +b_0 \leqq 1
なので、
\begin{aligned}
b_0 & \leqq 1 - b_1-b_2 -b_3 \\
& \leqq 1-b_0 -\frac{1}{2}b_0 \\
&= 1 -\frac{3}{2}b_0
\end{aligned}です。これから
b_0 \leqq \frac{2}{5}が導かれますが、これは b_0 = x > \frac{2}{5} であることに矛盾しています。ゆえに、 b_0 は最後まで水量が増えないことが証明できました。
解法のポイント
本問は問題文が長い上に、類似の問題もあまり見ないため、攻略方針が立てにくいところがありますが、問題文をよく読むとそんなに複雑なことはやっていないので、パズルとかが好きな人にはチャンスである可能性があります。
実際、小問1は比較的容易に解けるので、題意が理解できたなら必ずチェックしておきたいところです。
本問を背理法で証明することは、誰でも思いつけると思いますので、あとは論理的思考力の勝負です。この手の推論に慣れておくには、整数や剰余類の問題を多くやっておくと効果がありますが、いったん勉強を離れて、パズルや頭の体操的なものに多く触れておくことも、発想が柔軟になって論理思考の瞬発力が付けられると思います。