東京大学前期 2001年第5問 (解答解説)

容量1リットルの個のビーカー(ガラス容器)に水が入っている．で空のビーカーは無い．入っている水の総量は1リットルである．またリットルの水が入っているビーカーがただ一つあり，その他のビーカーにはリットル未満の水しか入っていない．

このとき，水の入っているビーカーが2個になるまで，次の(a)から(c)までの操作を，順に繰り返し行う．

(a)　入っている水の量が最も少ないビーカーを一つ選ぶ．
(b)　さらに，残りのビーカーの中から，入っている水の量が最も少ないものを一つ選ぶ．
(c)　次に，(a)で選んだビーカーの水を(b)で選んだビーカーにすべて移し，空になったビーカーを取り除く．

この操作の過程で，入っている水の量が最も少ないビーカーの選び方が一通りに決まらないときは，そのうちのいずれも選ばれる可能性があるものとする．

のとき，最初にリットルの水の入っていたビーカーは，操作の途中で空になって取り除かれるか，または最後まで残って水の量が増えていることを証明せよ．
のとき，最初にリットルの水の入っていたビーカーは，最後までリットルの水が入ったままで残ることを証明せよ．

【解答】

初期状態における $m$ 個のビーカーと総水量 $S = 1\text{ L}$ — 図 1: 初期状態における個のビーカーと総水量

[L] の水が入っているビーカーをとする．ビーカーに入っている水の全質量を [L]とする．題意より

である．

(1)

ビーカーが残り3個になったときの水量 $t, s, x$ と背理法の矛盾 — 図 3: ビーカーが残り3個になったときの水量と背理法の矛盾

題意を背理法で示す．命題の否定「が最後まで残って，かつ水が増えていない」が成立すると仮定する．操作を続けてビーカーが残り3個になった時は残っており，かつ (a) (b) の過程で選択されないので，残り2つのビーカーにはリットル以下の水しか入っていない．これらを [L]とすると，

である．題意よりだから(式1)も合わせて

となり矛盾する．よって背理法により題意は示された．

(2)

題意を背理法で示す．命題の否定「は (a)(b) の過程で選択される」が成立すると仮定する． (a)(b) の過程では，3個以上のビーカーの中から，入っている水の量が少ない順に2個のビーカーが選ばれる．よって，が選ばれる時， [L] 以上の水が入っているビーカーが以外に1個以上存在する．このようなビーカーが以外に2個以上存在すると仮定すると

となり，(式1)のに矛盾する．

したがって， [L] 以上の水が入っているビーカーは以外に1個である．それをとする．以上の議論よりが選ばれる時はビーカーは残り3個であり，その水の量はとして，

と表せる．

ここで，はじめの状態ではが最も水の量が多いから，ビーカーは最初は存在しておらず， [L]以下の水の入った2個のビーカーの水をあわせて作られる．( [L]より多くの水の入ったビーカーが用いられているならば，リットルのビーカーは残されない．) よって，

だから，(式5)より

だが，題意よりだから

となり(式1)のに矛盾する．

よって背理法によって題意は示された．

【別解】

(2)

のビーカーがあるところからは以下のような議論も可能である．

[L] のビーカーは最初からは存在しないので，このビーカーがつくられる時を考える．この時，個のビーカーがあるとし，水量の少ない順にとする．又としても良い．この時，(a)でが，(b)でが各々選ばれるとして良い．に入っている水量をとすると，が以上だから

であり，に入っている水量和は [L] 以下である．ここからのビーカーをのぞいたビーカーの内水量の和は [L] 以下だから，が必要で

である． (式1),(式5)から

である．これはに反し矛盾するから背理法により題意は示された．

\bigskip

この問題のOpen Issue（1件）

【解答】

(1)

(2)

【別解】

(2)