灯下 登录
番外 · 闲灯 / IMO Shortlist / C5 · combinatorics

2010 IMO Shortlist C5

题面据 IMO Shortlist 可核档案整理;中文题意为本站自译,公式请以原始来源为准。

IMO Shortlist 2010 C5 combinatorics

n4n \geq 4 players participated in a tennis tournament. Any two players have played exactly one game, and there was no tie game. We call a company of four players bad if one player was defeated by the other three players, and each of these three players won a game and lost another game among themselves. Suppose that there is no bad company in this tournament. Let wiw_{i} and i\ell_{i} be respectively the number of wins and losses of the ii th player. Prove that i=1n(wii)30\sum_{i=1}^{n}\left(w_{i}-\ell_{i}\right)^{3} \geq 0 (South Korea)

n4n \geq 4 玩家参加了网球锦标赛。任意两名选手只打一场比赛,并且没有平局。如果一个玩家被其他三名玩家击败,并且这三名玩家各自赢了一场比赛并输掉了另一场比赛,我们称四名球员为坏人。假设这次比赛没有坏公司。设wiw_{i}i\ell_{i}分别为第ii个玩家的获胜次数和失败次数。证明 i=1n(wii)30\sum_{i=1}^{n}\left(w_{i}-\ell_{i}\right)^{3} \geq 0 (韩国)

提示 1

先决定对象是什么:集合、图、排列、颜色、路径,还是一次操作后的状态。

提示 2

找一个极端对象、双计数式、不变量,或把限制转成图上的局部条件。

提示 3

把局部限制累加成全局矛盾,或给出覆盖全部情形的构造。

完整解答

这页先给题面、题型和提示阶梯,完整证明留给读者逐步展开。2010 年 IMO Shortlist C5 可先归入组合:第一步把题设翻成对象、条件、目标三行;第二步沿提示寻找不变量、标准构型或关键变形;第三步补齐边界情形,并回到题目原要求核对。

这题适合先独立想一轮再打开提示。不要急着搜索完整解答,先问自己:题面里最硬的限制是哪一句?