MathLabs

第4题

梦幻国由 20162016 个城市组成。星际航空公司想在城市对之间设立若干单向航班，使得每个城市恰好有一班出发航班。求最小的正整数 kk，使得无论星际航空公司如何设立航班，都总能把这些城市划分成 kk 组，使得从任一城市出发，无法用至多 2828 次航班到达同一组中的另一城市。
第 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}
详细分析

引理：任意 n≥1n\ge1 个顶点、每个顶点出度至多为 2828 的有向图，都可划分成 5757 组，组内没有边。对 nn 归纳证明：基础情形 n=1n=1 显然。当 n>1n>1 时，边总数至多为 28n28n，因此存在某个顶点 vv 的入度至多为 2828（否则每个顶点入度至少为 2929，边数将超过 28n28n）。