MathLabs

第4問

ドリームランドという国は 20162016 の都市からなる。航空会社スターウェイズは、各都市がちょうど一本の出発便を持つように、都市の組の間に一方向の便をいくつか設定したい。スターウェイズがどのように便を設定しても、任意の都市から高々 2828 回の便で同じ組の別の都市に到達できないように都市を kk 個の組に分けられるような最小の正整数 kk を求めよ。
ステップ 3/4: 頂点数に関する帰納法による補題
前のステップ次のステップ
n≥1, deg⁡+≤28  ⟹  split into 57 groups, no internal edgen\ge1,\ \deg^+\le28 \implies \text{split into } 57 \text{ groups, no internal edge}
詳しい解説

補題：すべての頂点の出次数が高々 2828 である n≥1n\ge1 頂点の有向グラフは、組内に辺がないように 5757 個の組に分けられる。nn に関する帰納法で証明する：基底ケース n=1n=1 は自明である。n>1n>1 のとき、辺の総数は高々 28n28n なので、ある頂点 vv の入次数は高々 2828 である（そうでなければすべての頂点の入次数が少なくとも 2929 となり、28n28n を超える辺数になってしまう）。