2014年JJMO本選第4問の解説

組み合わせの良問を紹介します。証明だけでなく,考え方や重要なテクニックも紹介します。

グラフ理論の言葉を使わないので問題文が少し長いですが,意味は単純です。

問題

nn22 以上の整数とする。大きさの異なる nn 個の島があり,その島を繋ぐいくつかの橋がある。どの 22 つの島も 11 本の橋で結ばれているかいないかのいずれかであって,橋の両端は相異なる 22 つの島につながっている。

さて,これらの島はそれぞれの避難先を求めて災害に備えることにした。各々の島では,橋でその島と直接結ばれている島が1つ以上あったのでこのうち最も大きい島を避難先にした。

(1)nn が奇数ならば,どの島の避難先ともならない島が存在することを示せ。

(2)nn が偶数であり橋が n24\dfrac{n^2}{4} 本より多く存在するならば,どの島の避難先ともならない島が存在することを示せ。

グラフ理論の言葉を使うと「孤立点のない単純グラフ」を考える,ということです。

証明の方針

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

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

を証明します(対偶法)。

サイクル

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

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

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

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

(1)の証明

AiA_i より AjA_j が大きいことを Ai>AjA_i > A_j と書くことにします。

位数5のサイクル

証明

上記の議論により,島たちはいくつかのサイクルに分解できる(全ての島はどれか1つのサイクルに属する)。よって,島の数 mm が奇数のサイクルがないことを示せば良い。

これは例えば m=5m=5 で実験すれば簡単に分かる:

A2A_2 の避難先が A1A_1 なので A1>A3A_1 > A_3

A4A_4 の避難先が A3A_3 なので A3>A5A_3 > A_5

以下同様に,A5>A2,A2>A4,A4>A1A_5 > A_2, A_2 > A_4, A_4 > A_1 となる。

しかし,55 つの不等式より A1>A1A_1 > A_1 となるので矛盾。

一般の奇数の場合も全く同様に証明できる。

以上から,「どの島もとある島から避難先に指定されている」ならばいくつかの偶サイクルで表せることが分かったので(1)が示された。

(2)の証明

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

つまり,m=2km=2k44 以上の偶数の場合:

A1>A3>A5>>A2k1>A1A_1 > A_3 > A_5 >\cdots > A_{2k-1} > A_1 となり矛盾。

ここに気づくのが(2)の山になります。

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

証明

nn 個の島は n2\dfrac{n}{2} 個のペアに分解できた。あとは異なるペアの間にかかる橋を数えればよい。

異なるペア ii とペア jj の間にかかる橋は多くても2本(※)なので,全体の橋の数は最大で,

n2+n2C2×2=n24\dfrac{n}{2}+{}_{\frac{n}{2}}\mathrm{C}_2\times 2=\dfrac{n^2}{4}

shima3

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

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

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

JJMO(日本ジュニア数学オリンピック)の組み合わせの問題はJMOの対策にもなりますね。

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