第4問

整数

n > 1

が与えられている。山の斜面に

n^2

個の駅があり、すべて異なる高度にある。二つのケーブルカー会社

A

と

B

はそれぞれ

k

台のケーブルカーを運行しており、各ケーブルカーはある駅から、途中で止まることなく、より高い駅へ利用客を運ぶ。

A

の

k

台のケーブルカーは

k

個の異なる出発点と

k

個の異なる到着点を持ち、より高い場所から出発するケーブルカーはより高い場所に到着する。同じ条件が

B

についても成り立つ。ある会社によって2つの駅が結ばれているとは、低い方の駅から出発し、その会社のケーブルカーを1台以上使って、駅間の他の移動を一切行わずに、高い方の駅に到達できることをいう。両方の会社によって結ばれる2つの駅が存在することを保証できる、最小の正の整数

k

を求めよ。

ステップ 3/8: 候補値を調べる

ざっくり言うと

提案された境界では、各社は n² 個すべての駅をわずか n−1 本の鎖に収めるため、この数え上げの圧力が働く。

k=n^2-n+1\quad\Longrightarrow\quad c_A=c_B=n-1.

詳しい解説

k=n²−n+1 とおく。前段階の数え上げにより、A も B も n²−(n²−n+1)=n−1 本の鎖に n² 個の駅を分ける。これが両社によって結ばれる駅の対を強制することを示す。