题面据 IMO Shortlist 可核档案整理;中文题意为本站自译,公式请以原始来源为准。
Lucy starts by writing integer-valued 2022-tuples on a blackboard. After doing that, she can take any two (not necessarily distinct) tuples and that she has already written, and apply one of the following operations to obtain a new tuple: and then write this tuple on the blackboard. It turns out that, in this way, Lucy can write any integer-valued 2022-tuple on the blackboard after finitely many steps. What is the smallest possible number of tuples that she initially wrote? (Czech Republic)
Lucy 首先在黑板上写下 整数值 2022 元组。完成此操作后,她可以采用她已编写的任意两个(不一定不同)元组 和 ,并应用以下操作之一来获取新元组: \begin{对齐} & \mathbf{v}+\mathbf{w}=\left(v_{1}+w_{1}, \ldots, v_{2022}+w_{2022}\right) \\ & \mathbf{v} \vee \mathbf{w}=\left(\max \left(v_{1}, w_{1}\right), \ldots, \max \left(v_{2022}, w_{2022}\right)\right) \end{aligned} 然后将此元组写在黑板上。事实证明,通过这种方式,Lucy 可以在有限的步骤之后在黑板上写出任何整数值的 2022 元组。她最初编写的元组的最小可能数量 是多少? (捷克共和国)
提示 1
先决定对象是什么:集合、图、排列、颜色、路径,还是一次操作后的状态。
提示 2
找一个极端对象、双计数式、不变量,或把限制转成图上的局部条件。
提示 3
把局部限制累加成全局矛盾,或给出覆盖全部情形的构造。
完整解答
这页先给题面、题型和提示阶梯,完整证明留给读者逐步展开。2022 年 IMO Shortlist C7 可先归入组合:第一步把题设翻成对象、条件、目标三行;第二步沿提示寻找不变量、标准构型或关键变形;第三步补齐边界情形,并回到题目原要求核对。
这题适合先独立想一轮再打开提示。不要急着搜索完整解答,先问自己:题面里最硬的限制是哪一句?