题面据 IMO Shortlist 可核档案整理;中文题意为本站自译,公式请以原始来源为准。
We are given an infinite deck of cards, each with a real number on it. For every real number , there is exactly one card in the deck that has written on it. Now two players draw disjoint sets and of 100 cards each from this deck. We would like to define a rule that declares one of them a winner. This rule should satisfy the following conditions: 1. The winner only depends on the relative order of the 200 cards: if the cards are laid down in increasing order face down and we are told which card belongs to which player, but not what numbers are written on them, we can still decide the winner. 2. If we write the elements of both sets in increasing order as and , and for all , then beats . 3. If three players draw three disjoint sets from the deck, beats and beats , then also beats . How many ways are there to define such a rule? Here, we consider two rules as different if there exist two sets and such that beats according to one rule, but beats according to the other. (Russia)
我们有一副无限的牌,每张牌上都有一个真实的数字。对于每个实数 ,这副牌中恰好有一张牌上写着 。现在,两名玩家从这副牌中抽出不相交的 和 组各 100 张牌。我们想定义一个规则来宣布其中一个获胜者。该规则应满足以下条件: 1. 获胜者仅取决于 200 张牌的相对顺序:如果牌面朝下按升序排列,并且我们知道哪张牌属于哪位玩家,但不知道上面写着什么数字,我们仍然可以决定获胜者。 2. 如果我们将所有 的两个集合的元素按升序写为 和 和 ,则 胜出。 3. 如果三名玩家从牌堆中抽出三组不相交的, 击败, 击败,则 也击败。有多少种方法来定义这样的规则?在这里,如果存在两个集合和,使得根据一个规则击败,但根据另一个规则击败,我们认为两个规则是不同的。 (俄罗斯)
提示 1
先决定对象是什么:集合、图、排列、颜色、路径,还是一次操作后的状态。
提示 2
找一个极端对象、双计数式、不变量,或把限制转成图上的局部条件。
提示 3
把局部限制累加成全局矛盾,或给出覆盖全部情形的构造。
完整解答
这页先给题面、题型和提示阶梯,完整证明留给读者逐步展开。2014 年 IMO Shortlist C6 可先归入组合:第一步把题设翻成对象、条件、目标三行;第二步沿提示寻找不变量、标准构型或关键变形;第三步补齐边界情形,并回到题目原要求核对。
这题适合先独立想一轮再打开提示。不要急着搜索完整解答,先问自己:题面里最硬的限制是哪一句?