第4問
整数 が与えられている。山の斜面に 個の駅があり、すべて異なる高度にある。二つのケーブルカー会社 と はそれぞれ 台のケーブルカーを運行しており、各ケーブルカーはある駅から、途中で止まることなく、より高い駅へ利用客を運ぶ。 の 台のケーブルカーは 個の異なる出発点と 個の異なる到着点を持ち、より高い場所から出発するケーブルカーはより高い場所に到着する。同じ条件が についても成り立つ。ある会社によって2つの駅が結ばれているとは、低い方の駅から出発し、その会社のケーブルカーを1台以上使って、駅間の他の移動を一切行わずに、高い方の駅に到達できることをいう。両方の会社によって結ばれる2つの駅が存在することを保証できる、最小の正の整数 を求めよ。
ざっくり言うと
横に隣り合う駅を結べば各行が A の鎖になり、縦に隣り合う駅を結べば各列が B の鎖になる。両社とも n(n−1) 台を使う。
詳しい解説
A には 1≤i≤n, 1≤j<n に対する (i,j) から (i,j+1) への n(n−1) 台を運行させ、B には 1≤i<n, 1≤j≤n に対する (i,j) から (i+1,j) への n(n−1) 台を運行させる。A のケーブルカーでは高度が n 増加し、B では1増加する。さらに各出発高度のブロック内で対応する到着高度の順序は保たれ、異なるブロックは重ならないので、各社は「高い出発点ほど高い到着点」という単調性条件を満たす。