JJMO予選2019問10


答え\(\cdots4850\)


【分析】
このようなJJMOの予選の組み合わせ論の問題は「小さな値で実験する」というのがかなり有効で、10番という終盤の問題とはいえ、「多分これが正解かな?」というものにたどり着けた人も意外と多いのではないのでしょうか。問題文の意味を理解するのに一苦労しますけれども。

【略解】
港を\(A_1,A_2,\cdots,A_{100}\)とおく。
「\(A_1-A_2\)」で\(A_1\)と\(A_2\)を結ぶ直行便が存在することを表すことにする。
(港の数が\(4,5,6\)のときあたりでとりあえず考えてみるなどすることにより、)\(A_1-A_2-A_3-\cdots-A_{99}-A_{100}-A_2\)のように100個の直行便が存在するとき、全ての2つの港間の直行便ができ、新たに作られる直行便が最大となると考えられる。これを示す。

(全ての2つの港間の直行便ができることの説明)
\begin{eqnarray} &&A_1-A_2-A_3-\cdots-A_{99}-A_{100}より、A_1-A_{100}\\
&&A_1-A_2-A_{100}-A_{99}-\cdots-A_3より、A_1-A_3\\
&&A_1-A_3-A_2-A_{100}-A_{99}-\cdots-A_4より、A_1-A_4\\
&&A_1-A_4-A_3-A_2-A_{100}-A_{99}-\cdots-A_5より、A_1-A_5\end{eqnarray}
同様に、任意の\(k\)に対し\(A_1-A_k\)となる。
すると、\(k<l\)なる隣り合わない100以下の自然数\(k,l\)に対し、\(A_k-A_{k+1}-\cdots A_{l-1}-A_1-A_{k-1}-A_{k-2}-\cdots-A_2-A_{100}-A_{99}-\cdots-A_l\)より\(A_k-A_l\)となる。
以上より、全ての2つの港間の直行便が新たに作られる。

(最大性の説明)
逆に、これより多く直行便が作られるような直行便の初期配置は存在しないことを示す。まず、新たな直行便を作るためには少なくとも1つ、ある港Xから出発して全ての港を通り、ある港Yにたどり着くようなルートが存在する必要があるので、最初に直行便が99個は必要である。しかし、それだけでは新たに作られる直行便はX-Yのみである。
\(∴\ 100\)個の直行便からはじまり、全ての2つの港間に直行便が作られる先ほど考えた初期配置が新たに増える直行便の数が最大となるものである。

\(∴\ \)そのときの新たに増える直行便の個数を求めると、これは、正100角形の対角線の本数に等しく、$$100×97÷2=4850$$

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です