橋で結ばれた島に関する調査

問題の説明

高校数学ではなじみのないグラフの問題です．見た目のいかつさほど難問ではなく，特にグラフ理論の知識は必要ないので，はじめてこのような問題を見た人もチャレンジする価値はあると思います.

ひとつ目の条件に関して，島にかかっている橋の本数としてありうる値は $0$ ~ $2015$ の $2016$ 通りしかありないことに注意してください．

二つ目の条件は，少しわかりにくいかもしれませんので，曖昧さを避けるために別の言い方で表現します．$2016$ 個の島に上手に $A_0,A_1,...,A_{2015}$ と番号をつけたとき，すべての $k$　$(0 \le k \le 1007)$ に対して，$A_k$ と $A_{2015-k}$ が橋で結ばれていないようにできる，という意味です．

なんと，これだけの条件で島 $A$ にかかっている橋の本数が決定できてしまうのです．

ヒント1

上で設定したように，島に上手に $A_0,A_1,...,A_{2015}$ と番号をつけます．ここで，$A_0=A$としておきましょう．繰り返しになりますが，すべての $k$　$(0 \le k \le 1007)$ に対して，$A_k$ と $A_{2015-k}$ は橋で結ばれていません．さて，かかっている橋の本数が $2015$ 本であるような島は存在するでしょうか．

ヒント2

今回の問題は$2016$という数字に特に意味はありません．難しければ島の数をより小さくして図にかいてみてください．特に，かかっている橋の本数が最大であるような島を考えてみてください．その島と同じ組の島について何がいえるでしょうか．

解説

もし仮に，かかっている橋の本数が $2015$ 本であるような島が存在したとすると，それはすべての島に橋がかかっていることになります．ところが条件 $2$ よりこのような島は存在しません．したがって，島にかかっている橋の本数としてありうる値は $0$ ~ $2014$ の $2015$ 通りしかありません．ここで，条件 $1$ より，$A$ 以外の $2015$ 個の島にかかっている橋の本数はすべて異なるので，それらは $0$~$2014$ の整数をひとつずつとります．

$A_{2014}$ にかかっている橋の本数が $2014$ 本であるとします．すると，この島は同じ組である $A_1$ 以外のすべての島に橋がかかっています．このとき，$A_1$ 以外のすべての島は少なくとも橋が $1$ 本はかかっているので，$A_1$ にかかっている橋の本数は $0$ 本です．

$A_{2013}$ にかかっている橋の本数が $2013$ 本であるとします．すると，この島は $A_1,A_2$ 以外のすべての島に橋がかかっています．このとき，$A_1,A_2$ 以外のすべての島は少なくとも橋が $2$ 本はかかっているので，$A_2$ にかかっている橋の本数は $1$ 本です．以下同様にして，$A_k$にかかっている橋の本数はつぎの表のようになります． \begin{array}{c|ccccccccc} &A_0(=A)&A_1&A_2&\cdots&A_{1007}&A_{1008}&\cdots&A_{2013}&A_{2014} \\ \hline 橋の数&&0&1&&1006&1008&&2013&2014 \end{array} したがって，条件 $1$ より，島 $A_{2015}$ ($A$と組になっている島) にかかっている橋の本数は$1007$ 本となります．上の議論から，島 $A$ は島 $A_{2014},...,A_{1008}$ とのみ結ばれているので，$A$ にかかっている橋の本数は $\color{red}{1007}$ 本です．

---

一般に島の数が $2n$ 個のときは $n-1$ 本であることもいえます．