MathLabs

第4题

梦幻国由 20162016 个城市组成。星际航空公司想在城市对之间设立若干单向航班，使得每个城市恰好有一班出发航班。求最小的正整数 kk，使得无论星际航空公司如何设立航班，都总能把这些城市划分成 kk 组，使得从任一城市出发，无法用至多 2828 次航班到达同一组中的另一城市。
第 4/4 步：移除并重新插入 vv
上一步下一步
deg⁡−(v)≤28, deg⁡+(v)≤28  ⟹  v has≤56 neighbours\deg^-(v)\le28,\ \deg^+(v)\le28 \implies v \text{ has} \le56 \text{ neighbours}
详细分析

移除 vv；由归纳假设，剩余图可划分成至多 5757 个合法组。顶点 vv 在原图中入度和出度都至多为 2828，因此至多与 5656 个其他顶点相邻，最多占据 5757 组中的 5656 组。于是必有某组不含它的任何邻居，把 vv 放入该组即可完成归纳。因此 5757 组总是足够，故 k=57k=57。