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

2019 IMO Shortlist C9

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

IMO Shortlist 2019 C9 combinatorics

For any two different real numbers xx and yy, we define D(x,y)D(x, y) to be the unique integer dd satisfying 2dxy<2d+12^{d} \leq|x-y|<2^{d+1}. Given a set of reals F\mathcal{F}, and an element xFx \in \mathcal{F}, we say that the scales of xx in F\mathcal{F} are the values of D(x,y)D(x, y) for yFy \in \mathcal{F} with xyx \neq y. Let kk be a given positive integer. Suppose that each member xx of F\mathcal{F} has at most kk different scales in F\mathcal{F} (note that these scales may depend on xx ). What is the maximum possible size of F\mathcal{F} ? (Italy)

对于任何两个不同的实数 xxyy,我们将 D(x,y)D(x, y) 定义为满足 2dxy<2d+12^{d} \leq|x-y|<2^{d+1} 的唯一整数 dd。给定一组实数 F\mathcal{F} 和一个元素 xFx \in \mathcal{F},我们说 F\mathcal{F}xx 的标度是 yFy \in \mathcal{F}xyx \neq yD(x,y)D(x, y) 值。令 kk 为给定的正整数。假设 F\mathcal{F} 的每个成员 xxF\mathcal{F} 中最多有 kk 个不同的尺度(请注意,这些尺度可能取决于 xx )。 F\mathcal{F} 的最大可能大小是多少? (意大利)

提示 1

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

提示 2

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

提示 3

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

完整解答

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

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