同一骨架 2022 年广西预赛 · P006833
两题的覆盖构造都要从少数控制点推广到整个三角形。把覆盖区域看成圆盘或线段的定距邻域后,利用凸性检查分块三角形的顶点,才能证明没有漏掉边角之外的区域。
固定圆盘覆盖点集与沿折线移动探测器,使用的是不同覆盖集,却共享凸分块的完整覆盖论证。
正三角形内的圆覆盖与分离点集
在边长为 的正三角形中有 个点,若用一个半径为 的圆形硬币总可以 盖住其中的 个点,则 的最小值为。
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
先独立尝试,再展开工具说明与想法来源。
先回想这道题的想法,再试试当前题。
两个点距离不超过 ,以其中点为圆心的半径 圆盘即可盖住它们;反之同一圆盘内两点距离至多为直径。圆盘是凸集,若三角形三个顶点在盘内,整个三角形也在盘内。
想法从哪来:硬币能盖住两点,只取决于两点距离是否不超过直径,因此先把问题转成“多大点集必有一对近点”。要确定最小点数,两面都要做:一面造出尽量多的两两远点,另一面把整个三角形分配给有限个能容纳近点的小区域。 边长按四份分割有两种尺度:用较大的三角格阵安排分离点,给反例;用较小的等分网格寻找圆盘覆盖,给保证。覆盖时同向小三角形的外接圆很自然,但不能就此忽略反向小三角形。把后者分成三块,各交给相邻圆盘,并通过顶点距离与圆盘凸性验证整块被盖住,才可以对任意点使用鸽巢原理。
一枚半径为 的硬币能同时盖住两点,当且仅当两点距离不超过 。 因此一方面要构造尽量多的两两距离大于 的点,另一方面要用直径 的蜂窝胞覆盖整个三角形。
把正三角形置于坐标平面,使三个顶点为
先证明 。在三边方向间距均为 的三角格阵上,取四行点,每行点数依次为 。这 个点均位于原三角形内,任意两点的距离至少为 。由于
任意一枚半径为 的硬币都不能同时盖住其中两点。因此 个点时题述性质 不一定成立。
再证明 已足够。把原正三角形的每条边四等分,并过分点作各边的平行线, 得到 个边长为 的小正三角形,其中与原三角形方向相同的有
个。在这 个同向小三角形的中心各放一个半径为 的圆盘。
每个同向小三角形的外接圆半径为
所以它完全在以自身中心为圆心的相应圆盘内。对任一反向小三角形,设 为其中心, 连接 与三个顶点,把它分成三块。每一块都邻接一个同向小三角形;该块的三个顶点 到这个相邻同向小三角形中心的距离均为 。由于圆盘是凸集,这一整块都在相应 圆盘内。因此上述 个圆盘覆盖了整个原三角形。
任取 个点,对每个点任选一个盖住它的圆盘。由抽屉原理,至少两个点被分到同一圆盘, 它们的距离不超过该圆盘的直径 ,故可由一枚半径为 的硬币同时盖住。
因此所求最小值为
下界构型的最近点距离为 ,严格大于硬币直径,故确实不能覆盖两点。 上界中的小三角形边长为 ,其外接圆半径恰为 ;反向小三角形的三块 分别由相邻圆盘覆盖。距离等于 的边界情形仍可由硬币覆盖,抽屉数为 无误。
“一个圆覆盖两点”可转成点对距离上界。最小点数通常由两部分夹出:用分离点集给下界, 再用有限个小直径圆盘覆盖配合抽屉原理给上界;正三角形的等分网格能同时提供两种构造。
下界需构造10个两两距离大于直径的点,上界需用10个圆盘实际覆盖整个三角形,特别要证明反向小三角形也被邻盘覆盖。
核心工具:抽屉原理与极端构造
同一骨架 2022 年广西预赛 · P006833
两题的覆盖构造都要从少数控制点推广到整个三角形。把覆盖区域看成圆盘或线段的定距邻域后,利用凸性检查分块三角形的顶点,才能证明没有漏掉边角之外的区域。
固定圆盘覆盖点集与沿折线移动探测器,使用的是不同覆盖集,却共享凸分块的完整覆盖论证。
已记下,谢谢!