トップ› 東京大学› 2001年› 理系第5問

東京大学 2001年理系第5問解説

方針・初手

最初に $x$ リットルの水が入っているビーカーに注目し、これをビーカー $X$ と呼ぶ。 $X$ が途中で空になって取り除かれる、あるいは水の量が増えるための条件は、$X$ が操作 (a) または (b) の対象として選ばれることである。逆に、$X$ が最後まで $x$ リットルのまま残るということは、「一度も操作対象として選ばれない」ことを意味する。この性質を利用し、（1）、（2）ともに「結論を否定して矛盾を導く」背理法によるアプローチが有効である。

解法1

（1）の証明

最初に $x$ リットルの水が入っていたビーカーを $X$ とする。「$X$ は途中で空になって取り除かれるか、または最後まで残って水の量が増えている」ことを示すために、その否定である「$X$ は一度も選ばれることなく、最後まで水量 $x$ のまま残る」と仮定して矛盾を導く。

$X$ が最後まで水量 $x$ のまま残ったとすると、最終的に残る2個のビーカーのうち1個は $X$ であり、もう1個を $Y$ とする。水の総量は $1$ リットルであるから、$Y$ の水量は $1-x$ リットルである。

最後の操作（ビーカーが3個から2個になる操作）の直前の状態を考える。このとき、存在する3個のビーカーは $X$ と、ある2個のビーカー $A, B$ である。 $A, B$ の水量をそれぞれ $a, b$ ($a \leqq b$) とする。 $X$ はこの最後の操作でも選ばれなかったのだから、操作 (a) で $A$ が、操作 (b) で $B$ が選ばれたことになる。 (b) の操作では残りの中で最も水量の少ないものが選ばれるため、もし $x < b$ であれば $B$ ではなく $X$ が選ばれているはずである。よって、$b \leqq x$ が成り立つ。

この操作で $A$ と $B$ の水が合わさって $Y$ になったので、$a + b = 1 - x$ である。 $a \leqq b \leqq x$ であるから、以下の不等式が成り立つ。

$$ 1 - x = a + b \leqq x + x = 2x $$

これを整理すると、

$$ 1 \leqq 3x \iff x \geqq \frac{1}{3} $$

しかし、これは条件 $x < \frac{1}{3}$ に矛盾する。したがって、$X$ が最後まで水量 $x$ のまま残ることはなく、途中で空になって取り除かれるか、または最後まで残って水の量が増えていることが示された。

（2）の証明

最初に $x$ リットルの水が入っていたビーカー $X$ が、最後まで $x$ リットルのまま残らない、すなわち「途中の操作で一度でも $X$ が選ばれる」と仮定して矛盾を導く。

初期状態において、$X$ 以外のビーカーの水量はすべて $x$ 未満である。 $X$ が初めて操作 (a) または (b) で選ばれるためには、その直前の状態で、$X$ より水量が少ないビーカーが1個以下でなければならない。すなわち、$X$ 以外のビーカーのうち、少なくとも1つの水量が $x$ 以上になっている必要がある。

そこで、「$X$ 以外のビーカーが合体して、初めて水量が $x$ 以上になった」操作に注目する。その操作が行われる直前の状態において、全体のビーカーの総数を $k$ 個とする。この操作で選ばれ、合体して初めて $x$ 以上になる2個のビーカーを $A, B$ とし、その水量をそれぞれ $a, b$ ($a \leqq b$) とする。この時点で $X$ はまだ選ばれていないため、$a, b$ は $X$ 以外のビーカーの中で最小および2番目に小さい水量である。

ここで、$A$ と $B$ が合体してビーカーが1つ減るが、全体が2個になるまで操作は続く。もしこの操作の時点で $X$ 以外のビーカーが $A, B$ の2個しか存在しなければ、合体後は $X$ と $A+B$ の2個になり操作が終了してしまうため、「合体後に $X$ が選ばれる」という仮定に反する。したがって、合体前には $X, A, B$ 以外に少なくとももう1つビーカーが存在しなければならず、$k \geqq 4$ である。

$X, A, B$ 以外の $k-3$ 個のビーカーの水量を $c_1, c_2, \ldots, c_{k-3}$ とする。 $A, B$ は最小と2番目に小さいビーカーであったから、すべての $i$ について $c_i \geqq b$ が成り立つ。 $X$ 以外のビーカーの水量の総和は常に $1-x$ であるから、

$$ 1 - x = a + b + c_1 + c_2 + \cdots + c_{k-3} $$

条件より $A$ と $B$ が合体して初めて $x$ 以上になるので、$a + b \geqq x$ である。また $a \leqq b$ より、$2b \geqq a + b \geqq x$ であるから、$b \geqq \frac{x}{2}$ を得る。 $k \geqq 4$ より $c_i$ は少なくとも1つ存在し、その水量は $b$ 以上であるから、水量の総和について以下の評価ができる。

$$ 1 - x \geqq (a + b) + b \geqq x + \frac{x}{2} = \frac{3}{2}x $$

これを解くと、

$$ 1 \geqq \frac{5}{2}x \iff x \leqq \frac{2}{5} $$

これは条件 $x > \frac{2}{5}$ に矛盾する。したがって、$X$ 以外のビーカーの水量が $x$ 以上になることはなく、$X$ が操作で選ばれることはない。よって、$X$ は最後まで $x$ リットルの水が入ったままで残ることが示された。

解説

問題の操作のルールを数式（不等式）に翻訳できるかが問われる論証問題である。「最後まで〜残る（残らない）」という結論を示すために、背理法を用いると状況を設定しやすくなる。

（1）は、最後まで残った場合の最後の1回の操作（3個から2個になるとき）に焦点を当て、選ばれなかった要素の大きさを評価することで容易に矛盾を導ける。（2）は、「選ばれてしまう」ために必要な条件（他のビーカーが合体して $x$ 以上に成長すること）に着目し、その「初めて $x$ 以上になる瞬間」の直前における水量の和を不等式で下から評価するのがポイントである。最小の2つが $a, b$ であるという条件から $b \geqq \frac{x}{2}$ が導かれること、そして残りのビーカーも $b$ 以上であるという事実を組み合わせることで鮮やかに証明できる。