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

2022 IMO Shortlist C7

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

IMO Shortlist 2022 C7 combinatorics

Lucy starts by writing ss integer-valued 2022-tuples on a blackboard. After doing that, she can take any two (not necessarily distinct) tuples v=(v1,,v2022)\mathbf{v}=\left(v_{1}, \ldots, v_{2022}\right) and w=(w1,,w2022)\mathbf{w}=\left(w_{1}, \ldots, w_{2022}\right) that she has already written, and apply one of the following operations to obtain a new tuple: v+w=(v1+w1,,v2022+w2022)vw=(max(v1,w1),,max(v2022,w2022))\begin{aligned} & \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} 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 ss of tuples that she initially wrote? (Czech Republic)

Lucy 首先在黑板上写下 ss 整数值 2022 元组。完成此操作后,她可以采用她已编写的任意两个(不一定不同)元组 v=(v1,,v2022)\mathbf{v}=\left(v_{1}, \ldots, v_{2022}\right)w=(w1,,w2022)\mathbf{w}=\left(w_{1}, \ldots, w_{2022}\right),并应用以下操作之一来获取新元组: \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 元组。她最初编写的元组的最小可能数量 ss 是多少? (捷克共和国)

提示 1

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

提示 2

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

提示 3

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

完整解答

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

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