灯下 登录
番外 · 题谱 · 2001 · P11

2001 IMO Shortlist S11

组合 · P3/P6 · 压轴题

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

IMO Shortlist 2001 S11 combinatorics

A pile of nn pebbles is placed in a vertical column. This configuration is modified according to the following rules. A pebble can be moved if it is at the top of a column which contains at least two more pebbles than the column immediately to its right. (If there are no pebbles to the right, think of this as a column with 0 pebbles.) At each stage, choose a pebble from among those that can be moved (if there are any) and place it at the top of the column to its right. If no pebbles can be moved, the configuration is called a *final configuration*. For each nn , show that, no matter what choices are made at each stage, the final configuration obtained is unique. Describe that configuration in terms of nn .

IMO ShortList 2001, combinatorics problem 7, alternative

一堆 nn 鹅卵石被放置在垂直的柱子上。此配置根据以下规则进行修改。如果卵石位于柱子的顶部,并且该柱子比紧邻其右侧的柱子至少多包含两个卵石,则可以移动该卵石。 (如果右侧没有卵石,请将其视为具有 0 个卵石的柱子。)在每个阶段,从可移动的卵石(如果有)中选择一个卵石,并将其放置在右侧柱子的顶部。如果没有卵石可以移动,则该配置称为“最终配置”。对于每个 nn ,表明无论每个阶段做出什么选择,最终获得的配置都是唯一的。用 nn 描述该配置。

IMO ShortList 2001,组合问题 7,替代

提示 1

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

提示 2

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

提示 3

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

完整解答

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

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