题面据 USAMO 可核档案整理;中文题意为本站自译,公式请以原始来源为准。
A father, mother and son hold a family tournament, playing a two person board game with no ties. The tournament rules are:
(i) The weakest player chooses the first two contestants.
(ii) The winner of any game plays the next game against the person left out.
(iii) The first person to win two games wins the tournament.
The father is the weakest player, the son the strongest, and it is assumed that any player's probability of winning an individual game from another player does not change during the tournament. Prove that the father's optimal strategy for winning the tournament is to play the first game with his wife.
一对父亲、母亲和儿子举办了一场家庭锦标赛,玩的是两人棋盘游戏,没有任何关系。比赛规则为:
(i) 最弱的选手选择前两名参赛者。
(ii) 任何一场比赛的获胜者将与被淘汰的人进行下一场比赛。
(iii) 第一个赢得两场比赛的人赢得比赛。
父亲是最弱的玩家,儿子是最强的,并且假设任何玩家从另一玩家那里赢得个人比赛的概率在锦标赛期间不会改变。证明父亲赢得比赛的最佳策略是和妻子一起打第一场比赛。
提示 1
先决定对象是什么:集合、图、排列、颜色、路径,还是一次操作后的状态。
提示 2
找一个极端对象、双计数式、不变量,或把限制转成图上的局部条件。
提示 3
把局部限制累加成全局矛盾,或给出覆盖全部情形的构造。
完整解答
这页先给题面、题型和提示阶梯,完整证明留给读者逐步展开。1974 年 USAMO P4 可先归入组合:第一步把题设翻成对象、条件、目标三行;第二步沿提示寻找不变量、标准构型或关键变形;第三步补齐边界情形,并回到题目原要求核对。
这题适合先独立想一轮再打开提示。不要急着搜索完整解答,先问自己:题面里最硬的限制是哪一句?