IMO 2020
問題 4

$n^2$ 個の駅を標高が低い順に駅 $1,2,\dots,n^2$ とする．集合 $\{1,2,\dots,n^2\}$ を $n^2-k$ 個の集合に分割する方法であって，相異なる駅 $x,y$ が会社 $A$ で結ばれていることと $x,y$ が同じ集合に属することと同値になるようなものがただ $1$ つあるのでこの分割された集合を $A_1,A_2,\dots,A_{n^2-k}$ とし，同様に $B_{1},B_2,\dots,B_{n^2-k}$ を定める．

$k\geq n^2-n+1$ のとき $(n^2-k)^2\lt n^2$ より，相異なる駅 $x,y$ と整数 $i,j$ であって $x,y\in A_i,x,y\in B_j$ が成り立つものが存在する．すなわち駅 $x,y$ は会社 $A,B$ のどちらでも繋がれている．

$k=n^2-n$ のとき

• $A_i=\{(i-1)n+1,(i-1)n+2,\dots,(i-1)n+n\}\quad (i=1,2,\dots,n)$
• $B_i=\{i,i+n,\dots,i+n(n-1)\}\quad (i=1,2,\dots,n)$

に対応するようなケーブルカーの配置を考えればいかなる相異なる $2$ 駅 $x,y$ も会社 $A,B$ のどちらかでは繋がれていない．ケーブルカーを削ることで $k\lt n^2-n$ の場合も同様の構成ができる．

以上より求める $k$ の最小値は $n^2-n+1$ である．