灯下 登录
番外 · 题谱 · 2014 · P14

2014 IMO Shortlist C8

组合 · P3/P6 · 压轴题

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

IMO Shortlist 2014 C8 combinatorics

A card deck consists of 1024 cards. On each card, a set of distinct decimal digits is written in such a way that no two of these sets coincide (thus, one of the cards is empty). Two players alternately take cards from the deck, one card per turn. After the deck is empty, each player checks if he can throw out one of his cards so that each of the ten digits occurs on an even number of his remaining cards. If one player can do this but the other one cannot, the one who can is the winner; otherwise a draw is declared. Determine all possible first moves of the first player after which he has a winning strategy. (Russia)

一副牌由 1024 张牌组成。在每张卡上,写入一组不同的十进制数字,其中没有两组数字重合(因此,其中一张卡是空的)。两名玩家轮流从牌堆中拿牌,每回合一张牌。当这副牌空了之后,每个玩家检查他是否可以扔掉一张牌,以便十个数字中的每一个出现在他剩余的牌上的偶数张上。如果一名玩家能做到这一点而另一名玩家不能,则能做到的一方获胜;否则宣布平局。确定第一个玩家的所有可能的第一步,然后他就有了获胜的策略。 (俄罗斯)

提示 1

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

提示 2

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

提示 3

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

完整解答

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

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