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

2018 IMO Shortlist C4

组合 · P3/P6 · 压轴题

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

IMO Shortlist 2018 C4 combinatorics

An anti-Pascal pyramid is a finite set of numbers, placed in a triangle-shaped array so that the first row of the array contains one number, the second row contains two numbers, the third row contains three numbers and so on; and, except for the numbers in the bottom row, each number equals the absolute value of the difference of the two numbers below it. For instance, the triangle below is an anti-Pascal pyramid with four rows, in which every integer from 1 to 1+2+3+4=101+2+3+4=10 occurs exactly once: 42657183109.\begin{array}{cccc} & & 4 \\ & 2 & 6 & \\ & 5 \quad 7 \quad 1 \\ 8 & 3 & 10 & 9 . \end{array} Is it possible to form an anti-Pascal pyramid with 2018 rows, using every integer from 1 to 1+2++20181+2+\cdots+2018 exactly once? (Iran)

反帕斯卡金字塔是一组有限的数字,放置在三角形数组中,使得数组的第一行包含一个数字,第二行包含两个数字,第三行包含三个数字,依此类推;并且,除了底行中的数字之外,每个数字都等于其下面的两个数字之差的绝对值。例如,下面的三角形是一个有四行的反帕斯卡金字塔,其中从 1 到 1+2+3+4=101+2+3+4=10 的每个整数都只出现一次: 42657183109\begin{array}{cccc} & & 4 \\ & 2 & 6 & \\ & 5 \quad 7 \quad 1 \\ 8 & 3 & 10 & 9 。 \end{array} 是否可以使用从 1 到 1+2++20181+2+\cdots+2018 的每个整数一次形成一个具有 2018 行的反帕斯卡金字塔? (伊朗)

提示 1

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

提示 2

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

提示 3

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

完整解答

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

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