2014年JJMO本選第4問の解説

証明の方針

(1),(2)ともに，「ある条件を満たす」→「どの島の避難先ともならない島が存在する」という形の命題で扱いにくいので，

「どの島の避難先ともならない島は存在しない」→「ある条件は満たされない」

を証明します（対偶法）。

そして「どの島も，とある島から避難先に指定されている」ことを利用してサイクルを作ります：

適当に島 $A_1$ を選ぶ。$A_1$ を避難先とする島 $A_2$ が存在する。さらに $A_2$ を避難先とする島 $A_3$ が存在する。これを繰り返していくといつか $A_1$ に戻ってくる（避難先は1つしかないので $A_2$ など途中の島に戻ってくることはない）。このかたまりをサイクルと呼ぶことにする。

上記が核心部分です。サイクルを作ることに気づけば（1）は解けたようなものです。（2）ではもう一工夫必要になります。

ちなみに， このようにグラフをたどっていきサイクルを作り出す議論は，数学オリンピックの問題や大学で学ぶグラフ理論で頻出です。

（1）の証明

$A_i$ より $A_j$ が大きいことを $A_i > A_j$ と書くことにします。

（2）の証明

実は，ほぼ同様な手法で $m$ が $4$ 以上の偶数でもダメだということが分かります。

つまり，$m=2k$ が $4$ 以上の偶数の場合：

$A_1 > A_3 > A_5 >\cdots > A_{2k-1} > A_1$ となり矛盾。

ここに気づくのが（2）の山になります。

よって，$m=2$ のみとなります。つまり，島たちはいくつかのペアに分解できます！

（※）「避難先の関係を保ったまま異なるペアに2本橋をかけることができる」のは図から分かります。

「避難先の関係を保ったまま異なるペアに3本以上橋をかけることはできない」のは4つの島の大小関係を場合分けしてしらみつぶしに調べれば確かめられます。

グラフ理論に少しでもなじみがあると取っ付きやすい問題でした。 →グラフ理論の基礎

Tag:各地の数オリの過去問