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

2014 IMO Shortlist C6

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

IMO Shortlist 2014 C6 combinatorics

We are given an infinite deck of cards, each with a real number on it. For every real number xx, there is exactly one card in the deck that has xx written on it. Now two players draw disjoint sets AA and BB 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 A={a1,a2,,a100}A=\left\{a_{1}, a_{2}, \ldots, a_{100}\right\} and B={b1,b2,,b100}B=\left\{b_{1}, b_{2}, \ldots, b_{100}\right\}, and ai>bia_{i}>b_{i} for all ii, then AA beats BB. 3. If three players draw three disjoint sets A,B,CA, B, C from the deck, AA beats BB and BB beats CC, then AA also beats CC. How many ways are there to define such a rule? Here, we consider two rules as different if there exist two sets AA and BB such that AA beats BB according to one rule, but BB beats AA according to the other. (Russia)

我们有一副无限的牌,每张牌上都有一个真实的数字。对于每个实数 xx,这副牌中恰好有一张牌上写着 xx。现在,两名玩家从这副牌中抽出不相交的 AABB 组各 100 张牌。我们想定义一个规则来宣布其中一个获胜者。该规则应满足以下条件: 1. 获胜者仅取决于 200 张牌的相对顺序:如果牌面朝下按升序排列,并且我们知道哪张牌属于哪位玩家,但不知道上面写着什么数字,我们仍然可以决定获胜者。 2. 如果我们将所有 ii 的两个集合的元素按升序写为 A={a1,a2,,a100}A=\left\{a_{1}, a_{2}, \ldots, a_{100}\right\}B={b1,b2,,b100}B=\left\{b_{1}, b_{2}, \ldots, b_{100}\right\}ai>bia_{i}>b_{i},则 AA 胜出BB。 3. 如果三名玩家从牌堆中抽出三组不相交的ABCA、B、CAA 击败BBBB 击败CC,则AA 也击败CC。有多少种方法来定义这样的规则?在这里,如果存在两个集合AABB,使得AA根据一个规则击败BB,但BB根据另一个规则击败AA,我们认为两个规则是不同的。 (俄罗斯)

提示 1

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

提示 2

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

提示 3

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

完整解答

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

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