第4問

便は $2016$ 頂点の有向グラフ $G$ をなし、各頂点の出次数は $1$ である。$G$ が長さ $57$ の有向閉路を含むなら、この閉路上の任意の二都市はこの $57$ 閉路の短い方を回って高々 $28$ 便で互いに到達できるので、それらは同じ組に入れられない。スターウェイズはこのような配置を実現できるので、常に少なくとも $57$ 個の組が必要、すなわち $k\ge57$ である。