第4問
整数 が与えられている。山の斜面に 個の駅があり、すべて異なる高度にある。二つのケーブルカー会社 と はそれぞれ 台のケーブルカーを運行しており、各ケーブルカーはある駅から、途中で止まることなく、より高い駅へ利用客を運ぶ。 の 台のケーブルカーは 個の異なる出発点と 個の異なる到着点を持ち、より高い場所から出発するケーブルカーはより高い場所に到着する。同じ条件が についても成り立つ。ある会社によって2つの駅が結ばれているとは、低い方の駅から出発し、その会社のケーブルカーを1台以上使って、駅間の他の移動を一切行わずに、高い方の駅に到達できることをいう。両方の会社によって結ばれる2つの駅が存在することを保証できる、最小の正の整数 を求めよ。
ざっくり言うと
A によって結ばれる対は同じ行にある対、B によって結ばれる対は同じ列にある対だけであり、異なる駅が両方を満たすことはない。
詳しい解説
A では各行が1本の道なので、異なる2駅が A によって結ばれることは第1座標 i が同じことと同値である。B では各列が1本の道なので、B によって結ばれることは第2座標 j が同じことと同値である。異なる組が i も j も同じになることはない。よって k₀=n²−n では両社によって結ばれる対が存在しない場合があり、前の議論から k=n²−n+1 なら常に十分である。したがって保証される最小値は n²−n+1 である。