灯下 登录
番外 · 题谱 · 1998 · P5

1998 Putnam A5

组合 · P2/P5 · 中段题

题面据 Putnam 可核档案整理;中文题意为本站自译,公式请以原始来源为准。 PDF:https://kskedlaya.org/putnam-archive/1998.pdf。

Putnam 1998 A5 combinatorics

Let F\mathcal F be a finite collection of open discs in R2\mathbb R^2

whose union contains a set ER2E\subseteq \mathbb R^2. Show that there

is a pairwise disjoint subcollection D1,,DnD_1,\ldots, D_n in F\mathcal F

such that

Ej=1n3Dj.E\subseteq \cup_{j=1}^n 3D_j.

Here, if DD is the disc of radius rr and center PP, then 3D3D is the

disc of radius 3r3r and center PP.

F\mathcal FR2\mathbb R^2 中开盘的有限集合

其并集包含集合 ER2E\subseteq \mathbb R^2。表明有

F\mathcal F 中的成对不相交子集合 D1,,DnD_1,\ldots, D_n

这样

Ej=1n3Dj.E\subseteq \cup_{j=1}^n 3D_j.

这里,如果DD是半径为rr、中心为PP的圆盘,那么3D3D就是

半径为 3r3r 且中心为 PP 的圆盘。

提示 1

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

提示 2

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

提示 3

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

完整解答

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

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