2010 年山西预赛 · 第 11 题

F4解答题组合计数综合

一次足球邀请赛共安排了 $n$ 支球队参加，每支球队预定的比赛场数分别是 $m_{1}, m_{2}, \dots, m_{n}$ 。如果任两支球队之间至多安排了一场比赛，则称 $(m_{1}, m_{2}, \dots, m_{n})$ 是一个有效安排。证明：如果 $(m_{1}, m_{2}, \dots, m_{n})$ 是一个有效安排，且

m_{1} \geq m_{2} \geq \dots \geq m_{n},

则可去掉一支球队，并重新调整各队之间的对局情况，使得

(m_{2} - 1, m_{3} - 1, \dots, m_{m_{1} + 1} - 1, m_{m_{1} + 2}, \dots, m_{n})

也是一个有效安排。

作答

这是解答题，请在纸上写出完整过程。写完后对照解答给自己评分。

解析

为什么评为 F4（会透露解法方向）

需以邻点数比较证明保度交换真实可行，再用有限改进把最高度点接到指定高位邻集，不能只凭直觉重排对局。

用到的方法（会透露解法方向）

核心工具：把限制关系画成图、操作中的不变量

专题卡：关系图与禁配结构

2010 年山西预赛 · 第 11 题

作答

解析

提示

思路

解答

复核

方法总结