一个单位圆盘里用红和蓝两种颜色染出每一个点
无论怎么染色,必然存在两个同色点距离恰好为d
请问这里d的上界
Moser纺锤体单位圆盘距离
用户提出了一个关于单位圆盘(半径为1)的染色问题:
- 用红蓝两色对单位圆盘内的每一个点进行染色。
- 无论怎么染色,必然存在两个同色点,它们的距离恰好等于d。
- 这样的d的上界是多少?
这是一个经典的组合几何和拉姆齐型问题。它类似于“在平面或特定区域内用有限颜色染色点时,必然存在某种特定距离的同色点对”。这让人联想到范德瓦尔登定理、Gallai定理,但更直接相关的是“距离图”和“哈达玛格问题”或“距离拉姆齐问题”。
我们需要理解“上界”在这里的含义:对于所有可能的二染色,都存在同色点对距离恰好为d。d的“上界”是指:存在一个最大的d值,使得对于任意d' < d,命题对所有二染色都成立。或者,上界是指满足该性质的最小d值的估计?题目问的是“d的上界”,这暗示我们需要找到一个最大的d,使得无论怎么染色,都必然存在距离为d的同色点对。换句话说,我们希望找到最大的d,使得距离为d的图的拉姆齐数R(D_d) ≤ 2(或类似表述)。
实际上,这个问题更像一个“距离图”的拉姆齐问题。对于单位圆盘(半径为1),我们考虑所有点之间的最大可能距离是2(直径)。问题要求找出最大的d,使得任何二染色都包含一个单色的点对,其距离恰好为d。这类似于“Erdos–Hadwiger–Nelson问题”或“距离图着色问题”。
让我重新表述这个问题:对于单位圆盘D = {x ∈ ℝ² : ||x|| ≤ 1},使用两种颜色(红、蓝)对D中的点进行任意着色。我们的问题是:对于哪些距离d,以下陈述恒成立?
P(d):在D的任何二染色中,都存在两个同色的点x, y ∈ D,使得||x - y|| = d。
题目在问:“无论怎么染色,必然存在两个同色点距离恰好为d”,即对于所有红色/蓝色着色,都存在一对同色点恰好相距d。这里的“d的上界”是指使得此性质恒成立的最大可能的d。
我们需要找出所有d的上确界,使得该性质对所有着色都成立。
或者,是否可以理解为我们需要找到最小的d,使得该性质对所有着色都成立?但“上界”一词表明我们需要找最大的d。实际上,如果对所有d ≤ d₀,该性质都成立,那么“上界”就是d₀。对于超过该值的距离,可能存在一种无单色点对的着色方式。因此,问题在于:求满足条件的最小上界d₀?还是在所有轨迹成立条件下的最大d值?通常“上界”指的是可能的最大值。
但需要注意:“上界”也可能是在询问:对于怎样的d,该命题为真?此时的“上界”是指最大的这样的d。例如,若命题在d ≤ √3时成立,则上界就是√3。
从对这类问题的通常理解来看,我们需要找到使得“距离图为d”的单位圆盘满足二染色下的拉姆齐性质时的最大距离d,也就是距离d₀。
现在考虑一些着色方案。例如,以该单位圆盘的中心O为基准,将所有点按到O的距离进行着色:比如,距离小于r的点染成红色,其余染成蓝色。但这会产生连续的色区,无法避免存在距离为任意小的同色点对?实际上,我们是否总能避免某些特定距离?对于任意给定的距离d,我们可以设计一种着色方案,使得不存在距离恰好为d的单色点对。针对固定的d,这种方法或许可行,但我们需要一种能同时避免所有小于某值的小距离出现的着色方案?实际上,该命题强调的是单一的d。
我们需要找出最大的d,使得对任意一种二着色方式,都必然存在一对同色的点,其距离恰好为d。另一种思路是:我们希望找到最大的d,使得以d为边长的单位距离图在单位圆盘内具有“2-拉姆齐”性质(即任何二染色都会产生单色的d-边)。
给定一个集合S,当S中的点具有唯一距离d时,其距离图G(S, d)是完全图吗?不,该距离图定义在顶点集为S,边连接距离恰好为d的点对上。
但在这里,我们关注的是点对的性质:任何二染色都会产生一个单色的距离d。我们需要找到最大的d,使得对于单位圆盘D的任意二染色,都存在一对点x, y ∈ D,满足||x - y|| = d,且x和y颜色相同。
因此,我们需要找出所有满足如下条件的d的上确界:存在一个避免单色距离d的二染色。
等价地,定义d* = sup{ d : 存在一种D的二染色,使得不存在距离为d的单色点对 }。那么所求的“上界”(即命题恒成立的d的上界)就是d。实际上,d是使得“存在一种避免单色距离d的染色方式”的d的上确界。对于任意d > d,命题必然始终成立(即任何染色都会产生单色距离d);而对于d ≤ d,存在一种染色方式能够避免单色距离d。因此,“使得命题恒成立的最大d”就是d*?等等,我们需要仔细考虑:
- 对于给定的d,我们要判断命题是否对所有染色都成立。如果成立,则称d为“好”的。因此我们希望找到最大的好d值。记D_good = {d ∈ ℝ^+ : P(d) 恒成立}。我们希望求出sup D_good。
- 如果存在一种染色方式可以避免单色距离d,那么P(d)就不成立,因此d ∉ D_good。所以避开某距离的染色方式的存在性决定了哪些d值是不成立的。
- 因此,sup D_good = inf{ d : 对所有更小的d' < d,都存在避开d'的染色 }?可能如此。
更好地说:使得命题对所有染色都成立的所有d的集合,即那些对于任意染色都不可避免会出现的单色距离。对于那些可以避免出现的距离,其补集即为可避免的距离。令A = {d: 存在一种对D的二染色,能避免单色距离为d的点对}。那么我们要求的答案可能是sup A(因为从上方趋近的任意距离都是不可避免的)。实际上,当d > sup A时,d必然不可避免(如果d大于任何可避免距离的上确界,则不存在能避免d的染色方式);而若d = sup A,则情况较复杂:是否避免了上确界距离?若上确界本身不属于集合A,则它可能是不可避免的。但“上界”这一说法可能即指sup A:即仍存在避开染色的距离的上确界;而超过该值的任何距离都不可避免。
因此,问题转化为:寻找最大的d,使得存在一种对单位圆盘D的二染色方案,其中任意两个同色点之间的距离都不等于d。问题中的答案即为此d。由于问题中“d的上界”指的是“必然出现的距离d的最大值”,这实际上正是最大的可避免距离。
因此,答案应为最大的d,使得存在一个不含该距离同色点对的二染色方案;即存在一个不含单色距离d的二染色。最大的这样的d值就是所求的上界。
现在的问题是如何计算这个值。
可能的方法是:考虑若干点的分布以及有限种染色方式的问题。虽然单位圆盘包含无穷多个点,但或许我们可以简化为一个有限的点集,以便应用鸽巢原理。
观察:该问题类似于“单位距离图的拉姆齐型问题”。对于平面上的任意有限点集,我们是否知道在某些假设条件下,二染色时总会出现单色单位距离?事实上,当两种颜色时,平面上的单位距离图满足R(2) = 4?等等,已知平面上的“Hadwiger–Nelson问题”涉及用不同颜色对平面着色以避免单位距离,即平面上的“色数”问题。但那是关于为所有点着色并避免任意两个点之间存在单位距离,不涉及二染色。
我们的问题是不同的:我们希望对点(整个圆盘)进行二染色,使得存在一个特定的距离d,作为不可避免的单色距离。
该问题与“Gallai定理”和“Van der Waerden定理”有关,这些定理处理的是整数区间内的距离问题。对于连续区域,可能存在相关结论。
也许答案与两个半径为 d/2 的圆盘在半径为 1 的圆盘内相交的方式有关。或者在矩形内部染色并避免某段距离的已知结论?
也许最简单的方法是考虑某点周围的 d-环:如果我们取任意一点 x,那么距离 x 恰好为 d 的点的集合构成一个圆(半径为 d)。如果该圆位于 D 内,那么当我们染色时,根据鸽巢原理,至少有两个圆上的点是同色的?实际上,我们需要的是圆上的两个点,它们之间的距离恰好为 d(即弦长为 d)。如果圆的半径是 d,那么同一圆上任意两点之间的距离最多为 2d,但不一定等于 d。
更好的思路是:采用构造避免特定距离 d 的染色方法。对于给定的 d,我们需要将圆盘划分为两种颜色,使得任意两个同色的点之间的距离都不等于 d。这类似于图染色问题:是否定义图 G_d,其顶点是圆盘中的点,边连接所有距离为 d 的点对?但我们要求是距离恰好等于 d,而不是小于等于 d。
因此,我们寻找一个图染色,其中相邻的两个点不能具有相同颜色。这等价于用 2 种颜色对无限距离图 G_d 进行正常的顶点染色。是否存在 2-染色,取决于图 G_d 是否是二分图。然而,G_d 无限且未必是二分图:它包含许多边。但我们是否总能用两种颜色对圆盘进行染色,使得没有两个距离为 d 的点同色?这本质上就是这些点的距离-d 图的色数问题:如果这些点可以被划分为两个子集,使得每个子集内都不包含距离为 d 的点对,则该图是 2-可染色的。这等价于:距离-d 图是二分图。
但要记住,点是连续统,我们可以在几何上进行任意划分。
给定点集 D,我们可以定义“禁止距离的超图”:我们希望避免任何同色点对之间的距离为 d。
一种方法是:使用一种在一组平行线上交替染色的模式,这些线之间的距离选择得当,使得同一颜色类的任意两点之间的距离都不等于 d。例如,将 D 划分为半平面(或条带),使得每个条带的宽度小于 d/2?但这并不能保证条带内不存在距离为 d 的点对。
另一种方法:使用“格点方法”:选择 D 的一个三角晶格子集,优先用红色染色,然后用距离 d 的点约束进行移位。
考虑到点的无限性,也许我们总能以某种周期性模式进行染色,从而对任意小于 √3 的距离 d 避免该距离?实际上是否存在已知结论:在用两种颜色对平面进行染色时,保证存在单色距离为 1 的最小距离?那可能是 d = 1 吗?事实上,由于平面具有“Hadwiger–Nelson 问题”中单位距离图的 2-染色特性,我们无法对平面进行 2-染色而不出现单色单位距离;已知平面的色数至少为 4,最多为 7。因此,仅用 2 种颜色对平面进行染色以避免单色单位距离是不可能的。所以对于平面而言,任意 2-染色必然包含单色的单位距离 d=1。但对于单位圆盘(一个有界区域),或许可以避免单位距离。然而我们需要考虑所有 d 值的整个连续统。
但这个问题关注的是除了避免单色距离 d 以外的任意染色方式。因此对于给定 d,我们需要判断是否可以染色以避免该距离。对于 d = 1,是否可能用两种颜色为单位圆盘染色且不出现单色单位距离?答案可能是肯定的:例如,将所有距离某中心点小于 0.5 的点染成红色,其余染成蓝色;此时任意两个红点之间的距离小于 1,任意两个蓝点之间的距离可能大于 1?不一定。是否存在两个距离恰好为 1 的蓝点?我们需要确保不存在任何两个蓝色点之间的距离恰好为 1。但由于蓝色区域是连续的且包含边界上的点,其中可能存在距离为 1 的点对。由于区域是连续的,难以完全避免。
但对于较小的 d,也许可以通过细分区域来避免:例如使用同心环带。思考一下:如果 d 很小,可以将 D 划分为宽度小于 d/2 的环带(annuli),并将相邻环带交替染色。这样,任意两个同色点要么位于同一环带内(且距离可能小于 d),要么位于不相邻的环带中(距离可能大于 d)。然而,同一环带内的点可能相距较远(例如靠近相对两侧的外环上两点最大距离约为 2),是否可能恰好等于 d?尽管很多距离会大于 d,但我们必须确保没有任何两点之间的距离恰好为 d。由于点集是连续的,或许可以实现这一点。
或者,也许对于任意 d < √3 都存在唯一明确定义的上界?嗯。
让我们尝试查找已知结论:这是用两种颜色对单位圆盘染色时的“Erdos 距离问题”吗?也可能被称为‘Steinhaus 问题’?或者是“在平面上针对两色的 Gallai 型距离问题”?有一个已知结果:对于平面上的任意二染色,存在单色距离为1的点对。事实上,已知平面的“拉姆齐数”对于距离1是无限的?等等,已知的结论是:对于正整数n,平面二色下的最小单色对距离是另一个问题。我们将回顾已知结果。
但注意:平面(无限平面)是否能用两种颜色染色以避免出现单色单位距离?我认为不能,因为平面内单位距离图的色数至少为4,这意味着任何 3-染色都会出现单色单位距离,但该结论不适用于 2-染色。实际上,平面的色数是指对平面上的点染色时,保证具有相同颜色的点之间没有距离为1的情况所需的最少颜色数。这个数至少为4,至多为7。因此,仅使用2种颜色无法避免单色单位距离,必然会出现距离为1的单色点对。也就是说,对于无限平面,d=1 是不可避免的。然而,对于单位圆盘这种有界区域,或许可以通过边界处理来避免单位距离。但真的可以避免吗?如果整个平面都无法避免,那么任何有界区域是否也必然存在?未必如此,因为我们或许可以利用区域形状的有界性来规避某些距离。
但也许我们可以基于已知结果对 d=1 构造一个反例:对于单位圆盘,可以考虑将点按极径小于1的染成红色,其余染成蓝色;但所有点都在圆盘内,因此不存在“外部”点。需要两种不同的颜色类:或许选择一个没有任意两点距离为1的小子集,将其染成红色,其余所有点染成蓝色。但此时蓝色点集就是整个圆盘除去该子集,这可能无法避免距离为1的点对。
或者,也许我们可以设计一种基于规则的着色方式,直接禁止距离为1的点对:例如,将所有 x 坐标为有理数的点染成红色,其余染成蓝色。在每一类中,可能存在许多距离为1的点对。
我认为,对于像单位圆盘这样的区域,任何二着色都会产生单色距离1。不过我并不完全确定。
让我们回顾已知结论:Hadwiger–Nelson 问题指出,平面不能被划分为两种颜色,使得每种颜色类都是“无单位距离”的。这是一个已知事实:平面的“色数”大于2,即至少需要四种颜色才能保证任意两个距离为1的点对颜色不同。因此,当使用两种颜色时,必然存在某种单色的距离为1的点对。这适用于整个平面。由于单位圆盘是平面的子集,任何对整个平面的着色限制在圆盘上也会产生单色距离1。但这里我们考虑的是仅针对圆盘内部的任意着色,而非平面的任意着色。然而,如果我们能找到一种对圆盘的着色方式,使其避免出现单色的单位距离,那么我们就可以通过周期延拓或无界延拓,将这种模式推广到整个平面?可能无法做到这一点,但也许我们可以在圆盘上避免,而在更大的区域中则不能。
但已知结果是:平面的色数大于 2。也就是说,任何对平面的二着色都会产生单色的单位距离。这一结论的证明通常依赖于有限构型(例如“莫泽纺锤图”),该构型是平面的一个单位距离图,其色数为 4。莫泽纺锤图是一个特定的单位距离图(即所有边长均为 1),需要 4 种颜色才能避免单色边。在任意二着色中,至少有一条边会成为单色边,即其端点颜色相同,从而形成一个单色的单位距离点对。因此,平面上的任何二着色都包含单色的单位距离点对。然而,莫泽纺锤图是否可以完全放置在单位圆盘内?让我们验证一下:莫泽纺锤图由两个菱形结构组成,其整体尺度可能可以缩放,但我们能否将其比例调整为适合单位圆盘的大小?该图包含 7 个顶点及若干距离为 1 的边。通过适当缩放,该图完全可能嵌入到单位圆盘内。但莫泽纺锤图是否要求整体最小尺度使得所有点都位于某个半径为 R 的圆盘内?当边长为 1 时,图的直径大约为 3,可能无法放入单位圆盘。但我们可以按比例缩小:该构造是基于单位边的,但可以将其缩放为边长变为 d 的形式,此时图完全适合放入某个半径的圆盘中?问题在于:最小的缩放比例是多少?如果我们按因子 s 缩放整个图,则所有距离都乘以 s。存在单位距离等价于存在长度为 d 的单色边。因此,我们需要嵌入一个所有边长恰好为 d 的图(类似于莫泽纺锤图),使其位于单位圆盘内。然后,在任意二着色下,是否至少有一对顶点颜色相同?实际上,莫泽纺锤图是一个单位距离图,其色数为 4:仅用 3 种颜色都无法避免单色边,因此用 2 种颜色时必然产生单色边。这意味着:用二着色为图的顶点着色时,必然会出现一条单色边(两个端点颜色相同)。因此结论是:对于任意二着色,存在单色的距离 d(即单色的边)。
因此,只要能在单位圆盘内嵌入一个需要不少于 4 种颜色的边长为 d 的图,就可以保证任何二着色都会产生单色的距离 d。问题于是转化为:在单位圆盘内,最大可嵌入的、边长为 d 且色数大于 2 的图是什么(即其边长可在 [0,2] 内任意选择)?实际上,我们可以直接考虑原图:边长为 1 的莫泽纺锤图是平面上的单位距离图,其边长为固定值 1。但对于任意边长 L,我们可以将图缩放至该边长。问题是:能否将一个边长为 d 的莫泽纺锤图嵌入单位圆盘内?当 d 足够小时可以:将整个图按因子 d 缩放后,可放入某一半径为 R×d 的圆盘中,其中 R 是原始图在边长为 1 时的半径。因此,条件变为:d 必须满足缩放后的图能完全放入单位圆盘内,即图的半径乘以 d 必须 ≤1。于是最大的 d 可表示为 1 /(莫泽纺锤图在原始尺度下的半径)。
因此,d 的上界可能等于(莫泽纺锤图的最小半径)的倒数?实际上,我们希望找到最大的 d,使得缩放后的莫泽纺锤图仍能完全放入单位圆盘内。当 d 更大时,无法满足条件(无法嵌入),此时我们或许可以通过其他染色方式避免单色距离 d;而当 d 更小(或等于该值)时,嵌入是可行的,从而确保了单色距离 d 的必然存在。
但问题是关于上界:即必然存在单色距离 d 的最大 d 值。如果上述推理成立,答案可能是基于莫泽纺锤图的某个最大 d 值。
另外,是否存在关于凸形在 2-着色下的“Hadwiger–Nelson 问题”的已知结论?对于圆盘,其“色数”可能小于 4。对于一个有界区域,有可能用 3 种颜色为其着色而不产生单位距离。事实上,若干凸形区域的色数已知为 4,但关于圆盘的具体情况尚不明确。然而,本题关注的是 2-着色下保证出现单色距离的问题。
让我们系统性地思考。
我们想要找的上界可能等于 d = 1。因为已知整个平面上的任意两色着色都会产生单色距离 1。但也许在单位圆盘中存在某种两色着色方式,能够避免单色距离 1。如果存在的话,那么该上界可能会小于 1。
我们可以尝试构造一种避免距离 1 的着色方案。方法之一是:考虑所有坐标均为有理数的点,将其染成红色?但这并不能保证避免距离 1 的情况。
另一种方法是基于最近整数格点来分配颜色:定义一个单位正方形(或六边形)的周期性平铺,使得相同颜色的点至少相距 1 以上。例如,将整个平面划分为边长为 1/2 的正方形,并以棋盘模式着色,使得相同颜色的正方形彼此不相邻。于是,任意同色点之间的最小距离至少为 1(若正方形对角放置,斜向距离为 √2/2)。但实际上,两个位于同色不同正方形中的点,其间距离可能小于 1。因此这种方法不能保证避免出现距离 1 的单色点对。
更好的方法:采用六边形密铺,将点按六边形晶格分配颜色,使得任意两个同色点之间的距离至少是某个值。
但我们仍需避免距离恰好为1的情况。避免某一特定距离的最简单方法是确保同色点集中不包含任何相距该距离的点对。对于每个红色点,我们可以“屏蔽”其周围距离为1的圆周区域,使其不包含其他红点。但在区域上实现全局着色且保持可扩展性是困难的。
不过,或许我们可以在单位圆盘内避免距离为1的情况,因为该区域有界,我们能够为每个点指定一种取决于其极角模2π/3的颜色?等等,这里需要引入“单位距离图”和“色数”的概念。单位圆盘的“色数”是指:若要求同色点之间距离不能恰好为1,则对圆盘进行着色所需的最少颜色数。这个数值至少为2,也许恰好是2?如果我们能用两种颜色为单位圆盘着色,使得任意两个红点之间的距离都不恰好为1,蓝点同理,那么d=1就不再是不可避免的距离。这将是关键。
单位圆盘的色数究竟是4?还是已知的其他数值?实际上,针对限制在单位距离图内的单位圆盘,存在相关研究结果:我认为其单位距离图的色数可能为4。但我们需要验证。
不过,回忆起一个已知结论:平面上的单位距离图需要4种颜色(已知下界为4)。这意味着存在有限点集构成的单位距离图,其色数为4。事实上,Moser纺锤体图正是一个此类单位距离图,其色数为4,并且如果我们能够调整该图使其适配,则它可嵌入平面上的任意大圆盘中。为了使图形适配单位圆盘,我们可以将其缩小。
由Moser纺锤体图可知,对平面上的任意2-着色,必然存在单色的单位距离点对。由于单位圆盘是平面的一个子集,在圆盘内部进行2-着色时,我们可能会遇到不包含整个Moser纺锤体图的着色方案;我们可以以不同方式对圆盘内的点进行着色,从而规避Moser纺锤体图成为单色图的情况?等等,Moser纺锤体图是一个单位距离图:如果将整个平面2-着色,是否必然存在某个Moser纺锤体图是单色的?实际上,2-着色会产生单色的单位距离点对,但该点对未必属于某个特定的Moser纺锤体图。每个点被赋予红色或蓝色的着色方案,均等价于对所有点的一种2-着色。由于平面的其色数大于2,任何2-着色都会产生某种单色的单位距离点对,但该点对可能不属于某个指定的Moser纺锤体图。
现在,如果我们将着色限制在单位圆盘内,那么可能需要考虑那些被包含在圆盘内的整个平面上的着色方案;但我们也可能采用其他的着色方式。然而,任何对单位圆盘D的着色都可以扩展为对整个平面(或一个更大的圆盘)的着色,例如通过任意方式对外部区域进行着色。这样做的结果是否仍然避免了在D内部出现单色的单位距离点对?但至少在D内部的单位距离点对会被避免。如果在整个平面上存在一种避免单色单位距离点对的着色方式,那么其在D上的限制也将避免单色单位距离点对。而平面上的结论指出,这样的着色方式并不存在。但我们能否将平面上的着色方式“限制”在对单位圆盘的着色上呢?实际上,平面上的结论是:没有任何一种对平面的2-着色能够避免单色单位距离点对。因此,任何对平面的着色都会在平面中某处(可能在圆盘外)出现单色的单位距离点对。但我们可能拥有一种着色方式,它能在单位圆盘内部避免单色单位距离点对,但在其他地方无法避免。因此,平面上的着色结果并不能直接保证在圆盘内部必然存在单色距离点对。
因此,Moser纺锤体的论证并不能直接保证在单位圆盘内部存在单色的单位距离点对。但我们仍可以考虑一种缩放后的Moser纺锤体,将其放置在任何一种二着色方案下的单位圆盘内部。由于着色是在整个圆盘上任意定义的,该图上的顶点具有某种颜色。如果Moser纺锤体图本身需要4种颜色,那么任何2-着色是否必然会在其某条边上产生单色的点对?等等,Moser纺锤体图的色数为4:它至少需要4种颜色才能正常着色(即相邻顶点颜色不同)。但这并不能直接保证在任意2-着色下(相邻点允许同色)都会出现单色的边。实际上,考虑一个具有色数k的图:若仅用k-1种颜色对其顶点进行着色,则必然存在至少一条边的两个端点被赋予相同颜色(即单色边)。例如,一个三角形(C₃)的色数为3;若仅用2种颜色对其着色,则必然会出现一条单色的边。类似地,Moser纺锤体图的色数为4;若仅用2种颜色进行着色,就必然会出现单色的边。不过这一点并非无需证明,需要进一步论证:色数为k意味着无法用k-1种颜色实现正常着色,但这仅表示在k-1种颜色下必然存在正常着色的冲突。而这并不一定意味着会出现单色的边:正常着色要求相邻顶点颜色不同;由于颜色数不足,无法避免某些相邻顶点被赋予相同颜色,而这恰好意味着会出现单色的边。是的,因此任何使用少于色数种颜色对图进行的着色,都必然会产生至少一条单色的边。由于Moser纺锤体图的色数为4,任何2-着色都会产生一条单色的边(即单色的单位距离点对)。因此,只要我们能将Moser纺锤体图嵌入单位圆盘中(即找到一组位于单位圆盘内的点,使得所有距离为d的点对恰好构成该图的边),那么任何避免单色距离d的着色都必须为图的顶点指定颜色,但这将导致一条单色边的出现,与假设矛盾。因此,任何避免单色距离d的着色都不可能存在,也就是说d是不可避免的。
因此,使用Moser纺锤体图时,使得d不可避免的条件是:可以将Moser纺锤体图按比例缩放以适应单位圆盘。
因此,问题转化为:最大的缩放因子d,使得存在一组位于单位圆盘内、所有边长均为d的点,且这些点中不存在单色点对。Moser纺锤体图具有7个顶点和11条单位长度的边。该图的直径(任意两个顶点之间的最大距离)是某个常数。如果我们将该图按比例s缩放,则所有边长变为s,直径也按s缩放。因此,为了使其完全包含在单位圆盘内,我们需要s乘以其原始直径不超过2(即缩放后图形的直径不超过单位圆盘的直径,也就是2)。实际上,圆盘的直径为2(从-1到1)。因此条件是:缩放后的图形必须完全包含在半径为1的圆盘内(即圆盘内任意两点间最大距离≤2)。所以我们需要s × 原始直径 ≤ 2。那么s的最大可能值为2 / 原始直径。
但我们希望找到最大的边长d(即s),使得该图形可以被放置在其中。因此d_max = 2 / 原始直径。
因此,我们需要知道Moser纺锤体图在边长为1时的原始直径。让我们回顾几何结构。
Moser纺锤体是由两个共享一个顶点的菱形构成的单位距离图,每个菱形由两个边长为1且夹角为60度的等边三角形组成?实际上,该构造使用菱形锐角为60度、边长为1,其对角线长度分别为1和√3?但需要具体细节。
最好回顾一下图示:Moser纺锤体可以通过取一个单位等边三角形开始,将其关于一边反射,然后加上其他一些部分而构建。它具有7个顶点和11条边。其中一个顶点作为枢纽。该图形可被描述为两个“Golomb尺”之类的结构。
让我们检查尺寸:该图可以放置在一个半径约为√3/2的圆内?或者,图形中任意两个顶点之间的最大距离大约为√3?实际上,考虑嵌入方式:该图可以放置在一个7×7的单位正方形网格上?不确定。
更好的方式是回忆已知事实:Moser纺锤体是一个平面单位距离图,其色数为4。它可以被画在一个半径约为1.5的圆内?但我们需要确切的尺寸。让我们查找或推导一下。
或者,可能存在一个已知的“Hadwiger–Nelson问题”上界:当缩放至边长为1时,用于证明低于4所需的最小圆的半径大约是R=……?有一段已知内容:“Moser纺锤体的半径约为0.5?” 实际上,Moser纺锤体的构造是否使得任意两个顶点之间的距离最多为√3?等等,考虑由边长为1且夹角为60°的两个等边三角形构成的菱形:该菱形的顶点位于(0,0)、(1,0)、(1/2,√3/2)、(3/2,√3/2)。实际上,这只是一个菱形?逐步构建:从一个等边三角形开始,顶点为(0,0)、(1,0)、(1/2, √3/2)。将其关于边(1,0)-(1/2,√3/2)作反射?不完全正确。
让我们回忆一下:Moser纺锤体可以被放置在一个大小为3×2的矩形内?或者该图形可以放入一个大小为2×2的矩形中。
最好直接获取确切的坐标。我知道原始边长为1时,Moser纺锤体可以放入一个宽度为√3、高度为1.5的矩形中吗?让我们确认一下。
实际上,让我们找一个可靠的来源:这似乎是一个已知的问题:用红色和蓝色对单位圆盘进行着色,并找到最大的d,使得必然存在一个单色的点对距离为d。答案是sqrt(2)?或者也许是sqrt(3)?但我们需要通过构造显着色方案来验证。
我们需要找到一种对单位圆盘的二着色方案,以避免出现单色距离d。这种方法可能涉及用不同颜色对相对的两个半球进行着色,或许可以使用某种特定形状。
也许答案是 1(或者可能是 sqrt(2) 之类)。我们尝试一些简单的 d 值:
- d = 2(直径):在任意着色中,必然存在一个距离恰好为 2(即直径两端)的单色点对吗?不一定:如果我们将中心对面的所有对径点涂成相反颜色,或许可以避免?实际上,对于圆盘上的任意一点,其对径点都存在。我们可以定义一种着色方式:如果某点的角度 (θ) 满足 sin(θ) > 0,则涂成红色,否则涂成蓝色。但可能存在大量对径点对具有相同颜色。不过,也许我们可以设计一种着色方式使得没有单色对径点对:将每个点 x 指定颜色为 c(x) = 红色当且仅当 x 位于某个距离原点半径为 1 的上半部分?但我们必须确保任意一对距离为 2 的点(即对径点对)颜色不同。这等价于在对径映射 x → -x 下的正常着色问题。对于一个圆盘,对径映射是一个对合映射,它将任意点与其对点配对。如果我们能为每一对对径点分配相反颜色,那么就可以避免距离为 2 的单色点对。这是否可行?我们只需定义 c(x) 为某种在对径下翻转的函数。例如,当 x 的非负角度坐标 θ ∈ [0, π) 时设为红色,当 θ ∈ [π, 2π) 时设为蓝色。但 -x 对应的角度是 θ + π mod 2π,如果 θ 属于 [0,π),则 θ+π 属于 [π, 2π)。因此它们颜色不同。所以确实,这种“上半部分与下半部分”的对角着色法可以避免出现距离为 2 的单色点对:任意两点对径,一个在“上半部分”(θ ∈ [0,π) → 红色),另一个在“下半部分”(蓝色)。但需要注意的是,原点的对点是其自身(距离为 0)。对径点对仅存在于半径为 1 的圆上。在圆盘内部,距离恰好为 2 的点唯一存在于边界上相对的两点。因此,为避免距离为 2 的情况,我们只需确保边界圆上的点着色使每对对径点颜色不同。我们描述的着色方案可以实现这一点:根据角度是否在 [0,π) 或 [π,2π) 来分配颜色。然而,位于边界上的内部点可能与另一个内部点构成距离为 2 的点对吗?在圆盘内,距离为 2 的点唯一的可能是位于直径两端的一对点;因此它们必须在边界上。所以我们只需处理边界点。因此我们可以避免距离为 2。
因此 d = 2 不是不可避免的。
那 d = sqrt(3) 呢?能否避免距离为 sqrt(3) 的情况?可能可以。
这个上界可能类似于 1/sqrt(3) 之类的值。
让我们思考一个已知结论:对于单位圆盘,拉姆齐距离 d 大约是 1/φ?不确定。
更好的方法:使用有限配置:对于任意二着色,我们可以保证存在一个单色的等边三角形吗?并不完全是这样。
经典的“Gallai定理”指出,对于平面上的任意有限着色,是否一定存在一对具有相同颜色的点,在任意给定方向上也具有相同的距离?我不确定。
让我们查找已知结果:“单位圆盘中任意二着色下的单色距离”。可能是一个已知问题:单位圆盘二着色时不可避免的最大距离大约是0.5?有可能。
另一种可能是,该上界由“Borsuk-Ulam定理”推导而来:对于任意从单位圆盘到{0,1}的连续函数,存在一对对径点(距离为2),使得f(x) = f(-x)。实际上Borsuk-Ulam定理指出:任何从S^n到R^n的连续映射都存在一对对径点映射到同一点。对于圆盘到{0,1}的情况虽然不连续,但具有离散性。然而,存在组合版本:对于将S^{n-1}边界任意二着色,是否存在一对对径点共享同一颜色。这是“火腿三明治定理”还是“Borsuk-Ulam”?事实上存在一个已知结论:对于S^2边界上的任意二着色,存在一对对径点颜色相同。但此处的着色定义在整个圆盘内部。而我们只关心圆盘内部距离为2的点对。根据边界仅使用两种颜色的Borsuk-Ulam定理,边界上必然存在一对对径点颜色相同。然而,我们是否可以根据内部区域选择性地为边界着色?让我们思考一下:球面S^2的边界情况是关于球面的,而不是圆盘。但存在一个组合定理:R^n中单位球面的任意二着色都包含一对单色的对径点。这对于R^n中的连续映射是否成立?Borsuk-Ulam是连续的,但我们面对的是一个离散的着色问题。然而存在一个“Borsuk-Ulam型”的离散版本:对于球面的任意二着色,总存在一对对径点颜色相同。这是真的吗?可能不成立:可以考虑将球面的一半任意着色为红色,另一半为蓝色(类似于赤道上的半球),使得每对对径点都被分配相反颜色(一个红色,一个蓝色)。这种着色会产生没有任何单色对径点对的情况。但这是否是球面的合法着色?它是不连续的,但在离散的着色问题中是允许的:每个点被分配一种颜色,无其他限制。因此我们可以通过在半空间使用一种颜色、其补集使用另一种颜色来避免距离为2的单色点对。因此Borsuk-Ulam在这里不直接适用,因为它要求映射是连续的。
因此对于距离d=2,该性质并不普遍成立:存在避免该情况的着色方式。所以d=2不是。
那么d>2呢?在单位圆盘内部不可能,因为最大距离为2。因此d必须≤2。
我们希望找到最大的d<2,使得任意二着色都必然包含一个单色的距离d点对。也就是说,我们想要找到最大的不可避免距离。
一种方法是考虑缩放后的“Moser纺锤体”:它能保证任何用二着色的此类图都会产生单色的距离d。Moser纺锤体顶点之间的最大距离是某个值(记为D₀)。如果我们按因子s = d进行缩放,则新图的直径为s×D₀。为了使该图能放入单位圆盘(直径为2)中,需要满足s×D₀ ≤ 2,即s ≤ 2/D₀。因此d的最大值至多为2/D₀。那么由Moser纺锤体保证的不可避免性是否适用于所有d ≤ 2/D₀?实际上,对于给定的d,我们能嵌入一个Moser纺锤体(所有边长为d)。如果缩放因子小于或等于2/D₀,则该图可以放入单位圆盘中。对于任何避免单色距离d的着色,都会对应于该图的一个顶点正常着色,而该图至少需要4种颜色,这在2-着色下是不可能的。因此,任何2-着色都必须包含一个单色的距离d。因此,对于任意d ≤ 2/D₀,这种方式都能保证必然性。因此上界至少为2/D₀。
但Moser纺锤体可能并非最优;可能存在更大的图,能够嵌入更大的d值。因此,d的上确界可能大于2/D₀。
另一种方法是考虑使用“Golomb尺”或“单位距离图”。
更好的方法是:问题要求的是使得该性质普遍成立的最大 d 值。因此,我们需要找出所有存在某种着色方式能避开单色距离 d 的 d 的集合的上确界;该上确界即为临界阈值。
于是问题转化为:对于哪些距离 d,存在一种对单位圆盘 D 的二着色,使得不存在距离为 d 的单色点对?使得这种着色方式存在的所有 d 的集合的上确界即为所求的“上界”。
因此,我们需要找出最大的可回避距离。
于是问题转化为:确定最大的 d,使得我们可以在单位圆盘内用两种颜色对点进行着色,同时避免出现距离为 d 的单色点对。
这类似于某个距离图的“拉姆齐型数”。已知相关结果为“平面上的欧几里得拉姆齐理论”:对于任意有限着色,平面上存在单色的相似拷贝。但此处我们仅限于两种颜色和一个特定的距离。
我们的目标是:寻找最大的 d,使得距离-d 图(边连接所有相距恰好为 d 的点对)对单位圆盘具有大于 2 的“拉姆齐数”。
另一种可能是,考虑在距离-d 图的补图背景下,单位圆盘被划分为两个集合的“色数”;即我们希望将点划分为两个集合,使得每个集合都不包含距离为 d 的点对。等价于构造一个图,其中顶点为点的集合,若距离为 d 则连边;我们需要将该图正常地二着色,即图是二分的。而我们需要确保该图不能用两种颜色进行正常着色:对于某些 d,单位圆盘内的距离-d 图是不可二分的,即包含奇圈。通常,一个图是二分图当且仅当它不包含奇数长度的环。对于距离-d 图,可能存在奇数长度的环(例如等边三角形),但当边长 d 等于等边三角形的边长时,三角形的顶点处会出现距离为 d 的边。若 d 是等边三角形的边长(即构成等边三角形),则存在由三个点组成的三元环(两两距离为 d),在该三元环上的任何正常着色至少需要 3 种颜色;因此 2-着色必然产生单色的边。因此,d 成为不可避免的距离的原因之一是:能在单位圆盘内嵌入一个边长为 d 的等边三角形。事实上,只要单位圆盘包含边长为 d 的等边三角形,那么任何 2-着色都会在该三角形顶点中产生两个同色点,而它们之间的距离为 d。因此,若能在单位圆盘内嵌入边长为 d 的等边三角形,则 d 是不可避免的。在更大构型中的情形也类似。
因此,我们可能会猜测,最大的不可避免距离就是能够在单位圆盘内嵌入等边三角形的边长的最大值。由于等边三角形是最简单的奇圈(三元环),它的出现会强制产生单色边。所以该上界至少是能够在单位圆盘内嵌入的最大等边三角形的边长。单位圆盘内能容纳的最大等边三角形是顶点位于圆盘边界上的内接等边三角形。若该单位圆盘的半径为1,则内接于半径为1的圆中的等边三角形边长为√3(因为中心角为120°,弦长 = 2R × sin(θ/2) = 2 × 1 × sin(60°) = 2 × (√3/2) = √3)。因此,单位圆盘内能容纳的最大等边三角形边长为√3。
现在,如果我们设 d = √3,是否总能在圆盘内嵌入一个边长为 √3 的等边三角形?是的,根据定义就可以实现。因此,任意一种对圆盘的二染色是否必然包含一对距离为 √3 的单色点?来看一个满足 d = √3 的构型:考虑一个内接于圆盘边界、顶点位于圆周的等边三角形。若将三角形顶点染成红色或蓝色,根据鸽巢原理,至少有两个顶点同色,而它们之间的距离为 √3。因此,任何对这三个点的染色都会产生一对距离为 √3 的同色点。然而,染色是针对整个圆盘的,而不仅仅是这三个点;如果这些点被染成不同颜色,染色结果也不仅限于这三个点。但这三个点只是整个区域的三个特定点,染色必须对每一单独点赋予某种颜色,没有其他限制。由于只有两种颜色,三个点中必有两个共享同一种颜色,且它们之间的距离为 √3。因此,任何对圆盘的染色都会产生一对距离为 √3 的同色点。这是一个简单的鸽巢原理应用。
因此,d = √3 是不可避免的,是所有染色方案中必然出现的距离。
但 d > √3 是否也不可避免呢?可能并不是,因为对于某些距离,我们或许可以避免出现单色点对。
例如,考虑 d = 1.9。是否可能避免?或许我们可以将相对的两个点染成不同颜色;但可能存在其他点对在距离为 1.9 时颜色相同。但也许存在某种巧妙的染色方式能够避免这种情况。
但等边三角形在小于等于√3的范围内给出了一个简单且较低的界限:对于任意d ≤ √3的情况,我们是否也能保证存在一个边长为d的等边三角形?实际上,对于任意d ≤ √3,我们都可以在圆盘内嵌入一个边长为d的等边三角形:只需取一个边长为d、中心在0点的小三角形即可;但能否将其完全放入半径为1的圆盘中?当d ≤ √3时,边长为d的等边三角形的高度为d×√3/2 ≤ √3×√3/2 = 3/2 = 1.5。由于圆盘半径为1,对应的高度为1.5,大于半径,可能无法被完全包含?等等,边长为d的等边三角形的外接圆半径为R_t = d / √3。实际上,对于等边三角形,外接圆半径 = d / √3,内切圆半径 = d/(2√3)。因此,若要将三角形放入单位圆盘中,需要其外接圆半径 ≤ 1(以确保所有顶点都在圆盘内)⇔ d ≤ √3。因此,确实任何d ≤ √3都是可行的,因为我们可将三角形的中心置于圆盘中心,此时顶点位于距离中心d/√3处 ≤ 1。因此,所有这样的边长d都是可实现的。
因此,对于任意d ≤ √3,我们都能嵌入一个等边三角形。因此,任何二着色都会产生一对距离为d的单色点,因为该三角形的顶点中存在同色点对。实际上需要注意:三角形的三个顶点位于圆盘内。而着色是任意的,三个带有颜色的点中,两种颜色根据鸽巢原理必有一种至少出现两次。因此,确实存在一对同色点,其距离为d。因此,d ≤ √3是不可避免的。
因此,界限至少是√3。那么大于√3的d值是否不是不可避免的呢?当d > √3时,我们无法在圆盘内嵌入一个边长为d的等边三角形,因为圆盘无法容纳这样的三角形。因此仅使用三角形是不够的。
但是否存在其他奇圈结构能在更大的d值下强制出现距离?也许我们可以嵌入其他边长为d的奇圈,例如边长为d的正五边形?但对角线距离是另一个值。对于奇圈,我们需要一组点,使得其中某些点对之间的距离为d(即图是一组点对之间距离为d的环)。一个环C_n具有边(v_i, v_{i+1}),距离为d,以及可能的弦。为了强制出现单色的距离d,我们需要一组点,使得无论何种着色都会产生一对距离为d的同色点。这可以通过n个点来实现,其中某些点对之间的距离为d,使得任何二着色都会有一对单色的距离d点对。这本质上是针对距离图的拉姆齐数:在n个顶点上、距离d的完全图的拉姆齐数为R(K_2, K_2)=2,但这并不重要。实际上我们需要的是:对于任意一个n个点的着色,都存在一对同色点,它们之间的距离为d。这等价于说边集E = {距离为d的点对}在完全图K_n中的拉姆齐数为2?等等,标准拉姆齐理论指出:对K_n的边进行着色时,我们可以保证某种结构的出现。但这里我们面对的是一个固定图(距离图),其顶点是点集,我们希望保证一条单色边(即两个同色顶点由一条边连接)。在二着色下,我们实际上是将每个顶点分配为红色或蓝色;边是否为单色边取决于其两个端点是否颜色相同。而这正是对顶点进行图着色的问题:我们希望用两种颜色对顶点进行着色,且不出现单色边,这对应于图的一个正常着色。因此,若一个图存在正常二着色(即它是二分图),则存在一个不含单色边的二着色;否则,任何二着色都会产生单色边。因此,其条件是该图不是二分图(即包含奇圈)。所以,任何包含奇圈(奇数长度的环)的图都不能被二着色而不产生单色边。对于我们的目的而言,我们需要一个可以嵌入圆盘内的、边长为d的奇圈图(即一系列点,形成一条路径,其中每个点与其两个邻居之间的距离为d,并且第一个点与最后一个点形成一个奇圈)。最简单的奇圈是三角形(等边三角形)。其他可能的奇圈包括五边形(正五边形),其中相邻顶点之间的距离为d,但不一定所有点对之间的距离都是d。图C5的边仅存在于相邻顶点之间,非相邻顶点之间的弦距离不同,但那些不是距离图的边。因此,对于距离图而言,我们有一组点,其中某些点对(环上的边)之间的距离为d。如果我们能嵌入一个边长为d的C5,则根据奇偶性,图的色数为3?实际上,任何奇圈都需要3种颜色来进行点正常着色,因为它们是二分图(圈是奇圈,不可二分;其色数为3)。因此,任何对顶点(点)的二着色都会在圈上的五对相邻顶点(距离为d)中至少产生一对同色点。等等,是这样的吗:对C5的顶点进行二着色时,是否能避免单色边?实际上,如果不能二着色,就会产生单色边。在二分图中,可通过交替颜色(如红、蓝、红、蓝……)进行二着色。但对于奇圈,由于无法一致地交替颜色(因为会回到起点),奇偶性冲突会导致某条边的两个端点颜色相同。因此,确实任何对奇圈的二着色都会至少产生一条单色边。所以,对于任意奇圈构型,都必然存在单色距离d。因此,我们无需依赖三角形:任何长度为奇数的环(即环上的点对间距离d构成的环)就足够了。
因此,对于更大的 d,我们可以考虑正五边形:如果能在圆盘内嵌入边长为 d 的正五边形,那么任何二着色都会在五边形的相邻顶点间(距离为 d)产生一对同色顶点。因此 d 是不可避免的。边长为 d 的正五边形必须能放入单位圆盘中;即其外接圆半径 ≤ 1。对于边长为 s 的正五边形,其外接圆半径 R_p 的公式为:R_p = s / (2 sin(π/5))。实际上,中心角为 72°;弦长 s = 2R sin(π/5)。因此 R = s / (2 sin(π/5))。于是,s ≤ 2 sin(π/5) ≈ 2 × sin(36°) ≈ 2 × 0.5878 = 1.1756。因此要完全放置在单位圆盘中,需要满足 s ≤ 1.1756。这意味着大于约 1.176 的 d 无法通过五边形实现。因此五边形给出的界限最多约为 1.176。但已经小于 √3 ≈ 1.732。所以三角形更为严格。
但或许我们可以使用不规则的奇环,将点放置得相距较远以容纳更大的边长。然而,三角形中任意三个点之间的最大距离可能大于任何奇环中相邻顶点间的距离?实际上我们需要的是每个相邻顶点之间的距离恰好为 d,而弧上其他点对之间的距离则不需要考虑。
因此,最大边长(相邻距离)可能受限于环上顶点之间的直径(最大间距)。对于奇环,存在一种构型,使得顶点可以位于一个较小的区域内,但它们之间的弦长必须恰好为 d。连续顶点之间的距离必须恰好为 d,但非连续顶点可能更近或更远。对于一个采用“路径”嵌入的奇环,我们可以在环路中连续放置边长为 d 的边,可能以 d 为步长形成一条简单的链,最终回到起点,此时两端点之间因共线也可能相距 d?实际上,将一个奇环嵌入具有欧氏距离的几何结构时,我们必须放置点 p₁, p₂, ..., pₙ,使得对所有 i 都有 |pᵢ - pᵢ₊₁| = d(下标模 n)。这要求经过一个奇数长度的闭合路径后回到起点。当 n 为奇数时,向量位移的总和必须为零(闭合路径)。对于一组长度为 d 的向量,若将其首尾相连成一个环,要精确闭合,必须存在这样的配置。
将边长相等的奇环嵌入平面是有限制的。对于等边三角形(n=3),可以构成一个闭合的等边三角形。对于 n=5,长度为 d 的五边形各边向量之和为零。这对正五边形是可能的。对于任意大于等于 3 的奇数 n,也都存在长度为 d 的正 n 边形:将所有顶点放在半径为 R = d / (2 sin(π/n)) 的圆上。因此边长 d = 2R sin(π/n)。要在单位圆盘(R ≤ 1)内容纳边长为 d 的正 n 边形(奇数 n),需要 d ≤ 2 sin(π/n)。当 n 增大时,sin(π/n) ~ π/n(较小),因此最大可能的 d 随 n→∞ 趋近于 0。所以三角形(n=3)在奇环中给出了最大的可能边长 √3:实际上,对于 n=3,正三角形的边长 s = 2R sin(π/3) = 2R × (√3/2) = R√3。当 R=1 时,s=√3,得到 √3 ≈ 1.732,大于任何 n>3 时的 2 sin(π/n):当 n=5 时,2 sin(π/5) ≈ 1.176;当 n=7 时,2 sin(π/7) ≈ 0.868。因此,在奇环中,等边三角形给出了最大的边长。所以等边三角形是在单位圆盘内能产生不可避免距离的最小奇环。
因此,√3 是由最小奇环(三角形)所能得到的上界。然而,可能存在非奇环结构的其他构型,能在更大的距离 d 上强制产生单色点,例如从 n=5 的拉姆齐数 R(2,2) 得出的“奇数个点”?实际上我们需要的是单位距离图的“拉姆齐型”结论:对于圆盘的任意二着色,必然存在一个单色的距离 d 点对。这等价于说单位圆盘上的距离-d 图不是 2-可染的(即色数 >2)。也就是说,该图不能是二分图。图的非二分性可能是由于存在奇环(如三角形)。是否存在不含奇环但色数仍大于 2 的图?对于一般图,存在色数 >2 但不含奇环(即无奇环)的情况,例如具有奇围长的图(高围长)且色数为 4 的已知图(如 Grötzsch 定理?不,Grötzsch 定理指出无三角形的平面图是 3-可染的,而非 4-可染)。但我们是否需要 4-色平面图?一般图的色数可能大于 2 但不含短奇环,尽管在平面图中任何色数 >3 的图都必须包含奇环?实际上,“四色定理”指出平面图是 4-可染的,但也存在 4-色且不含三角形的平面图(例如 Grötzsch 定理指出无三角形的平面图是 3-可染的)。因此,任何 4-色平面图必须包含三角形。但我们可能只关心距离-d 图是否为平面图?不一定。
但对于依赖特定距离的图,可能存在莫泽尔纺锤体这样的色数为 4 的构型,它是否也包含三角形?来看一下:Moser 纺锤体是单位距离图,其色数为 4,但它是否包含三角形?我认为它不含三角形(它是 4-色单位距离图中节点数最少的图)。实际上,Moser 纺锤体确实不包含三角形。它是一个不含三角形的单位距离图。因此,非二分性可能由更复杂的构型导致。
因此我们或许可以改进上界:可能存在大于 √3 的 d 值,通过 Moser 纺锤体的嵌入使得距离 d 不可避免。由于 Moser 纺锤体是 4-色的,任何二着色都会产生一个单色的距离 d(即它的一条边)。因此,如果我们能将其嵌入单位圆盘中,且边长为 d,则该距离将大于 √3(可能达到某个其他数值)。所以我们需要确定可以嵌入单位圆盘的最大 d 值。
因此答案可能是 sup d = 2 / D₀,其中 D₀ 是单位边长 Moser 纺锤体的直径(最大顶点间距)。我们来估算 D₀。
回忆一下:Moser 纺锤体由两个在一点相交的菱形构成。该图形大约可放入一个 2×1 的矩形中。我们查找其尺寸。
最好获取 Moser 纺锤体的确切坐标。我记得一些坐标:对于单位边长 1,各点如下:
设点:
- A = (0,0)
- B = (1,0)
- C = (1/2, √3/2) (构成边长为 1 的等边三角形 ABC)
- D = (3/2, √3/2) (因此 AB = 1,BC = 1,AD = 1?实际上需要验证)。
菱形 A-B-C-D,其中边长为1,且角为60°。这构成一个类似“钻石”形状:点A在(0,0),B在(1,0),C在(1/2, √3/2),D在(-1/2, √3/2)?等等,也许是这样。我们来构建一个锐角为60°、边长为1的菱形。这样的菱形可以看作是两个共享一条边的等边三角形。坐标:一个等边三角形的顶点为(0,0)、(1,0)、(1/2, √3/2)。将该三角形关于边(1,0)-(1/2, √3/2)反射?那会得到点(1,0) + (1/2, √3/2) - (0,0) =?实际上,关于三角形的一条边进行反射会生成菱形,但或许更简单的方法是定义菱形的四个顶点为:A = (0,0),B = (1,0),C = (1 + cos 60°, sin 60°) = (1 + 1/2, √3/2) = (3/2, √3/2),D = (cos 60°, sin 60°) = (1/2, √3/2)。因此,菱形的顶点为(0,0)、(1,0)、(3/2, √3/2)、(1/2, √3/2)。这是一个平行四边形(菱形),边长为1吗?检查边长:AB = 1(显然)。BC:从(1,0)到(3/2, √3/2):向量为(1/2, √3/2),长度为√((1/2)^2 + (√3/2)^2) = √(1/4 + 3/4) = √1 = 1。CD:从(3/2, √3/2)到(1/2, √3/2):向量为(-1, 0),长度为1。DA:从(1/2, √3/2)到(0,0):向量为(-1/2, -√3/2),长度为1。所以是的,这是一个菱形。其对角线:从(0,0)到(3/2, √3/2)的长对角线长度为√((3/2)^2 + (√3/2)^2) = √(9/4 + 3/4) = √(12/4) = √3 ≈ 1.732。短对角线从(1,0)到(1/2, √3/2):向量为(-1/2, √3/2),长度为1。因此对角线长度分别为1和√3。
现在考虑Moser纺锤体:它由两个共享一个顶点(可能是该顶点)的此类菱形构成。该图有7个顶点:A、B、C、D、E、F、G?来看一下:Moser纺锤体是通过取两个菱形并将其在某一顶点粘合而成的单位距离图,可能还添加了额外的边。
根据已知描述:Moser纺锤体可以通过取两个菱形ABCD和AEFG来构造(可能如此),并将它们放置成共享顶点A,使得B、D、E、G之间的距离也均为1?大概是这样。
或者,Moser纺锤体可以通过取两个等边三角形并使它们的顶点相互距离为1来构成,其中还包含其他一些边。
最好查一下确切的Moser纺锤体。我们可以尝试获取相关URL。使用工具吗?目前无法主动获取URL,除非用户明确请求,尽管我们可以假设一个已知的参考来源。但我们可能允许根据要求获取明确给定的URL。然而,我们不能假设用户拥有此类资源。我们仍然可以依赖于我们的知识。
让我们从已知的文献中查找Moser纺锤体的坐标。我回忆起在此上下文中使用过的一个坐标集合:设a = √3/2 ≈ 0.866025。
定义以下点:
- P1 = (0, 0)
- P2 = (1, 0)
- P3 = (1/2, √3/2) (构成等边三角形)
- P4 = (3/2, √3/2)
- P5 = (2, 0)
- P6 = (5/2, √3/2)
- P7 = (3, 0)
但这不是一个 Moser 纺锤体;它可能是其他结构。然而,Moser 纺锤体使用 7 个点,边长均为 1,位于一个相对较小的区域内。在边长为 1 的情况下,其外接半径可能约为 2。
我可以尝试推算其尺寸:文献中给出的 Moser 纺锤体直径约为 3?让我们回忆一下:Moser 纺锤体的尺寸约为一个 2 × 3 的矩形?不确定。
最好快速查阅可靠的资料以确认。使用工具获取“Moser spindle dimensions”页面。
Fetch URLs
1 pages
Think
该工具返回了失败信息(可能是被阻止了)。我们可以尝试通过搜索来获取结果。
Search
largest distance between vertices Moser spindle 38 results
Moser纺锤体几何直径最小坐标
搜索结果显示Moser纺锤体图的直径为2(图论中的距离,即任意两个顶点之间通过边数计算的最短路径长度)。但我们关注的是嵌入平面时的几何直径(任意两个顶点之间的最大欧几里得距离)。
Sage中的“直径”指的是图的路径距离(边数),而非欧几里得距离。从片段中得知:“半径为2,直径为2,围长为3”,这里指的是图的通常定义。
我们还需要Moser纺锤体作为单位距离图在原始尺度(边长为1)下的几何直径。这是一个需要推导的度量。
我们需要找到一组坐标,使得所有单位距离约束得以满足,并且最大欧几里得距离(任意两个顶点之间的最大距离)最小化。
现在寻找一个能提供坐标的资料来源。搜索“Moser纺锤体 坐标”。
Search
Moser spindle coordinates unit distance graph 42 results
Moser纺锤体顶点度与坐标分析
搜索结果提供了关于 Moser 纺锤体构造的描述,但未给出坐标。不过我们可以推断其坐标。
根据 Moser 纺锤体的构造描述:两个菱形(菱形)具有 60° 和 120° 的内角,即锐角为 60°、钝角为 120° 的菱形。菱形的边长为单位长度(1)。每个菱形的短对角线长度也为 1(因其连接两个锐角顶点,形成一个等边三角形)。实际上,若锐角为 60°,则菱形实际上由两个等边三角形组成,由一个角连接到对角的短对角线也是单位长度(短对角线长度 = 边长 × √(2 - 2 cos θ),其中 θ 为锐角?对于具有锐角 60° 的菱形,短对角线确实等于边长)。对于边长为 1、锐角为 60° 的菱形,其几何结构相当于两个共用一条边的等边三角形。短对角线连接两个锐角顶点,跨越钝角?实际上该菱形类似于 60°-120° 的菱形形状。短对角线(连接两个锐角顶点)长度应为边长 × √3?我们来计算一下:对于菱形,边长为 s,锐角为 θ,短对角线 d1 = s × √(2 - 2 cos θ)(连接锐角顶点)。当 θ = 60° 时,cos θ = 1/2,因此 d1 = s × √(2 - 2×(1/2)) = √(2 - 1) = √1 = 1。因此短对角线确实具有单位长度。长对角线长度 d2 = s × √(2 + 2 cos θ) = √(2 + 1) = √3 ≈ 1.732。因此菱形的形状如上所述。
Moser 纺锤体由两个这样的菱形共享一个锐角顶点构成。两个顶点(每个菱形的另一个锐角顶点)之间的距离为单位长度(1)。本质上,我们有两个菱形共享一个顶点(枢纽)。另外两个锐角顶点之间的距离也为 1。所形成的图在单位距离约束下具有 7 个顶点,除共享的枢纽顶点外,每个菱形的顶点度均为 3?实际上每个枢纽与其他顶点的连接数可能也是如此。
因此,在嵌入单位长度的边时,图形中任意两个顶点之间的最大距离由两个处于两端的非锐角顶点(即两个钝角顶点)之间的距离决定。这个距离可能会更大。
让我们为边长为 1 的 Moser 纺锤体建立坐标系。存在已知的嵌入方式:选择坐标:
- 令 O = (0,0),作为共享的锐角顶点。
- 将第一个菱形放置时,使得对角顶点位于 (1,0)(钝角方向?)。实际上我们需要生成一个锐角为 60°、边长为 1 的菱形。选择方向使得 O 位于锐角顶点之一。锐角是相对的两角;我们具有内角分别为 60°(锐角)和 120°(钝角)的菱形。该菱形可描述为点:O = (0,0);A = (1,0)(如果我们将一边沿 x 轴方向放置)。然后下一个顶点,即对角顶点(与 O 相对)的距离为长对角线长度 sqrt(3),方向与 O A 成 60°?让我们进行正确计算。
构造一个边长为 1 且一个锐角位于 O 的菱形。令 O 在 (0,0)。令 OA 是沿 x 轴方向的一条边,终点 A = (1,0)。现在,锐角为 60°,因此 OA 与从 O 到另一顶点(记为 B)的下一条边之间的夹角为 60°。由于菱形的所有边长均为 1,B = (cos 60°, sin 60°) = (1/2, √3/2)。那么第四个顶点 C = A + (B - O) = (1 + 1/2, 0 + √3/2) = (3/2, √3/2)。该菱形的顶点为 O (0,0)、A (1,0)、C (3/2, √3/2)、B (1/2, √3/2)。锐角位于 O 和 C(角度为 60°),钝角位于 A 和 B(角度为 120°)。实际上,O 和 C 处的角度为 60°,A 和 B 处的角度为 120°。是的。
现在第二个菱形与 O 共享一个锐角(与第一个菱形相同的顶点 O),但方向不同。稍后再确定其方向。两个菱形共享顶点 O(公共的锐角顶点)。另一个锐角顶点 D 和 E 是第二个菱形的对角顶点。两个锐角顶点(非 O 点)之间的距离也必须为 1。
因此,对于第二个菱形,我们需要在 O 处插入一条长度为 1 的边,与 OX 成 60° 角,其中 X 是第二个菱形的下一个顶点(类似于第一个菱形中的 A)。第一个点既可以是 (1,0),也可以是其他方向上的单位向量。实际上,第二个菱形也可能有一条与 OX 成 60° 角的边。O 处的锐角为 60°,因此从 O 出发的两条边也与 OX 成 60° 角。
但我们必须放置第二个菱形,使得另一个锐角顶点(对角顶点)与第一个菱形的对角顶点(C)之间的距离为 1?等等,描述是:“两个菱形共享一个锐角;剩下的两个锐角顶点之间距离为 1。” 我们来解析一下:两个菱形共享一个锐角顶点(即整个图形的中心顶点),而两个未共享的锐角顶点(即每个菱形中不与枢轴相对的锐角顶点)之间的距离也为 1。
因此,在第一个菱形中我们有锐角顶点 O(枢轴)和对角顶点 C。在第二个菱形中我们有两个锐角顶点:O(枢轴)和另一个点,记为 F(第二个菱形的对角顶点)。条件是:C 与 F(两个对角顶点)之间的距离 = 1。
因此我们得到一个图:边包括构成每个菱形的所有单位边(8 条边),加上连接每个锐角与其对角顶点的短对角线(2 条短对角线)——等等,菱形的短对角线是连接两个锐角顶点的线段(即在 O 和 C 之间?)实际上,在菱形中,短对角线连接的是两个锐角顶点(在 O 和 C 之间)。这正是该菱形的一条对角线。在长菱形几何结构中,O 到 C 的长对角线长度为 √3。但我们之前提到连接锐角顶点的对角线是短对角线?重新计算一下:对于锐角为 60°、边长为 1 的菱形,锐角是对面的角,它们之间的距离更长?实际上,锐角是较小的角度,连接这两个角的线段穿过菱形内部,是较长的对角线,因为菱形在锐角方向更“尖”?我们来计算一下:从 O (0,0) 到 C (3/2, √3/2):距离为 √((3/2)² + (√3/2)²) = √(9/4 + 3/4) = √(12/4) = √3 ≈ 1.732。这是更长的对角线。从 A (1,0) 到 B (1/2, √3/2) 的短对角线距离为 1。因此短对角线连接的是钝角顶点(较大的角)。所以锐角顶点 O 和 C 之间的对角线长度为 √3,而不是单位长度。
因此文献中所述的“短对角线”指的是连接锐角顶点的短对角线?实际上他们说:“菱形的边和短对角线在菱形内部构成等边三角形。” 我们来分析一下:在菱形中,每条边是单位长度。短对角线是否是长度为 1 的线段?实际上,在锐角为 60° 的菱形中,短对角线连接的是两个钝角顶点,其长度等于边长(为1)。短对角线与菱形的边共同构成等边三角形:确实,短对角线AB(连接两个钝角顶点)加上两条与其相连的边,形成边长为1的等边三角形。
因此每个菱形产生两条短对角线?实际上每个菱形只有一条长度为1的短对角线(即连接两个钝角顶点的那条)。另一条对角线较长,长度为√3。但我们之前所说每侧有两条短对角线,可能只是同一条对角线?在Moser纺锤体中共有11条边:8条菱形边(每个菱形有4条边,共8条),2条短对角线(每个菱形各一条),再加上连接两个锐角顶点的一条额外边(连接两个不同菱形锐角顶点之间的单位长度的边)。总共是8 + 2 + 1 = 11条边,正确。
因此每个菱形只有一条短对角线(连接其两个钝角顶点)。在第一个菱形中,钝角顶点是A(1,0)和B(1/2, √3/2),所以短对角线为A-B,长度为1。同样地,在第二个菱形中,也存在一条长度为1的短对角线,连接它的两个钝角顶点。
现在开始嵌入这两个菱形:每个菱形内的所有边长均为1。两个菱形共享一个锐角顶点O(枢轴)。在第一个菱形中,另一个锐角顶点C位于距离O为√3的位置。在第二个菱形中,另一个锐角顶点F同样位于距离O为√3的位置。C与F之间的距离必须为1(这两个锐角顶点之间的单位长度边)。因此O、C、F三者之间的边长均为单位长度:O-C = √3,O-F = √3,C-F = 1。实际上O到C和O到F是边长为√3的对角线,但我们规定这些对角线长度也应为√3(因为它们不是图的边)。然而,图仅包含长度为1的边(单位距离)。O与C之间没有边(因为这条对角线长度大于1),这不是图的一部分。与O关联的边仅为构成两个小菱形的边:即OA、OB(每个菱形都有类似A、B的钝角顶点),以及第二个菱形中的OD、OE。这些边均为单位长度。因此O是一个度为6的顶点?实际上O与每个菱形的两个钝角顶点和两个锐角顶点相连?等等,O是一个锐角顶点,因此O通过菱形的边分别连接到其两个钝角顶点。在每个菱形中,O与两个钝角顶点相邻,并通过对角线(长对角线)与对角的锐角顶点相连?实际上O到对角的锐角顶点是一条对角线,其长度大于1,不是单位边,因此不构成长度为1的图边。因此O不与对角的锐角顶点相邻。所以O仅通过菱形的边连接到每个菱形的两个钝角顶点(共四个顶点)。但每个菱形共享顶点O,因此O连接到每个菱形的两个顶点,总共四个邻接顶点(因为两个菱形不同)。但Moser纺锤体中顶点的度可能是3?实际上Moser纺锤体是一种平面单位距离图,其中每个顶点的度为3或4。我们来检查以下性质。
Moser纺锤体共有7个顶点,其中一个顶点可能度为4?让我们在脑海中查看Sage中的典型嵌入:其坐标可能是:
- O = (0,0)(锐角公共顶点)
- A = (1,0)
- B = (1/2, √3/2)
- C = (3/2, √3/2)
- D = (cos θ, sin θ),可能如此
- 等等。
让我们找到一个明确的坐标列表。
搜索“Moser 纺锤体坐标列表”。
Search
"Moser spindle" unit distance coordinates 26 results
避免1.8距离单色点对的两色染色
搜索结果展示了该结构,但没有给出明确坐标。然而,我们可以基于几何推理推导出坐标。Moser 纺锤体可以通过两个角度相差 60° 的菱形构造而成。或许可以通过欧几里得几何方法进行计算。
但也许我们可以避免确定精确的最大距离,因为答案可能已知为 √3。让我们思考一下:由等边三角形(或等边三角形三联体)是否能保证任意二染色都会产生单色点对,且最大距离为 √3?实际上,三角形的保证距离可以是内接于圆盘的任意等边三角形的边长。最大边长为 √3(内接于单位圆的三角形)。因此 d = √3 是不可避免的。那么 d > √3 的情况如何?是否会出现某个距离仍然不可避免?以 d = 1.8 < 2 为例。我们能否避免单色距离为 1.8 的点对?可能的方法是:基于点的极坐标角度模 180° 进行染色?等等,我们之前已经构造过避开单色距离为 2 点对的染色方式。对于略小于 2 的 d,也许也可以避免。但也许 √3 并不是上确界;也许我们可以在略大于 √3 的 d 下避免,但不会太大。
另一种可能是该界限是 φ,例如黄金比例?让我们查阅文献中关于凸形或圆盘在 2-染色下的“单色距离”问题。有一个已知概念:“单位圆盘内距离的拉姆齐型结果”。也可能与“两色平面距离图”中所谓的“临界距离”有关。
搜索关键词:“单位圆盘的两色距离图”
Search
chromatic number of unit disk graph two colors 44 results
寻找可缩放的4色单位距离图
搜索结果没有直接帮助。
根据已有知识和推理,我们推测上界可能是 sqrt(3)。但需考虑是否存在能在 sqrt(3) 到 2 之间强制出现单色距离的构造。可能存在一种“二染色”,可避免超过 sqrt(3) 的任何距离出现单色点对。如果存在这样的染色方式,则上界就是 sqrt(3)。
但我们必须验证是否存在一种对单位圆盘的二染色,能够避免距离 d > sqrt(3) 出现单色点对。若存在,则说明 sqrt(3) 是最优上界。
我们需要考虑的是:对于圆盘内任意一对距离大于 sqrt(3) 的点,它们是否必须被赋予不同颜色?或者我们是否可以通过设计,使得所有距离恰好为 d 的点对都染成异色。
一种方法是:使用“棋盘式”染色,将交替的扇区染成红色或蓝色,每段角度为 60°。例如,根据点的极角 θ mod 60° 是否等于某个值来进行染色,可能需要偏移以避免特定距离。
但我们需要保证的是距离恰好为 d,而非小于等于 d。因此,我们需要建立一种映射关系,使得任意两个距离为 d 的点总是获得不同颜色。这类似于在距离图 G_d 上的正常染色问题。这类图的边对应距离为 d 的点对。因此,我们需要 G_d 的一个 2-染色方案(即正常染色)。条件是否能被满足,取决于该图的色数是否不超过 2。
因此,对于给定的 d,使得染色方案存在的条件是:当连接顶点的条件为“距离为 d”时,由圆盘内的点诱导出的单位距离图应为二分图。由于这些点是不可数集,我们需要寻找一种连续染色的构造方式,即能否为每个点分配颜色,使得任意两个距离为 d 的点颜色不同。这等价于圆盘内集合的距离图存在一个二分染色(即正常 2-染色)。
我们不能仅仅局限于有限图:该图是无限的。然而,也许图的二分性可归约为某个有限的子图,这个子图是一个“奇数长度的环”,会阻碍二分性的实现。如果该图包含任何无法 2-染色的有限奇环(三角形、五边形等),则无法对其进行二分染色。
因此,为了避免出现单色点对,该距离图必须具有二分性。所以我们需要研究距离图的奇环。
如果对于某些 d,距离图包含一个长度为 3(三角形)的奇环,则该图不是二分图,因此无法实现无单色边的 2-染色。对于长度为奇数的奇环同样如此。
因此,下界(最小阈值)可能是最大的距离 d,使得在圆盘内存在距离为 d 的奇环。那么,随着 d 增大,是否还能找到奇环?例如,当 d 大于某个值后,是否可能嵌入正五边形?但对于 d 大于 sqrt(3) 的情况,我们无法在该距离上嵌入正五边形(因为正五边形的外接圆半径必须 ≤1),但是否可能嵌入一种非正但边长为 d 的奇环?也许我们可以使用一条不闭合的折线形奇环,即通过一个各边长为 d 但方向不同且能闭合的闭合路径来形成奇环;这就像用长度为 d 的边构造一个正奇数边形,但其顶点不一定共圆。然而,在欧几里得几何中,一个长度为 n、边长为 d 的闭合多边形链的存在是有约束条件的。对于给定的边长 d,我们需要找到 n 个点 p_i,使得所有 |p_i - p_{i+1}| = d,且 |p_n - p_1| = d。这相当于一个“单位距离环”或“长度为奇数的多边形链”。
对于任意 d < 2,我们是否可以构造边长为 d 的正 n 边形?实际上,边长为 s 的正 n 边形可以内接于半径为 R = s / (2 sin(π/n)) 的圆中。因此,如果我们能放入一个半径为 R 的圆,则 d ≤ 2 sin(π/n)。当 n 增大时,该上界随 1/n 减小。因此,对于给定的 d,能作为单位距离图嵌入到单位圆盘中的最大奇整数 n 满足 d ≤ 2 sin(π/n)。反过来,对于给定的 d,我们可以找到满足 d ≤ 2 sin(π/n) 的最小奇数 n,此时可以嵌入具有该边长的正 n 边形。但更大的奇数 n 可能会使 2 sin(π/n) 过小。
因此,对于每个 d,我们可能在圆盘内嵌入某种长度的奇环。三角形的 d ≤ sqrt(3) 限制如上。对于五边形(奇数),d 必须 ≤ 2 sin(π/5) ≈ 1.1756(如前所述)。因此当 d > 1.1756 时,五边形无法放入。当 d > sqrt(3) ≈ 1.732 时,三角形无法放入。因此当 d > 1.732 时,不存在正奇环。虽然可能存在非正但奇数条边的奇环,但该奇环需满足不同的距离约束;存在长度为奇数、边长为 d 且闭合路径的约束条件更为复杂。
但也许对于任何大于 sqrt(3) 的 d,距离图可能是二分图(即可进行二染色)。让我们验证一下:如果 d > sqrt(3),则任何边长为 d 的内嵌等边三角形都无法放入,同样正五边形也无法放入。然而,仍然可能存在使用不规则形状的其他奇环。但也许所有边长为 d > sqrt(3) 的奇数边多边形都无法放置在单位圆盘内,这似乎是合理的,因为三个点之间两两距离为 d 的条件对 d 构成了很强的限制。对于三个点,条件仅仅是能嵌入一个边长为 d 的等边三角形。对于更多奇数个点,可行的距离限制可能更小。
但是否存在一种由 5 个点构成、边长为 d > sqrt(3) 的奇环?让我们分析一下约束条件。对于一个各边长度相等、边长为 s 的闭合多边形链,存在一个几何条件:如果所有内角相等(即正多边形),则当 s ≤ 2R sin(π/n) 时,半径为 R 的圆内可以容纳该多边形。如果多边形不规则,即使不共圆,某些边长可能会更大?但如果边长固定,多边形可以被“拉伸”,导致某些内角变小、另一些变大,但边长仍保持为 d。当 n=3 时,三角形是刚性的(仅形状固定,方向可变)。当 n=5 时,存在多种可能的形状:你可能有一个非凸的奇环。然而,一个 5 条边均为长度 d 的闭合路径仍能放入单位圆盘之内的条件是存在某种限制。
但也许存在一个已知结果:在单位圆盘内,单位距离图的最大边长,使得该图不是二分图(即包含奇环),这个最大值为 sqrt(3)。这是因为唯一长度最小的奇环是三角形;如果无法放入三角形,则任何其他单位距离图都可能是二分图。但我们需要验证:即使无法放入三角形,仍然可能存在非三角形的其他奇环;例如正五边形的边长上界更小;但是否存在不满足凸性的奇数环?可能存在一个边长为 d > sqrt(3) 的 5-环,但顶点不在同一圆周上;但你总可以通过弦使五边形具有更长的边长?让我们思考一下:对于一个 5 个顶点 (v1...v5) 的奇数环,每对相邻顶点之间的距离恰好为 d。如果这些点不在同一圆周上,可能存在某些非相邻顶点之间的距离小于 d,但这没有问题,因为这些点对不属于图的边。然而,需要将所有这些点放置在单位圆盘内。约束条件可能允许合理的边长:例如,你可以将点 v1 放在圆盘边界上的 (1,0) 处,然后从 v1 到 v2 画一条长度为 d 的弦至某个位于圆盘内部的点 v2,以此类推。然而,5 步之后必须回到起点。当 d 接近 2 时,你可能在直径上往返跳跃,但由于需要奇数步,这不可能实现。由于闭合条件,可能存在一些局限性。
也许这个界限是 sqrt(3)。但对于 d 在 sqrt(3) < d < 2 范围内,是否存在已知的单位圆盘双色染色可避免单色距离?我们可以尝试使用一种“交替的半圆扇区”染色方式:将圆盘划分为 6 个角度为 60° 的扇区,并根据扇区编号的奇偶性交替染色。那么对于距离 d > sqrt(3) 的情况,任意两个距离为 d 的点都会属于不同颜色的扇区?这并不一定成立。
更好的方法是:利用连续双色染色的“Borsuk-Ulam 定理”的概念?但该定理不适用于离散情况。
另一种思路是使用类似于“Hadwiger–Nelson 问题”的染色方法:为了避免单色距离 1,我们需要至少 4 种颜色。但对于更大的距离,或许可以仅用 2 种颜色实现避免?因为当距离足够大时,距离图会变得稀疏。
但这个问题具有对称性:在半径为 1 的圆盘内,任取一点 p。令 C(p) 表示距离 p 恰好为 d 的点的集合,这是一个以 p 为中心、半径为 d 的圆。如果该圆完全位于圆盘 D 内部,那么可能存在两种染色方式,使得该圆上的任意两点颜色不同?着色是针对整个圆盘的,我们需要保证该圆上不存在单色的点对?但实际上,我们只关心圆上某一对点是否被赋予相同颜色。圆的半径为 d,如果 d 较大(接近 2),这个圆可能很小且位于 D 外部。
但条件关乎任意两点之间的距离,而与方向无关。
或许我们可以考虑圆周上染色之间的“最大距离映射”。对于固定的 d,D 中每个点 x 可以确定 y(x) = x + 向量 v,使得 |v| = d(模去旋转)。实际上,存在许多可能的 y,但我们只需避免存在两个同色的点恰好相距 d 的情况。
一种避免该条件的方法是采用一种“无距离 d”的染色方式:为每个点分配一种颜色,使得距离为 d 的两个点颜色不同。这相当于构造一个图,其中当两点距离为 d 时连边,我们需要得到这个无限图的一个正常二染色。这正是 2-染色意义上的正常图染色问题。该图具有偶围长(即为二分图)是一个必要条件。如果这个图不包含奇圈,则可能是二分图。当 d 较小时,该图包含奇圈(例如三角形)。当 d 较大时,也许就不存在奇圈。
因此问题转化为:对于哪些 d,半径为 1 的圆盘内的距离-d 图是二分图?当 d ≤ √3 时,我们可以嵌入等边三角形(奇圈)=> 图包含三角形 => 不是二分图 => 任何染色都会出现单色距离。当 d > √3 时,可能无法构成等边三角形。但是否存在其他类型的奇圈?我们能否嵌入正五边形?如前所述,当 d > 2 sin(π/5) ≈ 1.1756 时无法嵌入。因此在 d > 1.1756 时,五边形不存在。因此当 d > √3(约 1.732)时,五边形也无法成立。因此可能除了三角形外,没有其他奇圈可以嵌入。但是否存在非正但仍具有等边长度的奇圈?例如,一组 5 个点,其中某些顶点之间的距离不必等于边长,但我们仍需存在一个包含 5 个顶点的子图,其边恰好是 5-圈中的边。这本质上是将 5-圈嵌入为几何图。长度为 d 的 5-圈的嵌入条件等价于寻找一个闭合的 5 段折线,每段长度均为 d。对于给定的 d,其存在性可能是有界的。
我认为已有结论:在单位球面上,欧几里得距离图的色数为 4(?),但单位圆盘可能有所不同。
不妨搜索“chromatic number of a disk of radius 1 with distance d”。但或许已存在已知结论:将圆盘二染色后,确保存在单色距离为 d 的点对,这类距离的上确界是 √3。这似乎是合理的。
但我们仍需验证是否能够对大于 √3 的距离避免单色点对。让我们尝试为 d ∈ (√3, 2) 构造一种染色方式。
一种思路是:将圆盘划分为宽度为 w < d/2 的等距平行条带(水平方向)。将连续的条带交替染成红色和蓝色。那么同一颜色的任意两个点之间的距离要么小于 w(如果在同一矩形内),要么大于某些距离(如果在相隔较远的条带中)。然而,可能存在位于不同条带中的点,它们之间的距离恰好为 d 且颜色相同。如果我们选择 w 使得任意两个同色点之间的距离都不是 d。如果条带宽度为 w 且交替着色,则任何距离为 d 的点对可能属于不同颜色的条带,但也可能恰好属于相同颜色的条带。
或者,也许我们可以基于径向坐标为点着色(例如根据半径是否在某个区间内将其分为红色或蓝色),但是否存在两个距离恰好为 d 的同色点?有可能:位于环带内对称位置的两个点可能相距 d。
一种更好的方法:利用“距离图是二分图”这一概念,因为我们可以通过相对于某条直线定义一个奇函数来将区域划分为两个集合。
考虑使用到原点的距离来定义着色:定义 f(p) = 红色,当 ||p|| < 0.5;否则为蓝色。那么任意两个红色点之间的距离 < 1(因为每个点最多距离原点 0.5,因此红色点之间的最大距离是 1)。实际上最坏情况是红色点位于以 0.5 为半径的小圆盘边界上相对的两点:距离 = 1。因此红色点之间可能出现距离为 1 的点对(如果两点都在半径 0.5 的圆上相对,则距离可能为 1)。但我们可以通过限制该内部圆盘的半径,使其小于 0.5,从而确保红色点之间的最大距离小于 1。然而,我们仍需要考虑所有距离;避免特定距离 d 的着色可能会更复杂。
但也许我们可以通过根据某点对的距离取模来定义着色,从而为任意 d 构造一种着色方式:将所有点染成红色,仅除了那些在距离 d 上具有给定“伙伴”的点?但我们必须为每个点都不止一次地分配颜色。
也许我们可以采用连续的方法:为每个点 p 定义关于方向 d 的“模 2 距离函数”。由于距离是实数,我们需要避免的是那些恰好等于 d 的情况。如果我们通过某种翻转方式根据模 d 的值来定义着色,就可以避免距离为 d 的单色点对。
一种方法是:使用无限单位距离图的正常二着色能否由一个势函数给出:对每个点,定义其颜色由 ⌊x / d⌋ 的奇偶性决定,其中 x 是某一固定方向投影的坐标。对于任意两个相距为 d 的点,由于位移改变了坐标值 d,其投影坐标值 x 一定相差整数倍,即发生 +d 或 -d 的偏移。因此,⌊x/d⌋ 的差值将为奇数?实际上,如果点对具有固定的距离 d,那么某些方向上的投影差绝对值将在 [−d, d] 范围内。但如果我们将 x 坐标以某个与 d 不可通约的值(例如 mod d)来定义颜色,则可能得到同色或异色。
如果考虑颜色依赖于某个线性泛函模 d 的值,而 d 与该线性方向正交的情况,这可能会有帮助。
更具体地说:定义颜色为 f(p) = 红色,当 ⌊α·p⌋ mod 2 = 0;否则为蓝色,其中 α 是一个向量(例如单位向量)。对于任意两个距离为 d 的点 p 和 q,α·(p − q) 的值可能很小;但差 α·p − α·q 的取值范围取决于方向。对于任意方向 α,点积最大可达 d(当两点方向与 α 平行时)。于是(点积)的模 d 值可能变化 0 或 ±?但能否保证其奇偶性翻转?然而这种方法并不精确。
另一种正弦模式着色:基于 floor(k * x) mod 2 的字典序分配颜色,其中 x 是相对于某个方向的坐标。若适当地选择 k,则对于任意两个距离为 d 的点 p 和 q,当距离恰好为 d 时,k·(p − q) 可能整除该方向上的投影差;但此方式仍不够稳健。
也许我们可以采用基于“距离为 d 的图是二分图”以及“区域本身也是二分图”的已知着色方案:因为圆盘是否关于绕某点旋转角度为 θ 的变换构成二分图?并非如此。
更好:使用图论结论:平面上的单位距离图对于任意距离 d(即图是无限的)已知色数至少为 4?但需要查证已知结论:平面上的“距离-d 图”是否与“单位距离图”相同,只是将距离缩放为 d?实际上,对于任何 d > 0,距离 d 的图与单位距离图是同构的,只需按比例缩放即可。因此所有距离图都是相似的(缩放即可)。因此,若将整个平面按比例 1/d 缩放,则距离 d 图就是单位距离图。因此,已知单位距离图在距离为 1 时具有不小于 4 的色数结论,那么在缩放后是否意味着在所有距离下都需要至少 4 种颜色?实际上,若将整个平面的所有点按比例 1/d 缩放,则距离变换为:原平面上距离为 d 的点对在新平面上变为单位距离。因此,若平面仅用 3 种颜色着色就能避免单色单位距离,则将整个平面按比例 d 缩放后也能得到仅用 3 种颜色避免单色距离 d 的着色。然而已知单位距离图的色数至少为 4,意味着无法用 3 种颜色避免单色单位距离。那么是否也不可能用 3 种颜色避免单色距离 d?实际上,单位距离图的 4 种颜色结论表明:任何对平面的 3 着色都会产生一对距离为 1 的单色点。
因此,对于任意 d > 0,任何对平面的 3 着色都会产生一对单色点,其距离恰好为 d?但这里缩放并不直接成立,因为缩放的是点集本身,而非着色。如果整个平面以比例 1/d 缩放,则距离为 d 的任意点对在新平面上变为单位距离。因此,任何对原平面的着色可以视为按相同规则(即 f'(x) = f(dx),其中 f 是原平面的着色)定义的缩放后平面的着色。那么,若原着色避免了距离 d 的单色点对,缩放后的着色是否会避免单位距离的单色点对?等等:若在原始平面中,对所有距离为 d 的点 p, q 满足 f(p) ≠ f(q),则定义新平面上的着色 f'(y) = f(dy)。当两点在单位距离下(即 |y - y'| = 1)时,对应原始点 |dy - dy'| = d,因此它们颜色不同。这意味着 f' 在平面上避免了单色单位距离。但这是不可能的(平面色数 ≥4),因此这样的 f 不存在。于是,任何对平面的 3 着色(甚至 2 着色?)都会产生单色距离 d。等等,我们需要的是 2 着色而非 3 着色。单位距离图的已知结论是:至少需要 4 种颜色才能避免出现距离为 1 的单色点对,即其 4 色性。因此使用 3 种颜色不足以避免单色单位距离;但使用 2 种颜色更不可能。因此对于任意 d,任何 2 着色都会产生单色距离 d?但该论证使用的是 3 着色;我们或许能对所有 d 用 2 种颜色避免单色距离?然而单位距离图的 4 种颜色下界仅表明至少需要 4 种颜色才能避免出现单色单位距离,并未对 2 种颜色给出正面结论?实际上,至少需要 4 种颜色意味着 2 种颜色肯定不够,即无法用 2 种颜色避免单色单位距离。因此对于 d = 1,任何 2 着色都会包含一对单色单位距离点。
对于其他 d(通过缩放)同样成立:由于我们可以将平面整体缩放,使其在新尺度下单位距离对应原平面上的距离 d。但缩放改变的是点的位置,而非着色方式本身。然而,对原始平面的着色可以基于坐标定义:在缩放后的平面上,点 x 的颜色定义为 f(d*x),其中 f 是原始着色。如果在原始平面上着色能避免出现距离 d 的单色点对,则缩放后的所有单位距离点对(对应原始距离 d)颜色也不同。因此我们将得到平面的一个无单色单位距离的 2 着色,这与已知结果矛盾(除非原着色使用的颜色数 >2)。但原着色是 2 色的!这将与单位距离图至少需要 4 种颜色的结论矛盾。因此这样的 f 不可能存在。因此,对于任意 d > 0,任何对平面的 2 着色都会产生单色距离 d 的点对(即距离-d 图无法 2-着色)。然而,这一结论与我们有界区域(圆盘)的条件不同:缩放可能将区域外的点带入圆盘内;不能保证缩放后的着色仍局限于单位圆盘内。实际上,我们仅对单位圆盘(半径 1)进行着色。单位距离图在平面上的 4 色结论适用于对整个平面着色(无限延展)。即使我们将着色限制在较小区域(如圆盘),只要着色仍使用 2 种颜色,着色结果仍是整个平面的一种 2 着色(尽管区域外未着色)。但我们能否以任意方式扩展圆盘外的着色?注意,整个平面的已知结果要求着色对所有点有定义。如果我们仅在单位圆盘内着色,可以任意定义圆盘外部分以避免距离 d 的单色点对,从而在圆盘内可能避免该距离。由于平面的 2 着色无法避免单位距离,这一结论不能推出圆盘内的具体结论。
因此需要更细致的分析。
因此,该界限可能正好是 sqrt(3)。我们尝试构造一种针对 d > sqrt(3) 的二色染色方案,以避免出现单色的 d-点对。如果成功,则答案为 sqrt(3)。如果不成功,则界限可能更大。
让我们思考一种针对 d 略大于 sqrt(3)(例如 1.8)的可能构造方式。我们能否将区域划分为两个集合,使得每个集合中不包含距离恰好为 d 的点对?也许可以采用基于距离原点半径的“交替环带”方法,设置适当的宽度,使得任意两个同色的点要么接近(距离 < d),要么相距较远,而相距较远的情况可能恰好等于 d。
但如果适当地选择间隔,间隔本身是离散的集合,并且环带之间的间距也可以被选取得使得环带内任意两点之间的距离不等于 d。
对于连续的几何区域,可能存在某种划分方式,使得每个颜色类构成“独立集”,即不存在距离为 d 的点对。这等价于用两种颜色对区域进行正常着色,使得每个颜色类都不包含距离为 d 的点对。如果这样的划分存在,则说明该距离是可以避免的。
存在一种称为“通过有理数对距离 d 回避距离”的方法:选取一个有理向量 r,使得平移 r 会导致距离恰好为 d?不确定。
或者,考虑“Moser 纺锤”,它表明当 d=1 时无法避免;但也许当 d 更大时,该图无法嵌入,因此该距离可能可以避免。
但或许存在另一个不同于等边三角形的图构型,使得 d 的上界更大。例如“Golomb 图”或其他单位距离图,其色数为 4,但可能具有更大的直径,从而允许更大的边长。也许存在一个 4-色的有限单位距离图,能够被缩放至任意大的边长。事实上,任何单位距离图都可以被缩放至任意边长;但单位圆盘的容纳能力会限制这种缩放。然而,也许存在一个不是三角形的 4-色单位距离图,其构型允许更大的边长嵌入单位圆盘中。Moser 纺锤体就是其中一个候选;但如果将其边长按某个因子 s > 1 缩放,我们或许仍能将其嵌入,直到某个最大的 s。Moser 纺锤体能够容纳的最大 d 受限于其嵌入在单位圆盘内的直径。
因此,我们需要计算单位边长 Moser 纺锤体在欧几里得空间中的直径。让我们计算这个值。
我们有带坐标的 Moser 纺锤体。我们来看看能否找到已知坐标。搜索“Moser 纺锤体 坐标”。
Search
Moser spindle coordinates points 16 results
计算 Moser 纺锤体欧几里得直径
arXiv 上的论文给出了嵌入双曲平面时的坐标,但非欧几里得几何;不过我们是否也能由此得到欧几里得几何中的坐标?所给数据是八元组;也许它们代表了平面坐标基础上的线性组合。
但或许我们可以通过更简单的方式避免求解这些坐标,也能计算出直径。
或许可以通过已知的几何方法来计算 Moser 纺锤体在欧几里得平面上的直径:该图形由两个菱形组成。我们来粗略计算一下这个图形。
两个菱形共享一个锐角 O。每个菱形的另外两个锐角顶点之间的距离为 1(这是另一个单位距离)。O 到每个锐角顶点的长对角线距离为 sqrt(3),正如我们之前推导的,因为 O 与对角的锐角顶点之间的距离等于菱形的对角线长度(长对角线)。事实上,在该菱形中,连接锐角顶点的对角线是长对角线,长度为 sqrt(3)。因此 O-C = sqrt(3) ≈ 1.732。同样,O-F = sqrt(3)。因此该图的最大距离很可能出现在两个对角的钝角顶点(距离较远)之间,或者出现在一个锐角顶点与一个非相邻的钝角顶点之间?让我们进一步探讨。
放置第一个菱形:O (0,0)。边:OA 沿 x 轴方向到点 A (1,0)。B 是从 O 出发 60° 方向的单位长度顶点:B = (1/2, sqrt(3)/2)。相对顶点 C = A + (B - O) = (3/2, sqrt(3)/2)。第二个菱形:从 O 出发,一边沿相对于 OA 的某个角度 phi 方向。为使两个菱形关于某条轴对称?已知有一种嵌入方式:第一个菱形的锐角位于 O,角度可能为 30° 并旋转?实际上 Moser 纺锤体具有一个四阶旋转对称轴。该图形可描述为两个菱形,其中一个相对于另一个旋转 90°?验证一下:该图形包含 7 个顶点:O 为公共顶点,第一个菱形的另外两个顶点是 (1,0) 和 (1/2, sqrt(3)/2);第二个菱形的顶点是可能从 -90° 方向达到的单位距离点?让我们查找标准坐标。
搜索“Moser 纺锤体在平面的嵌入坐标”。也许是“David Eppstein”等提供的已知坐标。
Search
"Moser spindle" coordinates" 0,0" "1,0" 11 results
单位圆盘二着色不可避免最大距离√3
搜索结果包含来自 Eppstein(或其他学者)关于表示 Moser 纺锤体的坐标代码。该代码片段列出了顶点 0 至 6 的坐标(即 Moser 纺锤体)。具体坐标如下:
顶点:
0: [0,0]
1: [1,0]
2: [(3 - sqrt(33))/12, (3sqrt(11) + sqrt(3))/12]
3: [(3 + sqrt(33))/12, (3sqrt(11) - sqrt(3))/12]
4: [(9 - sqrt(33))/12, (3sqrt(11) - sqrt(3))/12]
5: [(9 + sqrt(33))/12, (3sqrt(11) + sqrt(3))/12]
6: [0.5, sqrt(11)/2]
1: [1,0]
2: [(3 - sqrt(33))/12, (3sqrt(11) + sqrt(3))/12]
3: [(3 + sqrt(33))/12, (3sqrt(11) - sqrt(3))/12]
4: [(9 - sqrt(33))/12, (3sqrt(11) - sqrt(3))/12]
5: [(9 + sqrt(33))/12, (3sqrt(11) + sqrt(3))/12]
6: [0.5, sqrt(11)/2]
现在我们可以计算任意两个顶点之间的最大距离(欧几里得距离)。让我们用近似数值来进行计算。
我将手动计算距离吗?可能比较繁琐,但可以通过近似数值计算。
首先,需要 sqrt(33) 和 sqrt(11)。sqrt(33) ≈ 5.744562646538029,sqrt(11) ≈ 3.3166247903554,sqrt(3) ≈ 1.7320508075688772。
计算每个坐标:
定义:
v0 = (0, 0)
v1 = (1, 0)
v1 = (1, 0)
v2:x = (3 - sqrt(33))/12。先计算分子:3 - 5.7445626465 = -2.7445626465。除以 12 约等于 -0.228713553875。
x2 ≈ -0.2287135539。
y = (3sqrt(11) + sqrt(3))/12 = (33.31662479 + 1.73205080757)/12 = (9.94987437107 + 1.73205080757)/12 = 11.6819251786/12 = 0.97349376488。因此 v2 ≈ (-0.22871355, 0.97349376)。
x2 ≈ -0.2287135539。
y = (3sqrt(11) + sqrt(3))/12 = (33.31662479 + 1.73205080757)/12 = (9.94987437107 + 1.73205080757)/12 = 11.6819251786/12 = 0.97349376488。因此 v2 ≈ (-0.22871355, 0.97349376)。
v3:x = (3 + sqrt(33))/12 = (3 + 5.7445626465)/12 = 8.7445626465/12 ≈ 0.728713553875。y = (3*sqrt(11) - sqrt(3))/12 = (9.94987437107 - 1.73205080757)/12 = 8.2178235635/12 ≈ 0.6848186303。因此 v3 ≈ (0.72871355, 0.68481863)。
v4:x = (9 - sqrt(33))/12 = (9 - 5.7445626465)/12 = 3.2554373535/12 = 0.271286446125。y = 与 v3 相同:(3*sqrt(11) - sqrt(3))/12 ≈ 0.6848186303。因此 v4 ≈ (0.27128645, 0.68481863)。
v5:x = (9 + sqrt(33))/12 = (9 + 5.7445626465)/12 = 14.7445626465/12 = 1.228713553875。y = (3*sqrt(11) + sqrt(3))/12 ≈ 0.9734937649。因此 v5 ≈ (1.22871355, 0.97349376)。
v6:x = 0.5,y = sqrt(11)/2 = 3.31662479/2 = 1.658312395。因此 v6 ≈ (0.5, 1.6583124)。
现在计算任意两点之间的最大距离。
我们可以估算最远的点:v0 (0,0) 与 v5 (1.2287, 0.9735) 之间的距离 ≈ sqrt((1.2287)² + (0.9735)²) ≈ sqrt(1.5097 + 0.9477) ≈ sqrt(2.4574) ≈ 1.567。与 v6 (0.5, 1.6583) 之间的距离 ≈ sqrt(0.5² + 1.6583²) = sqrt(0.25 + 2.751) = sqrt(3.001) ≈ 1.732。v1 (1,0) 与 v5 (1.2287, 0.9735) 之间的距离 ≈ sqrt((0.2287)² + (0.9735)²) ≈ sqrt(0.0523 + 0.9477) = sqrt(1.0) = 1.0(可能)。v6 与 v5 之间的距离:sqrt((0.5−1.2287)² + (1.6583−0.9735)²) = sqrt(−0.7287² + 0.6848²) = sqrt(0.531 + 0.468) = sqrt(0.999) ≈ 0.999。因此,v6 可能距离最远。
计算 v2 与 v5 之间的距离:v2 的坐标约为 (-0.2287, 0.9735),v5 的坐标约为 (1.2287, 0.9735)。x 方向的差值为 1.4574,y 方向的差值为 0。因此距离 ≈ 1.4574。不算太大。
v2 与 v6 之间的距离:y 方向的差值约为 1.6583 - 0.9735 = 0.6848,x 方向的差值约为 0.5 - (-0.2287) = 0.7287。因此距离 ≈ √(0.6848² + 0.7287²) ≈ √(0.468 + 0.531) = √0.999 ≈ 0.999。结果合理。
v3 与 v6 之间的距离:x 方向的差值约为 0.5 - 0.7287 = -0.2287,y 方向的差值约为 1.6583 - 0.6848 = 0.9735。因此距离 ≈ √(0.2287² + 0.9735²) = √(0.0523 + 0.9477) = √1 = 1。
因此,最大距离很可能出现在 v0 与 v6 之间?实际上 v0 (0,0) 到 v6 (0.5, 1.6583) 的距离为 √(0.5² + 1.6583²) ≈ √(0.25 + 2.751) = √3.001 ≈ 1.7317。另外 v0 到 v5 的距离约为 1.567,等等。
因此,Moser 纺锤体(边长为 1)的直径大约为 √3 ≈ 1.732(很可能就是 √3)。事实上,最长距离很可能就是主轴的长度,即 √3。
因此,Moser 纺锤体中任意两个顶点之间的欧几里得距离至多为 √3(这很合理:两个菱形相对的两个锐角顶点之间的距离为 √3)。事实上,我们早前已指出,O 到对角的锐角顶点(C)的距离为 √3;而 O 作为一个顶点,到另一个菱形中对角的锐角顶点 F 的距离也是 √3。但 O 与某些其他顶点之间没有边,而任意两个顶点之间可能的最大距离是否恰好为 √3?我们来验证示意图:两个菱形相对的两个锐角顶点之间的距离——即第一个菱形中锐角顶点 O 与第二个菱形中对角的锐角顶点(记为 F)之间的距离——是 1(因为这是它们之间的单位边)。等等,我们之前说两个锐角顶点之间的距离必须为 1(两个非共享锐角顶点之间有一条单位边)。实际上,每个菱形中最远的顶点是其中心的锐角顶点 O,以及对侧的锐角顶点(在菱形 A 中记为 C,在菱形 B 中记为 F)。O 与 C 之间的距离 = √3。O 与 F 之间的距离 = √3。而 C 与 F 之间的距离为 1(它们之间的边)。因此,任意两个顶点之间的最大距离可能为 √3(可能是 O 到 C 或 O 到 F)。但其他顶点之间是否可能有更大的距离?例如,C 与第二个菱形中某个非锐角的顶点之间的距离可能更大?我们来计算近似距离:C = (3/2, √3/2) ≈ (1.5, 0.866)。与 F 比较(F 未知)。实际上我们需要知道 F 的坐标。在上面给出的 Moser 纺锤体坐标中,我们只有顶点 0 到 6。这 7 个顶点对应的是 Moser 纺锤体吗?实际上这个列表(0..6)可能是 Moser 纺锤体(7 个顶点)。我们来验证:这些坐标包含点 v0: (0,0)。v1: (1,0)。v2、v3、v4、v5、v6:某些点。还有 v6: (0.5, sqrt(11)/2) ≈ (0.5, 1.658)。这可能是顶点 O?等等,O 是某个顶点;我可能混淆了。让我们检查边关系:Moser 纺锤体中每个顶点的度为 3(可能有一个顶点度为 4?)。让我们检查已知的标签:在该示意图中,顶点是:
- O = (0,0)(公共的锐角顶点)
- A = (1,0)(第一个菱形的一个钝角顶点)
- B = (1/2, √3/2)(另一个钝角顶点)
- C = (3/2, √3/2)(对角锐角顶点)
- 对于第二个菱形:可能是 D = (0.5, sqrt(11)/2?),但这似乎太远了。
实际上我们需要确认映射关系。我们现有的坐标对应一个更大的结构吗?坐标 v6 = (0.5, sqrt(11)/2) ≈ (0.5, 1.658)。这超出了半径 1 的范围!实际上 sqrt(11)/2 ≈ 1.658 > 1,因此 v6 在 D 之外。所以这些坐标可能是针对缩放版本或其他单位的?检查距离:v0 到 v6 的距离为 sqrt(0.5² + 1.658²) ≈ sqrt(0.25 + 2.75) ≈ sqrt(3) ≈ 1.732。这小于 2,因此仍在半径 1 的圆盘内?但如果 y 坐标 1.658 > 1,则该点位于单位圆盘之外(因为半径 1 限制 y ≤ 1)。实际上 D(0.5, 1.658)到原点的距离为 sqrt(0.5² + 1.658²) ≈ 1.732 > 1。因此 v6 不在单位圆盘内部(半径 1)。所以这些坐标可能是针对缩放版本(更大半径)的。事实上,边长可能不是 1,或者坐标适用于包含整个图形的某个半径的圆盘。但我们需要的是单位圆盘(半径 1)的坐标。因此应该对图形进行缩放,使其适配单位圆盘。
因此,边长为 1 的 Moser 纺锤体的直径约为 sqrt(3),但整个图形可能无法放入单位圆盘内;我们需要将其缩放,使得最大距离 ≤ 2(直径)。实际上,整个图形的最小外接圆可能大于 1。例如,给定坐标中最远的点 v5 坐标约为 (1.2287, 0.9735),到原点的距离为 sqrt(1.2287² + 0.9735²) = 1.567 < 2。实际上 v5 在半径 2 范围内?v6 距离原点约 1.732,也 < 2。因此外接圆半径大约为 sqrt(3)。那么单位边长的 Moser 纺锤体能否放入半径为 sqrt(3) 的圆盘?实际上 sqrt(3) ≈ 1.732。但单位圆盘半径为 1,更小。因此,为了使图形能被半径为 1 的圆盘容纳,我们需要相应缩小比例。
因此 Moser 纺锤体可以被缩放:如果我们将其缩小比例 s,使其外接圆半径 ≤ 1(即所有顶点到原点的距离 ≤ 1)。在这种给定方向下,最大距离出现在 O 与 C(或 O 与 F)之间。到原点的最大距离可能更大,若将 O 置于中心,则可能是 O 到最远顶点的距离?但我们也可以移动图形使其位于单位圆盘内部。
因此我们可以计算出 Moser 纺锤体能被放置在单位圆盘内的最大缩放比例(即最大边长 d,使得该图形能完全放入单位圆盘内)。这就是 d* =(单位圆盘的直径)/(图形在其原始边长 1 下的直径)。单位圆盘的直径为 2。因此 d* = 2 /(边长为 1 的 Moser 纺锤体的原始直径)。如果这个原始直径为 sqrt(3),则 d* = 2 / sqrt(3) ≈ 1.1547。等等,当边长为 1 时,原始直径是 sqrt(3),但我们要求边长 = d。因此如果原始直径 = sqrt(3) × 边长?实际上,原始直径是指当边长为 1 时,任意两个顶点之间的最大距离。当边长 s(变量)时,所有距离与 s 成线性关系缩放。因此缩放后图形的直径 = s × 原始直径。条件是该直径 ≤ 2(圆盘直径)。因此 s ≤ 2 / 原始直径。如果原始直径 = sqrt(3),则 s ≤ 2 / sqrt(3) ≈ 1.1547。这比 sqrt(3) ≈ 1.732 要小。因此 Moser 纺锤体方法得到的上界是 1.1547,而不是 sqrt(3)。实际上我们之前估计它更大;我们需要谨慎分析。
我们考察了边长为 1 的 Moser 纺锤体,任意顶点之间的最大距离约为 sqrt(3) ≈ 1.732。但这是否是直径?我们来验证一下:O 到对角锐角顶点的距离为 sqrt(3);但这是否是任意两点之间的最大距离?最远的一对点可能是第一个菱形的对角锐角顶点与第二个菱形中相反的钝角顶点?我们来计算 O (0,0) 与 v5 (1.2287,0.9735) 之间的距离,约为 1.57,更小。而 v6 (0.5, sqrt(11)/2) 到原点的距离为 sqrt(3) ≈ 1.732。因此原始直径约为 sqrt(3)。确实,O(位于原点)与 v6(位于 (0.5, sqrt(11)/2))之间的距离为 sqrt(3)。这是该集合中任意两点之间的最大距离;其他任意两点之间的距离似乎都更小(很多对点的距离为 1)。因此原始直径 = sqrt(3)。所以 s ≤ 2 / sqrt(3) = 2 / 1.732 = 1.1547。因此嵌入的单位边长为 s。这意味着如果 s > 1.1547,则该图形无法放入直径为 2 的圆盘内。对于任意 s ≤ 1.1547,我们可以将 Moser 纺锤体嵌入单位圆盘(通过适当的放置和平移)。实际上必须确保整个图形完全位于半径为 1 的圆盘内。该图形可以被放置,使其最远两点之间的距离(即长度约为 sqrt(3)×s 的直径)不超过 2。因此 s ≤ 2 / sqrt(3) 可确保图形的外接圆直径 ≤ 2,但我们还需要能够将该图形放置在单位圆盘内部,即我们需要一个能完全包含缩放后图形的半径为 1 的圆盘。
如果我们按 s 缩放整个图形,则最大顶点间距为 s×sqrt(3)。为了将其放入半径为 1 的圆盘内,我们需要 s×sqrt(3) ≤ 2。因此 s ≤ 2 / sqrt(3)。于是,能够被嵌入单位圆盘内的 Moser 纺锤体的最大边长为 d_max_spindle = 2 / sqrt(3) ≈ 1.1547。这小于 sqrt(3)。因此仅使用三角形构造得的界限为 sqrt(3) ≈ 1.732,更大。因此,仅由三角形的上界得到 d ≤ sqrt(3)。但对于任何 d > 约 1.1547 的情况,我们是否可以避免单色距离?等等,Moser 纺锤体表明,当 d 不超过 1.1547 时,任何二染色都会产生单色距离。然而,我们也有三角形的界限:当 d ≤ sqrt(3) 时,我们保证存在等边三角形产生单色点对。这比 1.1547 更强。因此关键在于这两个界限中哪一个更大:sqrt(3) > 1.1547,因此三角形给出了更宽松的界限:只要 d ≤ sqrt(3),就能保证存在单色点对。同时,当 d 不超过 1.1547 时,Moser 纺锤体也提供保证(但更小)。但是否存在其他构型可以将保证扩展到超出 sqrt(3)?是否可能存在另一种单位距离图,其直径的缩放因子更大,导致界限大于 sqrt(3)?我们来思考一下。
为了向上扩展该界限,我们需要一种单位距离图(即某距离 d 的图),它是非二分图(色数 >2,即包含奇环,可能是三角形),并且当边长为 d 时能够嵌入单位圆盘内。三角形是一种直径为 d(边长)的图。对于给定的边长 d,在缩放至单位边长时,三角形的直径为 d?实际上,边长为 d 的三角形其直径就是 d(任意两顶点之间的距离)。因此,对于边长为 d 的三角形,要求其能放入半径为 1 的圆盘内,等价于 d ≤ sqrt(3)。因为三角形的顶点不一定以原点为中心;内接于单位圆的三角形边长最大可达 sqrt(3)。所以三角形的界限为 d ≤ sqrt(3)。
Moser 纺锤体是一种具有 7 个顶点的更复杂图。在该图中,所有顶点之间的最大距离可能大于边长。在我们边长为 1 的嵌入中,直径约为 sqrt(3);缩放后,直径与边长成线性关系。因此,Moser 纺锤体的嵌入条件给出 s ≤ 2 / sqrt(3) ≈ 1.1547。因此,Moser 纺锤体给出的上界比三角形更小。
因此,在能够将非二分单位距离图嵌入圆盘的约束下,三角形似乎是最大化该界限的最优结构(因为在三角形中,较长距离上将任意两个顶点分隔开的比率是最小的)。事实上,对于三角形,直径等于边长,比例为 1,因此该界限等于单位圆盘中能容纳的最大可能弦长,即 sqrt(3)。对于任何其他包含非三角形单位距离边的图,任意两个顶点之间的最大距离与边长之比更大,导致在受限于圆盘半径条件下的可缩放边长更小。因此,三角形很可能给出了最大的 d,使得任何二染色都会产生单色点对。
因此,答案很可能是 d_max = sqrt(3)。
但我们需要验证,对于任意 d > sqrt(3),都存在一种单位圆盘的二染色,使得不存在距离为 d 的单色点对,即此时距离图是二分图。看起来是可能的,因为当一个 d 使得关联图不含奇环时,该图就是二分图。我们怀疑当 d > sqrt(3) 时,无法嵌入奇环(如三角形)或其他奇距离环。但是否存在一种不规则的奇环形状,其边长大于 sqrt(3)?让我们尝试考虑一个具有弯曲边且包含非等距分离内角的奇环?实际上,我们可以将一个 5 个点构成的奇环作为一组点来嵌入,使得每对相邻点之间的距离恰好为 d,但非相邻点之间的距离可以不同。对于 5 个点的情况,存在一定的灵活性:我们可以将点沿一条近似闭合的锯齿形路径排列,每步长度为 d。当 d 接近 2 时,能否让这些点来回跳跃?对于 d 接近 2 的情况,每对相邻点几乎都位于圆盘的相对边界上;但为了闭合这个奇数长度的环,由于几何限制,我们需要奇偶性匹配。
让我们探讨一个步长为 d 的奇数长度、以原点为中心的正多边形。闭合路径的条件是经过 n 步之后的总和向量为零。如果每一步是长度为 d 的向量,并且相对于前一步旋转某个角度。对于正多边形,每一步旋转固定角度 2π/n,每个向量的长度为 d。要使闭合路径存在,需要 d * ∑_{k=0}^{n-1} e^{i * (θ₀ + 2πk/n)} = 0。由于该和式为零,对任意 d 都成立,因为在转向角度之和为 2π 完整旋转的情况下,单位向量之和为零。因此,正多边形可嵌入于任意半径的圆内,只要 d 不超过外接圆内的弦长。对于内接于半径为 R 的圆的正 n 边形,边长 s = 2R sin(π/n)。因此给定 s(即 d)后,可解得 R = d / (2 sin(π/n))。要使图形能放入单位圆盘(R ≤ 1)中,需满足 d ≤ 2 sin(π/n)。对于奇数 n,sin(π/n) 随 n 增大而减小;因此 d ≤ 2 sin(π/n) ≤ 2 sin(π/3) = √3 ≈ 1.732。故当 n ≥ 3 时正多边形所能允许的最大边长为 √3(对应 n=3)。当 n > 3 时,sin(π/n) 更小,因此最大 d 更小。因此,奇数环所能允许的最大边长受三角形情况限制(即 √3)。然而,对于非正则的奇数环,由于各边可能不内接于同一圆,最大边长可能超过 2 sin(π/n)。但闭合条件仍可能要求各边向量之和为零。对于奇数 n,大小为 d 的向量之和为零必须满足某些几何约束,这可能限制了 d 的范围。
让我们更一般地分析:假设在平面上有 n 个点 p₁, ..., pₙ,构成一个环状连接,即 p_{i+1} = p_i + v_i,其中 v_i 是长度为 d 的向量。闭合条件为:∑_{i=1}^n v_i = 0。对于奇数 n,若存在非零合力,则这是不可能的?实际上向量之和可以为零,但每个向量长度固定。这形成一个闭合的多边形链,其所有边长度相等;这被称为“等边多边形”。此类多边形有多种类型。已知一种结论:对于任意奇数 n,存在边长为 d 且直径任意小的等边多边形(例如可通过折叠实现)。但也可能存在直径较大的情况。
我们可以设想一个所有点共线分布的等边多边形:让点沿一条直线从左到右再返回等方式排列。然而,当 n = 5 时,若要求所有边长均为 d,则不可能将所有点排列在一条直线上,因为相邻点之间的距离必须为 d;我们能否得到一条折线,5 步后回到起点?对于奇数 n,若所有步长为 d 且方向仅取 +d 或 -d(即共线),则闭合路径不可能实现,因为这要求总位移为零,即所有步长的代数和为零,每一步为 +d 或 -d;对于奇数步数,+d 的个数减去 -d 的个数必须为零 ⇒ 总数为奇数意味着不可能(因为差值必须为偶数)。因此奇数环无法通过共线方式实现。因此需要一定的弯曲。
但或许我们能使所有点几乎在一条直径上共线,但存在微小偏转来调整方向;这样可能使多边形所占据的区域具有较大宽度,但如果点靠近边界,仍可能容纳于单位圆盘内。对于较大的 d,每一对相邻点必须在圆盘中相隔较远。当 d 接近 2 时,每一步几乎穿过整个圆盘。对于奇数步,五边形的奇数步后不可能闭合,因为在奇数次穿越后奇偶性无法匹配。然而,通过多次横穿圆盘的方式可能实现大小为 d 的闭合奇数环,即在圆盘内部来回穿越。
考虑 d = 2 - ε(略小于直径)。每一步几乎穿越整个圆盘;每一步的方向可能约等于某个角度。对于奇数步,无法使所有边的向量和为零,因为每条边长度接近 2(几乎为直径),且必须满足角度约束。也许当 d > √3 时可能实现,但不确定。
尽管如此,已知的组合几何结果表明:对于平面,Ramsey 距离阈值是 d = √3(也许?)。我记得一个已知问题:对单位圆盘进行二着色时,不可避免的最大距离为 √3。这被称为“欧几里得 Ramsey 理论:单位圆盘”中一个已知难题。这可能与 1970 年代的某篇论文有关。
回忆一下:有一个已知问题:平面上任意二着色是否必然包含一个单色等边三角形,其边长可为任意给定长度?这并不总是成立;但对于单位圆盘,某种尺寸三角形的存在也许是无法避免的。
考虑一个已知结论:对于任意二着色,半径为 1 的圆盘中必然存在一对单色点,其距离至少为 √3。实际上结果可能有所不同:这是一个极值问题,即寻找一个最大距离 d,使得任何二着色都会产生一对距离大于等于 d 的单色点。这个问题被称为“Gallai 选择定理”或“Borsuk-Ulam”类型?实际上有一个已知定理:对于球面上任意二着色,存在一对单色的对径点(距离为 2)。但我们已有反例;不过通过 Borsuk-Ulam 定理可能适用于连续函数。
另一个已知结论:对于圆盘(或二维球面)的任意二着色,是否存在一对单色点,其距离至少为 √2?不确定。
为了确认,我们需要查找已知结果。让我们查找“单位圆盘二着色不可避免的距离 √3”。
Search
"unit disk" "monochromatic" distance sqrt(3) 14 results
5环长边近径点排列几何构造示例
搜索结果不直接相关。
但这个具体问题可能被称为“单位圆盘中的欧几里得拉姆齐问题”或“圆盘中的距离拉姆齐问题”。它可能有一个已知的解答:“上确界距离是 sqrt(3)”。让我们看一个已知的类似问题:“在半径为1的圆盘中用红蓝两色对点进行着色,证明存在距离至少为 sqrt(3) 的一对同色点。” 实际上,存在一个已知问题:对单位圆盘进行二着色时,是否存在一对单色点,其距离至少为 sqrt(3)??等等,也许向一个大距离扩展可能是不可避免的?
再仔细回忆一下:有一个已知的问题:“对单位圆盘进行任意着色时,必然存在一对距离为 sqrt(3) 的单色点。” 这是否是“幸福结局问题”的一个特例?不是。
实际上,我认为可能与通过集合划分的“Borsuk-Ulam 定理”有关:对于球面上任意二着色,都存在一对对径点具有相同颜色。这是针对球面的情况;但对于圆盘则不适用。
对于距离 sqrt(3),考虑一个内接于圆盘的等边三角形。共三个顶点,着色仅有两种颜色,根据鸽巢原理,必有两个顶点同色,且它们之间的距离为 sqrt(3)。因此,对于任意 d ≤ sqrt(3),我们都可以有一个内接等边三角形(通过缩放实现)。实际上,对于任意 d ≤ sqrt(3),任何二着色都会产生一个单色的点对,其距离恰好为某个长度 d(不一定是 sqrt(3))。但我们所需的是距离恰好等于 d,而不是至多 d。对于给定的 d,我们需要的是距离恰好为 d 的点对,而非更小或更大的距离。对于每个小于等于 sqrt(3) 的 d,等边三角形方法虽然保证存在距离为 sqrt(3) 的同色点对,却不一定存在距离为其他值的同色点对。我们来验证一下:对于任意 d,取一个边长为 d 的等边三角形(必须位于圆盘 D 内)。当 d ≤ sqrt(3) 时,这是可行的:这样的三角形可以被放置。然后任意对三个顶点进行二着色,必有两个同色顶点,其距离恰好为 d。因此,对于任意 d ≤ sqrt(3),该条件都成立。也就是说,距离集合 d ∈ [0, sqrt(3)] 都满足条件。
因此,对于不超过 sqrt(3) 的距离,该上界是确定的。对于 d > sqrt(3) 的情况,我们无法在圆盘内嵌入一个边长为 d 的等边三角形。此时我们可考虑其他构型。
因此,最大的 d(上确界)至多为 sqrt(3)。实际上我们已证明,对于任意 d ≤ sqrt(3),该条件均成立;而对于 d > sqrt(3),能否找到反例?若存在针对某个 d > sqrt(3) 的着色方式,则可说明上界恰好为 sqrt(3)。因此我们需要为每个 d > sqrt(3) 构造一种着色,使得没有同色点对之间的距离恰好为 d。尝试寻找一种对任意给定 d > sqrt(3) 的通用构造方法。也许可以根据某种与 π 的倍数相关、但不等于 d 的方向距离,将每个点染成红色或蓝色,从而避免距离恰好为 d。
一种简单方法:对于固定的 d,考虑围绕每个点、半径为 d 的圆周。如果 d > sqrt(3),那么半径为 d 的圆将与 D 有较大交集。但也许我们可以对所有角度 θ 模 π 位于某个区间内的点染成红色,其余染成蓝色,使得距离为 d 的任意两点总是位于不同的颜色类别中。或者,也可以考虑将点划分为两个集合:对每个点 p,若其极角 θ ∈ [0, π) 则染成红色,否则染成蓝色。此时若一对点的距离为 d,只有当连接它们的弦具有某种方向时才可能颜色相同。但无法保证所有情况。
若基于点的 x 坐标模 d 来分配颜色如何?定义颜色为 floor(x/d) mod 2。对于任意两点 x₁, x₂ 满足 |x₁ - x₂| = d,有 floor(x₁/d) 与 floor(x₂/d) 相差 1,因此奇偶性相反,点对颜色不同。水平方向分离距离恰好为 d 的点颜色不同。但其他方向的情况如何?在垂直方向或其他方向上,x 坐标相同的两个点仍可能距离为 d。但如果两点在水平方向分离 d,则 x 坐标差恰好为 d,奇偶性翻转。对于方向不水平的点对,x 坐标的差值小于 d(因为水平分量小于总距离)。因此 floor(x/d) 可能相同或不同,颜色仍可能相同。
因此需要更强的方法:或许可通过划分空间来定义着色方式,使得距离恰好为 d 的任意两点必然落在划分线的两侧。这类似于构造一张“距离图”,用两种颜色着色,使其成为平面图;对于一个具有二着色方案的图,我们知道图必须是二分图;希望避免使用长度大于 √3 的奇数长度环。
但当 d > √3 时,该图可能是二分图。我们来检验一下:对于距离 d > √3,图中可能出现哪些边?考虑 D 中任意一点 p,其到 p 距离恰好为 d 的点 q 的集合,构成以 p 为中心、半径为 d 的圆,与 D 相交。由于 d > √3,该圆相对于 D 较大,但仍可能与 D 相交于一段弧。然而,对于每个 p,都存在许多距离为 d 的 q。
如果图中存在三角形,则必须存在三个点,它们两两之间的距离都恰好为 d,即构成一个边长为 d 的等边三角形。这只在 d ≤ √3 时才可能。因此当 d > √3 时,图中不存在三角形。是否存在任何奇数长度的环?对于五边形而言,要嵌入一个边长 d 大于 √3 的正五边形是不可能的。但是否存在一种不规则的、边长 d > √3 的 5-环?让我们尝试思考一个边长为 d > √3 的非正则 5-环的嵌入方式。能否将五个点放置成每对相邻点之间的距离为 d,但整个图不是正多边形?或许可以让点非常接近圆盘的边界,并在边界上略微前后移动。
考虑 d 接近 2(接近直径)的情况。选择边界上五个大致等距的点,但相邻点之间的距离 d 必须接近 2。然而在圆形边界上,两点之间的最大距离(弧长)是弦长:弦长 ≤ 2;只有当两点为对径点时,弦长才为 2。因此对径点对的距离为 2。对于略小于 2 的 d,边界上仍可能存在许多距离接近 d 的点对。但对于奇数长度的环,我们需要回到起点;可能由于奇偶性限制而无法实现:假设我们从边界上的点 p1 开始,沿边界移动到与 p1 距离为 d 的点 p2(但方向并非完全相切,因为弦长接近 d)。然后类似地继续到 p3 等。由于角度累加,n 步之后的总转角可能受限。
但如果我们将点移出边界进入内部区域,则存在足够的灵活性。
让我们使用向量几何方法:假设有一系列向量 v_i,每个向量的长度均为 d,我们需要它们之和为零:Σ v_i = 0。对于奇数 n,如果所有向量完全相同,则其和不可能为零。但我们可任意选择方向,甚至可能高度对称。
对于构造边能放入给定范围内(例如单位圆盘内)等边多边形的一般性约束,其可能性条件是要求存在一种“闭合的等边多边形链”构型。已知有如下结论:对于任意奇数 n 和任意满足 d ≤ 2 的边长 d,都存在能在半径为 2/d 的圆内嵌入的等边多边形链吗?不确定。
如果时间允许,或许可以调用一个已知结果:当 d > √3 时,单位圆盘内的距离图是二分图。我猜测该上界 d 恰好为 √3。
因此答案为:上界 d 是 √3。实际上问题描述为:“每次染色时总存在两个同色点距离为 d,求 d 的上界。” 所以答案应为 √3。
但我们还应给出一种构造性证明:证明当 d > √3 时,存在一种无单色距离 d 的染色方式。例子或许可参考以下方法:根据距离最近顶点属于 60° 扇形的奇偶性为每个点分配颜色。再进一步说明细节。
我们可以构造一种染色方式:对每个点 p,考虑由原点 O 出发、角度在 60° 倍数方向的 6 条射线,将圆盘划分为 6 个长度为 π/3 的扇形区域(类似披萨切片)。将交替的扇形区域染成红色或蓝色(例如,索引为偶数的区域染红色,奇数的染蓝色)。现在假设存在两个同色点 p 和 q,其距离恰好为 d > √3。证明它们之间的距离不可能大于 √3,否则它们将位于不同的扇形区域中。实际上,对于任意两个距离大于 √3 的点,它们不可能落在同一个 60° 扇形区域内(因为在 60° 扇形区域内,任意两点之间的最大距离至多为 √3)。我们来验证一下:在同一个角度跨度为 60° 的扇形内,点之间最远的距离出现在扇形边界圆的交点处?考虑一个半径为 1 的圆盘,被划分为 6 个中心角各为 60° 的扇形。在这样的扇形内部,任意两点之间的最大距离是否出现在扇形边界的两端?实际上,任意扇形内的点都在圆盘内,且它们之间的夹角至多为 60°。两点之间的距离公式为 √(r₁² + r₂² - 2 r₁ r₂ cos θ)。对于给定的 r₁, r₂ ≤ 1,当 θ ≤ 60° 时,距离最大不超过某些边界值的组合。我们可以尝试证明:在同一个 60° 扇形内的任意两点,其距离至多为 √3。事实上,考虑扇形边界上角度分别为 φ 和 φ+60° 且半径均为 1 的两个点,它们的弦长为 √3。若将任一径向距离减小,则弦长也会减小。因此,扇形内任意两点之间的最大距离为 √3,且只有当两点都位于半径为 1 的边界圆弧上,并处于扇形两端时才能达到该最大值。因此,若有两点距离大于 √3,则它们不可能位于同一个 60° 扇形内,而必须位于不同的扇形中。在我们的染色方案中,交替的扇形被赋予不同颜色,因此任意两个距离大于 √3 的点必然落在不同颜色的扇形中。然而,我们要求避免距离恰好为 d > √3 的情况。由于 d > √3,任何相距 d 的点对必然位于不同扇形,因而颜色不同(因为同色扇形互不重叠)。因此,这种染色方式避免了距离大于 √3(包括等于 d)时出现单色点对。
因此,我们得到了一种对任意 d > √3 的显式染色方案(通过 6 个扇形)。但我们还需仔细验证:两个同色扇形之间是否存在相距大于 √3 的点对?在此方案中,不存在距离恰好为 d > √3 的同色点对,因为任意两个距离大于 √3 的点必须位于不同的扇形中,因而具有不同颜色(因为相同颜色的扇形不相邻)。但这里有一个细节:由于集合未被完全分隔,同一点可以属于多个扇形;我们应根据角度将每个点分配到一个唯一的扇形中。如果某点恰好位于扇形边界上,我们在边界处赋予其不同颜色。但距离极近的两点是否可能落在不同扇形却颜色相同?实际上,相同颜色的扇形之间相隔两个扇形(例如扇形 0、2、4 颜色相同)。因此,两个同色扇形之间至少被一个异色扇形隔开,它们之间的角度差至少为 120°。距离大于 √3 的两个点,有可能分别位于两个同色扇形中;例如,考虑扇形 0 中的一个点与扇形 2 中的一个点,它们之间的夹角至少为 120°。夹角为 120° 时的最大距离(两点均位于边界上)为:弦长 = 2 sin(120°/2) = 2 sin(60°) = √3 ≈ 1.732。对于小于 180° 的角度,弦长随角度增大而增大;在 120° 时,弦长为 √3。距离能否超过 √3?对于更大的角度,最大弦长可达 2(直径),出现在 180° 时。因此,当两点位于不同但同色的扇形(如扇形 0 和扇形 2)且距离大于 √3 时,这是可能的。然而,我们的染色方案将相同颜色赋予了所有 0、2、4(偶数索引)扇形。因此,可能存在位于扇形 0 和扇形 2 中的两个距离大于 √3 的点,且它们颜色相同(均为红色)。这是否构成违反?但我们的目标是避免距离恰好为 d > √3 的单色点对。然而,这些点可能距离超过 √3,甚至大于 d,但不一定恰好等于 d。我们将 d 定义为大于 √3 的某一精确距离。要出现距离恰好为 d 的单色点对,必须存在两个颜色相同、距离正好为 d(精确值)的点。因此,我们必须确保不存在这样的点对。在扇形染色方案中,是否存在距离恰好为 d(例如 d = 1.8)的两个红色点?有可能。例如,在扇形 0 接近边界处取一点 p,在扇形 2 对称位置取另一点 q,使它们相距恰好为 d。这可能通过调整径向位置实现。因此,扇形染色方案可能无法避免所有单色距离为 d 的点对。
因此,我们可能需要更精细的染色方式。
也许,对于某个特定的 d > √3,我们可以避免单色点对;不一定对所有 d > √3 都成立;而存在避免的单色距离的上确界可能是 √3。因此,边界是 √3。也就是说,对于任意 d > √3 且任意 ε > 0,存在一种染色方案,可以避免单色点对恰好相距该 d 的情况?这看起来更可信:上确界是 √3,但上确界本身可能无法被任何在圆盘内距离大于 √3 的等边三角形实现?实际上,上确界是 √3,因为它是任意二染色中必然出现的距离集合的上确界。对于任何大于 √3 的 d,都存在一种双色染色方案,使得不存在距离为 d 的单色点对。因此,该上界恰好是 √3。
但我们需要明确“上界”的含义:它是使该命题对所有染色方式都成立的最大距离 d。因此答案是 √3。然而,我们需要验证对于任意 d > √3,确实存在一种双色染色方案可以避免该距离。给出一个构造性例子:也许我们可以将圆盘划分为交替着色的环形区域(像一个目标靶),其宽度经过调整以避免特定的距离。
或者,我们可以采用不同的思路:使用“单位圆盘图”,其色数大于2,当d > √3时,该图可能是二分图。因此只需对图进行二着色即可。实际上,圆盘内的距离-d图被称为单位距离图;如果d > √3,则该图可能不包含奇环,因此可能是二分图(可能包括无限的情况)。由于没有三角形,该图可能是二分图?但我们需确认是否存在奇环。是否存在当d > √3时长度为5的奇环?让我们检查边长为d的五边形情况。如前所述,五边形的外接圆半径必须满足 R = d / (2 sin(π/5))。由于D的半径为1,需要满足 R ≤ 1 → d ≤ 2 sin(π/5) ≈ 1.1756 < √3。因此,当d > √3时,不可能存在正五边形。然而,可能存在非正但边长仍为d的5-环。当d > √3时是否存在这样的5-环?是否可能将一个闭合的5段折线(每条边长均为d)嵌入圆盘中?可能,但不确定。
我们需要考虑欧几里得几何:假设有5个点p1...p5,每对相邻点之间的距离恰好为d。这形成一条闭合的路径。如果d > √3,则每一对点之间的距离相对较大,当5条这样的边首尾相连时,整个图形会超出圆盘范围。但也许我们可以让它来回穿行以仍保持在圆盘内。让我们分析总的可能的矢量贡献:每条边的长度均为d,我们可以任意选择其方向。为了达到闭合,方向角之和(加权)必须满足净位移为零。由于d较大,每条向量都较长;要总和为零,向量之间必须指向不同的方向,甚至彼此相对。对于奇数条边,除非存在一定程度的“回旋”,否则无法完全抵消。但或许当d接近2时,可以让一条边几乎横跨整个圆盘(从边界到对边),然后下一条边又几乎返回,如此反复;经过奇数条边后是否可能闭合?测试如下:假设 p1 位于最左边界点(-1,0),p2 位于最右边界点(1,0),其距离为2。若 d=2-ε,我们可以选择靠近边界的 p2 使得距离接近2。然后 p3 可能靠近左边界,略低于 p1,依此类推。对于奇数条边,我们需要在若干步之后恰好回到 p1,但可能并不完全精确。
但由于有5条边,我们可以让 p1 → p2 作为从左到右的一条近乎直径的路径,然后 p2 → p3 是从右向左的另一条近乎直径的路径,接下来 p3 → p4 又是从左到右的路径,依此类推。经过5步后,净位移可能非零。我们尝试模拟:将方向交替设为 +d 和 -d;但由于有5条边(奇数条),平均方向不可能完全抵消?让我们考虑一维情况:若沿直线放置边,方向可选 +d 或 -d,经过5步后,若要求总和为零,则需要 +d 的边数减去 -d 的边数等于0,即两条方向的边数必须相等,因此总边数应为偶数。因此奇偶性条件禁止奇数条边共线。然而,边的方向可以不在一条直线上,可以具有垂直分量。是否存在一种方向组合,使得5个长度均为d的向量之和为零?是的,这是可能的:选择正五边形的向量方向(即单位向量的矢量和为零)。对于正五边形,每个向量长度为1(单位长度),其矢量和为零。这是一个已知事实:作为多边形的闭合性质。若将所有向量按因子d缩放,只要取向保持一致,总和仍为零。因此,长度为d的闭合路径可以通过正五边形实现,只是外接圆半径会更大。正五边形的边长为 s = 2R sin(π/5)。当 s 给定时,可解出 R。因此,若 s > 2 sin(π/5),则所需的 R 将大于1,无法放入单位圆盘中。因此,任何边长为 s 的5段闭合路径都不能完全包含在单位圆盘内,因为其所有顶点必须位于半径为 R ≥ s / (2 sin(π/5)) 的圆内。若 s > 2 sin(π/5),则 R > 1,因此无法完全放入单位圆盘内。所以,任何边长 s > 2 sin(π/5) 的闭合等边多边形都不能位于单位圆盘内部。因此,当 d > 2 sin(π/5)(≈1.1756)时,五边形无法嵌入。这比 √3 ≈ 1.732 更小。
因此,当 d > 1.1756 时,五边形无法存在。所以奇环不能是五边形。然而,可能存在非正多边形的其他奇环构型,其顶点的凸包可能不是一个圆,某些顶点可能位于内部,而非全部在边界上。这是否可能实现更大的边长而不增加凸包半径?可能,因为某些顶点可以放在内部,从而使凸包变小。但请注意,每条边的长度为 d,若 d 很大,则每条边连接的点之间距离较大,这往往迫使它们靠近边界。对于大于 √3 的 d,即使是一个三角形也可能超出圆盘范围。但对于非三角形的奇环,也许我们也可以嵌入。
让我们考虑边长 d 接近 2 的情况。长度为 d 的奇环意味着每个顶点通过长边连接到相邻顶点。当 d 接近 2 时,每条边几乎穿过整个圆盘,连接接近对径的点。对于一个 5-环,我们可以设想点 p1、p2 彼此几乎对径。然后 p3 几乎与 p2 对径,即 p3 接近 p1。因此 p2 ≈ -p1 + ε₁,p3 ≈ -p2 + ε₂ ≈ p1 + (ε₁ + ε₂)。经过两步后,p3 接近 p1;第三步可使 p4 接近 p2,依此类推。在 5 步之后,我们可能接近 p1,但若 ε 之和不为零,则不保证完全重合。不过,我们可能进行调整以实现精确重合。
但可否举例说明:设 d 为接近 2 的某值,比如 1.95。取 p₁ 在角度 0°、半径为 1 的圆上:(1, 0)。p₂ 在角度约 180° 但略有偏移,设为 (-cosθ, sinθ),使得从 p₁ 到 p₂ 的距离为 d。解得:两点间距离 = sqrt((1 + cosθ)² + sin²θ) = sqrt(2 + 2cosθ) = sqrt(2 + 2cosθ)。令其等于 d,有 d² = 2 + 2cosθ ⇒ cosθ = (d² - 2)/2。对于接近 2 的 d,cosθ 接近 (4 - 2)/2 = 1,因此 θ 很小(约 0)。实际上,若 d 接近 2,则 cosθ 接近 1,θ 很小。因此 p₂ 应接近 p₁ 的对径点,但存在微小偏差。对于 d = 1.95,d² = 3.8025,cosθ = (3.8025 - 2)/2 = 1.8025/2 = 0.90125 ⇒ θ ≈ arccos(0.90125) ≈ 26°。因此两条半径之间的夹角约为 26°,即偏离对径点的程度不大。因此 p₂ 与 p₁ 近乎相对。
现在 p₃ 必须与 p₂ 距离为 d;可选择 p₃ 接近 p₂ 相对的另一端点(即靠近 p₁),带有微小偏移。这会形成来回震荡的模式。经过 5 步后可能闭合,但可能需要调整角度偏差,使得位移总和为零。对于奇数 n,令每条边近似地来回穿越,并适当选择偏离方向,是否可能使总和为零?有可能,但需要实现精确闭合。
然而,当 d > √3 时,能否嵌入一个 5-环并不明显,但也可能存在。
或许存在已知定理:对于凸区域,若在区域内无法构成边长为 d 的等边三角形,则距离-d 图是二分图。这可能是 O. Schramm 等人的研究结果?尚不明确。
更稳妥的方式是系统性地查阅文献:搜索“单位圆盘中的欧几里得 Ramsey 理论”和“距离 Ramsey”。
Search
Euclidean Ramsey theory unit disk distance 29 results
Think
搜索结果没有直接回答该问题。我们来优化一下。
搜索“单位圆盘内任意二着色必然包含距离为√3的单色点对”
Search
"unit disk" "two-coloring" "distance" sqrt{3} 12 results
圆周点距>√3的两色二分着色
我们看到一些结果,但尚未直接回答问题。让我们聚焦更具体的问题:或许被称为“圆盘内的欧几里得拉姆齐定理”或“Erdos–Hadwiger–Nelson问题”。
可能已有结论:对于任意二染色,单位圆盘内必然存在单色的距离d,其中d的最大值为√3。我记得曾读到或了解到一个已知结果:对于单位圆盘的任意双色染色,都存在一个单色的等边三角形(从而得到√3)。实际上,该已知结论正是:对于单位圆盘的任意双色染色,存在一个单色的内接等边三角形(其顶点位于边界上)。证明使用了博苏克-乌拉姆类型的组合论证,或简单的鸽巢原理。
但等等,三角形方法的证明是显然的:选择三个构成边长为√3的等边三角形的点?但我们选择的三个点必须是固定的;而染色是针对所有点的,我们可以考虑单位圆盘内任意一个固定的内接等边三角形T。在任意染色下,T的三个顶点中必有两个同色,且它们之间的距离为√3。因此,对于d = √3,该性质自然成立。对于d ≤ √3,我们可以嵌入一个边长为d的等边三角形;但对于给定的d,我们需要保证存在距离恰好为d的一对点。然而,三角形方法保证的是距离为√3,而不是任意距离d。因此,它并不是证明所有d ≤ √3都成立的直接方法;它只是说明d = √3是不可避免的(由三角形得出)。对于d < √3,也许我们可以通过构造特定三角形来保证?实际上,我们可以嵌入一个边长为d的等边三角形(如果d ≤ √3)。由于圆盘的半径为1,任何d ≤ √3都可以作为内接于圆盘的等边三角形的边长实现。确实,对于任意d ≤ √3,我们可以选择一个中心位于原点的等边三角形,使其顶点位于半径r = d / √3 ≤ 1的圆上(因为d ≤ √3)。因此该三角形完全位于圆盘内。在任意染色下,该三角形的三个顶点中必有两个同色,它们之间的距离恰好为d。因此,确实,对于任意d ≤ √3,这都迫使存在一对同色的等色距离d点。因此条件在区间(0, √3]内对所有d都成立,而不仅仅是在√3处。
因此,上界至少为√3。
现在我们需要检验d > √3的情况。是否存在一种双色染色,可以避免出现单色距离d的点对?如果存在,则上界恰好为√3。
因此我们需要为任意给定的 d > sqrt(3) 提供一种染色方案。这可以通过使用“单位圆盘图”来实现,只要没有等边三角形迫使该图成为二分图,就可以用两种颜色对图进行染色。因此我们需要生成一种染色方式,使得距离为 d 的任意两点颜色不同。这相当于构造一个图的正常 2-染色,其中该图的边表示距离为 d 的点对,即所谓的“单位 D 的 d-距离图”。如果该图包含奇圈,则无法用两种颜色进行正常染色,必然会出现单色边。因此 d > sqrt(3) 可能被避免的条件是该图是二分图。
因此问题归结为确定距离-d 图的奇圈阈值为 sqrt(3)。也就是说,对于 d > sqrt(3),该图是二分图。
但证明图的二分性可能不容易,不过已知有这样的结论:当 d > sqrt(3) 时,单位圆盘内的距离图是二分图。我回忆起一个已知结果:对于凸形区域(例如圆盘),其“单位距离图”在什么距离上是二分图?实际上,“单位距离图”通常被定义为点位于平面上,当两点距离恰好为 1 时就连边(或任意固定距离)。对于圆盘,距离-d 图是指顶点为圆盘中的点、边连接那些恰好相距 d 的点对;其结构依赖于区域形状。当 d 小于区域宽度时,图中可能包含奇圈;当 d 大于某个值时,图的结构更类似于匹配?有可能。
对于 d > sqrt(3),任何等边三角形的存在都会被排除,但五边形能否加入仍不确定。然而,即使存在长度大于 sqrt(3) 的奇圈,整个图仍可能是二分图。
我们需要检验圆盘内是否存在仅使用边长 d > sqrt(3) 的奇圈。考虑一个可能的 5-圈:假设我们试图放置 5 个点 p1,...,p5,使得每一对相邻点之间的距离为 d,但非相邻点之间的距离可以小于或大于 d。对于 d > sqrt(3),我们能否将它们放置成近乎直线但存在偏移的形式?让我们尝试证明其不可能性。
考虑任意三个在圈中依次连接的顶点 p_i、p_{i+1}、p_{i+2}。三角形的两条边 p_i p_{i+1} 和 p_{i+1} p_{i+2} 的长度均为 d。因此 p_i 和 p_{i+2} 是单位边长的 d 图中 p_{i+1} 的邻居。它们之间的距离可以是 0 到 2d 之间的任意值?实际上,它们的位置可以是达到 2d 距离的任意位置,但哪些值是可能的?给定一个长度均为 d 且共享一个顶点 p_{i+1} 的三角形,另外两个顶点 p_i 和 p_{i+2} 之间的距离由它们之间的夹角决定:根据余弦定理,距离 = sqrt(d^2 + d^2 - 2 d^2 cos θ) = d * sqrt(2 - 2 cos θ) = 2d * sin(θ/2)。这里 θ 是向量 p_i - p_{i+1} 与 p_{i+2} - p_{i+1} 之间的夹角。该 θ 可在 0 到 π 之间取值(因为点可以放置为共线但方向相反等情况)。因此 p_i 与 p_{i+2} 之间的距离范围从 0(θ=0)到 2d(θ=π)。因此它们之间的分离可以是 0 到 2d 之间的任意值。
现在考虑五边形:p1-p2-p3-p4-p5-p1。这里每对相邻点之间的距离为 d。考虑三角形 (p1,p2,p3)。p1 与 p3 之间的距离(p2 的路径长度为 2)可以在 0 到 2d 之间变化。类似地也是如此。
现在我们需要将 5 个点放置在单位圆盘内。单位圆盘的直径为 2。因此任意两点之间的最大可能距离为 2。因此我们可以有 d 最大接近 2,但条件可能会限制。
让我们尝试为大于 sqrt(3) 的 d 寻找一个奇圈。考虑 d = 1.8。设 p1 = (-1, 0)(最左侧的点)。p2 必须距离 p1 为 1.8;因此它必须位于以 (-1,0) 为中心、半径为 1.8 的圆上。该圆与单位圆盘(中心在原点,半径为 1)的交集形成一个区域。由于圆心距离较远,交集区域较大;我们来计算 p2 可能的位置。从 (-1,0) 出发、半径为 1.8 的圆与单位圆盘相交成一段弧。两个圆之间的距离为 1(圆心间距)。对于两个半径分别为 R1=1(圆盘)和 R2=1.8(接触圆),相交通的条件是:圆心间距 d_c = 1 ≤ R1 + R2 = 2.8(成立),且 d_c ≥ |R2 - R1| = 0.8(成立)。因此交集区域是一个透镜形状。交集区域中存在可能的点 p2。
现在 p2 必须位于单位圆盘内。p2 的可能位置区域是靠近右侧的一段弧。选定 p2 后,p3 必须距离 p2 为 d,依此类推。因此我们需要一条闭合路径。
但也许已知一种结论:对于圆盘内的任意 d > sqrt(3),距离图是二分图,因为圆盘内的任意奇圈都必须在某个三角形(三角形)中包含三个彼此等距的点。但也许任何奇圈都包含一个三角形作为子图?不一定。
但也许我们可以证明,任何奇圈必然包含一个长度至多为 sqrt(3) 的“短”对角线。对于任意一个环,其中某对非连续顶点之间的距离都可能小于 sqrt(3),然后我们可以考虑这个三角形。
或者,我们可以采用更组合化的方法:使用单位圆盘中任意两色着色都具有一个单色的内接等边三角形的已知结论,这可能是已被证明的结果:由于“Gallai 选择定理”?不太确定。
我们尝试直接证明:对于任意大于 sqrt(3) 的 d,存在一种两色着色,使得不存在单色点对之间的距离恰好为 d。构造如下:将圆盘沿某一直线分为两个半圆盘(例如左半部分和右半部分),一半染成红色,另一半染成蓝色,同时在边界上进行适当着色。
现在需要验证:任意两个距离为 d > sqrt(3) 的点不可能颜色相同。对于大于 sqrt(3) 的 d,任意两个距离为 d 的点不可能同时位于同一个封闭半圆盘内(从原点分割的水平半圆盘)。我们来分析一下:对于左半圆盘(角度从 90° 到 270°?)中的点,该半圆盘的宽度为 2(同样直径为 2)。该半圆盘内的最大距离出现在边界上相对的两点之间,即从圆盘顶部到底部,可能接近直径 2 吗?实际上左半圆盘包含靠近顶部的点和靠近底部的点;它们之间的距离可能达到接近 2 吗?我们来计算:点 (-1,0)(最左端)和点 (0,1)(顶部)不在左半圆盘内,因为 x=0 不是负值。左半圆盘对应 x ≤ 0 的点。其最远两点为 (-1,0) 和 (0,1);但 (0,1) 的 x=0,属于边界点(可能包含在内),距离为 sqrt((1)^2 + (1)^2) = sqrt(2) ≈ 1.414 < sqrt(3)。实际上左半圆盘内的最远两点可能是 (-1,0) 和 (0,-1),距离同样为 sqrt(2)。左半圆盘内部的最大距离也可能出现在 (-1,0) 和 (0,1) 之间;计算结果为 sqrt(1^2 + 1^2) = sqrt(2)。因此左半圆盘的直径为 sqrt(2)。确实,对于 x ≤ 0 的半圆盘,最远的两点是其边界与 y 轴交点处的 (0,1) 和 (0,-1)。实际上 (0,1) 和 (0,-1) 都位于 y 轴上,x=0,属于左半圆盘(若包含 x=0)。它们之间的距离为 2(距离的竖直差为 2)。注意 (0,1) 到 (0,-1) 的距离为 2(竖直线)。虽然这两点的 x=0,不一定位于半圆盘的直线边界 x=0 上,但如果我们将半圆盘定义为 x ≤ 0,则 (0,1) 被包含在内(因为 x=0),因此距离可以为 2。确实,(0,1) 和 (0,-1) 都在左半圆盘内(x=0),距离为 2。因此两个点都在左半圆盘内时,可以相距 2,这大于 sqrt(3)。这意味着仅通过半圆盘划分可能无法避免所有距离大于 sqrt(3) 的单色点对。
但我们可以尝试将圆盘划分为六个扇形区域,正如之前考虑的那样:60° 的扇形可能限制扇形内的最大距离。我们来计算一个角度宽度为 60° 的扇形内任意两点之间的最大距离。在连续区域内,最远的情况是两点分别位于扇形边界圆弧的两端。从圆心到这两点的半径均为 1?实际上,扇形边界上相距最远的两点,是两条 60° 夹角的半径与边界圆弧的交点,如前所述,这两点恰好是每条半径在半径为 1 处的端点。这两点间弦长的距离为 sqrt(3)。因此,该扇形内任意两点之间的最大距离为 sqrt(3)。所以,在同一个 60° 扇形内,不可能存在距离大于 sqrt(3) 的点对。很好!现在我们需要将颜色分配给各个扇形:可交替地染成红色和蓝色,例如扇形 0、2、4 染成红色,扇形 1、3、5 染成蓝色。这样可避免距离大于 sqrt(3) 的单色点对,即使这样的点对相距较远,只要每个扇形内点之间最大距离不超过 sqrt(3),就不会出现同色且距离大于 sqrt(3) 的情况。实际上,两个红色点可能位于两个不同的红色扇形中,而这些扇形之间可能距离较远(例如相隔 120°)。它们之间的距离可能超过 sqrt(3)。但我们的目标只是避免距离恰好为等于某个大于 sqrt(3) 的特定值 d 的单色点对。由于可以按照交替颜色分配扇形,任何距离恰好为 d 的点对必须满足某种条件:p 和 q 要么都位于同一扇形内(如果它们足够接近),要么位于不同扇形中。但我们仍需确保不存在同色且距离恰好为 d 的点对。让我们针对给定的 d > sqrt(3),使用这种 6 扇形着色方案来分析。
设 us 的顶点在 0°, 60°, 120°, 180°, 240°, 300° 对应的位置定义扇形。按角度区间给每个点分配颜色:扇形 i(i 从 0 到 5)包含角度在 [i*60°, (i+1)*60°) 的点。分配颜色:当 i mod 2 == 0 时为红色,否则为蓝色。
现在考虑两个点 p 和 q,它们之间的距离恰好为 d > sqrt(3)。我们需要证明它们的颜色不能相同;如果可能相同,我们就失败了。我们来计算角度差 Δθ = |θ_p - θ_q|(模 360°)。由于它们之间的距离 d > sqrt(3),角度差必须大于 60°,因为如果 Δθ ≤ 60°,则弦长最多为 sqrt(3)(如前所述)。事实上,对于弦长 s = 2 sin(Δθ/2),给定半径为 1。因此 s > sqrt(3) 意味着 sin(Δθ/2) > sqrt(3)/2 = sin(60°)。因此 Δθ/2 > 60° → Δθ > 120°。所以角度差大于 120°。此外,距离较大的点的角度分离也必须大于 120°。更准确地说,弦长 s > sqrt(3) 当且仅当 Δθ > 120°?我们来计算:s = 2 sin(Δθ/2)。s > sqrt(3) 意味着 sin(Δθ/2) > sqrt(3)/2 = sin(60°)。因此 Δθ/2 > 60° → Δθ > 120°。此外,若考虑最小角(即 ≤ 180°),则 s > sqrt(3) 推出 Δθ > 120°,否则若 Δθ > 180°,可考虑较小的反射角(360 - Δθ)。因此我们可以考虑较小的角 ≤ 180°。所以条件是两个点之间的较小角必须大于 120°。
因此,任何距离大于 sqrt(3) 的两个点的角分离必须大于 120°。因此它们的方向位于宽度大于 120° 的不同扇形中。在我们的 6 扇形着色(每个扇形 60°)中,分离大于 120° 的两个点可能位于以下扇形:
- 它们可能位于扇形 i 和 i+2(相隔 120°),但这种分离恰好为 120°,不足以满足大于 120° 的条件;距离将恰好等于 sqrt(3)。由于 d > sqrt(3),它们不能恰好相隔 120°(除非在边界情况)。因此它们必须至少相隔两个扇形,即位于扇形 i 和 i+3(相隔 180°)或 i 和 i+2,但如果它们的角位置不完全在边界上;分离可能大于 120°,但如果角度跨越扇形边界,扇形编号差可能为 2。例如:一个在 10°(扇形 0),另一个在 140°(扇形 2)。角差为 130°(在扇形边界上测量)。实际上扇形 2 覆盖的角度范围是 120° 到 180°,因此 140° 属于扇形 2。因此分离为 130°,大于 120°,它们位于扇形 i 和 i+2。因此它们可能颜色相同,如果这两个扇形都是红色(i 和 i+2 均为偶数)。事实上,扇形 0 和 2 都是红色。因此两个红点可能相距大于 sqrt(3)。所以我们通过交替扇形进行的着色不能保证对于所有大于 sqrt(3) 的距离 d 都避免出现同色点对。
但我们可以合并不同的图案:不采用每隔一个扇形(周期为 2)的交替着色,而可以使用 3-着色(三种颜色)来避免同色点对,但这里我们只有两种颜色。可以将颜色模式设为在围绕圆周的 12 个扇形区间内重复,以避免某些特定距离。
但如果 d > sqrt(3),也许仍可仅使用两种颜色通过更巧妙的染色方法避免同色点对。这可能对应于构造一个 2-着色,使得距离为 d 的图是二分图。对于大于 sqrt(3) 的 d,也许该距离图为二分图。如果该图是二分图,则存在一种 2-着色(因为当图是二分图时,其顶点可以进行 2-着色而无单色边)。然而,可能存在多种这样的着色方式;但存在一种着色并不意味着可以在连续集合上显式构造;而对于二分图,存在适当的 2-着色:为每个连通分量指定一种颜色,然后交替着色。对于无限图,可能存在一种全局的 2-着色方案(可能是非连续的)。由于这是一张几何图,也许我们可以将颜色定义为“条纹”模式的某种函数。
我们需要证明,对于每个大于 sqrt(3) 的 d,都存在一种对 D 的 2-着色,使得没有两个同色点恰好相距 d。实际上,这表明距离图是二分图,即该图不存在奇圈。已知一个结论:对于 [0,2] 内的 d,当 d > sqrt(3) 时,单位圆盘内的距离-d 图是二分图。这可能被称为“临界距离”。
我们可以考虑使用“维津定理”来给单位圆盘中的距离图着色:这涉及到“欧几里得拉姆齐理论”。
让我们系统地查找文献:搜索词为“unit disk distance graph bipartite threshold sqrt(3)”
Search
"distance graph" "unit disk" bipartite sqrt(3) 22 results
距离约束下奇环可收缩为三角形
搜索结果并未直接回答该问题。然而,这个问题很可能有一个已知答案。让我们思考一些已知结果:“单位圆盘内任意两色着色下的单色距离”。我记得一个已知结论:对于凸形的任意两色着色,存在一个单色直径(即距离等于该凸形直径的两个点)。但这是针对连续着色以及对应于该图形宽度的某个特定距离而言的。不过,对于圆盘来说,直径为2;但我们已经有过一个反例(通过将相对的扇形区域着色以对径点颜色不同),说明可以避免出现颜色相同的对径点。但或许任意两色着色是否必然存在一对单色点,其距离至少为√3?实际上,等边三角形给出了距离恰好为√3的结果。
是的,很可能这个问题的答案就是√3。让我们通过构造一个针对任意d > √3的着色方案,来验证d > √3时的情况。也许可以使用一种“旋转的条纹”模式,随着半径增大而螺旋式旋转,但需要保证对于较大的距离,不会出现单色点对。
另一种方法是,我们可以通过“角度坐标的二进制展开”来定义着色:将点p的颜色定义为极角θ(模π)的二进制表示的奇偶性,也就是说,当⌊θ/π × 2ⁿ⌋ mod 2等于0时,将点染成红色,否则染成蓝色,其中n足够大以至于能够区分出距离d。由于d > √3时,具有相同颜色且距离恰好为d的两个点的最小角分离应大于120°,因此我们可以据此调整参数。
更好一点,或许我们可以设计一种周期性重复的着色方法,基于整数网格将平面划分为若干单元,并将每个单元染成红色或蓝色,使得任意两个同色单元之间的距离都不恰好等于d。对于大于√3的d,或许可以选择宽度为d' < d的条纹(因为不存在距离恰好为d但非常接近的同色点对)?但实际上我们需要避免的是距离恰好为d,而不是任意距离。因此我们可以把颜色定义为 floor(x / d)(模2),这能确保任意两个水平距离恰好为d的点颜色相反。然而在同一水平条带内但具有垂直偏移的点,如果它们在水平方向上没有恰好相差d,则可能距离为d。尽管其欧几里得距离可能由于垂直分量而等于d,但对于任意距离为d的两个点,其水平分量差异为 ±d。因此,着色 floor(x / d) mod 2 是否能保证水平距离差恰好为d(Δx = d)时,这两个点颜色相反?确实,如果两个点的x坐标相差d,则floor(x1/d)与floor(x2/d)相差1,因此奇偶性翻转,颜色相反。这是针对水平方向分离的情况。对于任意方向,我们可以考虑投影到某个与向量相关的直线上。
但如果能够选择方向使得距离为d的任意点对在该方向上的投影差恰好为d(某些直线上恰好相距d的点对可能具有小于d的投影)。实际上,对于任意固定的方向u,点对(p, q)在方向u上的投影差为 |⟨p−q, u⟩| = d * cos(θ),其中θ是点对连线与方向u之间的夹角。该值是否总是小于或等于d?事实上,如果该连线的方向单位向量与u一致,则两个点之间的x方向投影差恰好为d。如果它们不与u对齐,则投影差将小于d。因此基于floor(投影/d)的奇偶性着色可能无法区分那些距离为d但投影差较小的点对。不过我们可以尝试使用某种着色组合,使其依赖于坐标在一个与d不可公度的模数下的奇偶性。
让我们考虑一个更结构化的方法:假设我们将平面按方向为垂直、间距为w的平行线进行划分(或者可能是相对于d为无理的某个方向)。然后根据点位于哪一条带中为每个点分配颜色。但我们必须确保任意两个相距恰好为d的点不会落入同色带中。如果我们把平面划分为交替颜色的条带,则任何距离大于条带宽度的点对将属于不同的条带;但如果它们恰好落入同一颜色类别中,仍有可能位于相同颜色条带内(例如两个点都在红色条带中)。为了避免距离为d的点对颜色相同,我们需要确保条带宽度小于d,并且任何相距恰好为d的两个点永远不会同时落入同一颜色的条带中。
如果我们定义宽度 w = d/2,并将条带交替染成红色和蓝色,那么距离大于 w 的两个点是否可能位于不同颜色的条带中?实际上,考虑两个相距为 d 的点 p 和 q,它们完全可能位于同一颜色的条带中:每个条带的宽度为 w;如果点 p 位于某个红色条带中,点 q 可能在第一个点上方距离 d 处,若 d < 2w 则可能仍处于同一条带内?数值计算如下:假设 p 位于红色条带底部附近,q 位于上方距离 d 处,如果 d 小于红色条带的宽度,则 q 可能仍处于同一条带。为了避免这种情况,需设 w < d。事实上,若 w < d,则任意相距为 d 的两个点不可能处于同一条带内,因为其垂直距离大于条带宽度。然而,距离为 d 的两个点不一定具有垂直方向;它们可能在水平或斜向方向上的位移。条带是水平方向的,因此垂直分量小于 d 的点对仍有可能位于同一条带中。例如:点 p 在 (0,0),点 q 在 (d,0),它们具有相同的 y 坐标,因此位于同一条带(因为条带按 y 坐标水平划分),故而可能出现颜色相同(两者均为红色)的情况。实际上,由于它们处于同一水平条带内,颜色确实可能相同。因此这种简单的条带划分方法失败。
因此我们需要一种对两个坐标都敏感、或具有“棋盘”图案的划分方式。
考虑以边长为 w 的正方形网格对平面进行铺砌。像国际象棋棋盘一样,交替地为正方形着色(例如黑色和白色)。这样可避免每个颜色类别内部的最大距离:两个同色方格之间的最大距离取决于它们可能相距较远。但在某个给定颜色类别中,两点之间的最大距离可能很大(跨越多个方格)。然而我们可以使 w 相对于 d 非常小:若 w 足够小,则任意距离为 d 的两个点不可能位于同色方格内,因为它们至少需要跨越约 d/w 个方格。不过,若点对恰好跨越边界,仍有可能使两个点位于同色方格中;但若 w 相对于 d 较小时,唯一能够相距 d 的方式是它们处于较远的位置,可能跨越许多方格。但如果它们是交替着色的方格,则虽然存在大量同色方格,但这些方格并不相邻。例如,两个同色方格之间可能被相反颜色的方格隔开。两个点可能分别位于两个相距较远的同色方格中,并通过一系列颜色不同的方格形成距离为 d 的连接?颜色本身并不是距离上的障碍。
然而,我们需要确保不存在距离恰好为 d 的两个同色点。这种二元着色的棋盘网格可能无法避免这一点:假设有两个点分别位于两个红色方格的中心,彼此相距较远,但可能恰好距离为 d,此时两点均为红色,从而导致违反条件。
更好的方法是使用周期性铺砌,将区域划分为交替着色的六边形单元,并仔细选择颜色,使得任意两个同色单元之间的欧几里得距离永远不会等于 d(针对给定的 d)。如果允许两单元之间的距离在一定模意义下等于 d,这种方法也许是可行的。
或者,我们或许可以断言这样的着色存在(通过选择轴的线性组合,其系数为 d 的倍数且符号交替等方式)。对于给定的 d,我们可以将平面划分为平行线族的等价类,这些平行线以 d/2 为间距并相互偏移,使得每条线上的点与给定颜色类中其他线上的点颜色相同?这种方法类似于二分图:距离为 d 的图是二分图,等价于存在一个从平面的赋范空间到 Z₂ 的同态映射,且在距离为 d 时发生符号翻转。这意味着存在一个函数 f: ℝ² → {0,1}(着色),使得对于任意距离为 d 的向量 v,都有 f(x+v) = 1 - f(x)。即一种“完美码”类型的映射。对于某些离散点集(如格点),此类函数是存在的。
或许可以考虑函数 f(p) = floor((x + y)/d) mod 2?但实际上我们需要的是在距离为 d 的平移向量下具有周期为 2 的“距离无关”性质。
考虑 ℝ² 在距离恰好为 d 的平移向量集合下的商空间。该群可能由多个方向生成。如果该群存在二染色,则可以构造出相应的染色方案。
另一种方法是利用已知的“单位圆图距离为 d 时具有 2-染色”这一结论,这是否等价于圆盘内的距离-d 图是二分图?我回忆起一个已知概念:“距离图” G(ℝ², {d}) 是指以 ℝ² 中所有点为顶点,边连接距离恰好为 d 的点对的图。该图的色数被称为“单位距离的 Nelson-Hadwiger 型问题”。对于平面,单位距离图的色数至少为 4(也许在任何距离下均如此)。但对于有界区域,情况可能更低。
但对于单位圆盘而言,与之相关的可能是特定概念:“圆盘色数”指的是在圆盘内以距离 d 为边所构成图的色数。这一点我不确定。
考虑到难度,或许这个问题来自某道数学竞赛题或谜题,其预期答案为 √3。这很可能就是正确答案。
接下来我们需要给出最终答案:上界是 √3。需提供证明:下界(必然成立)可通过构造一个内接于单位圆盘的等边三角形来说明;上界(可以避免)则通过构造一种将圆盘划分为六个 60° 扇形的染色方案(或以中心为基准的交替扇形染色)来证明,当 d > √3 时,可以避免出现同色点对距离恰好为 d。但我们之前已经意识到,对于某些 d > √3,这种简单的六扇形交替染色可能无法避免所有距离下的同色点对(例如 1.8)。也许我们可以换一种方式调整染色:使用以中心角 120° 为间隔的两个半平面交替染色(类似“三色”模式?),但我们只有两种颜色)。实际上,我们可以将圆盘划分为三个扇形(各 120°),并以特定方式染色:例如将扇形 A 染红,扇形 B 染蓝,扇形 C 染红?这样红色区域会被蓝色扇形隔开。由于同色扇形之间至少相隔 120°,因此任意两个红色点之间的最小角度至少为 120°,对应弦长至少为 √3。实际上,相隔 120° 时弦长恰好为 √3。因此,任意同色两点间距离至少为 √3(最小值);而距离大于 √3 是否就是红色点之间的最小距离?事实上,严格大于 √3 的距离也是可能的:角度略大一点,弦长就略大于 √3。因此,任意同色红色点对至少相距 √3,要么恰好等于 √3(当角度为 120° 时),要么大于 √3(当角度更大时)。然而,我们需要避免的是距离恰好为某个 d > √3 的同色点对。如果染色方案允许同色点之间存在至少 √3 的多种距离,则可能会在某个大于 √3 的特定 d 值上恰好出现距离 d。因此,只要存在某个同色的点对对,其距离恰好是我们试图避免的 d 值,这种着色方案就会失败。
即使我们将角度划分为 120° 的扇形并采用红、蓝、红的配色模式,仍然存在许多红色点可能恰好处于某种距离 d > √3 的情况,特别是当大量红色点均匀分布在同一个扇形内时?实际上,每个红色扇形为 120°。从原点出发,一个红色扇形内的点的角度范围最大为 120°。对于位于同一红色扇形内的点,它们之间的最大距离最多可达到当两者均位于边界半径上且夹角为 120° 时的弦长 √3(这就是该扇形内的最大距离)。然而,若两点都在同一扇形内,则它们之间的角度差最多为 120°,因此距离 ≤ √3。因此,同一扇形内的任意两点之间最多相距 √3;它们不可能恰好相距 d > √3。所以,如果我们仅关注距离大于 √3 的情况,则任意两个同色点必须属于不同的同色扇形。要使两点均为红色,它们必须分别位于两个被蓝色扇形隔开的不同红色扇形中。这意味着它们之间的角度差至少为 240°(即相隔两个扇形),而较小的夹角可能为 120°?实际上我们有三个扇形:红色扇形位于 0–120°、蓝色扇形位于 120–240°、红色扇形位于 240–360°。因此两个红色扇形分别为 0–120° 和 240–360°。一个红色点位于角度 θ1 ∈ [0,120°],另一个红色点位于角度 θ2 ∈ [240°,360°]。它们之间的角度差(最小绝对差值)可能是 (θ2 − θ1) mod 360,若考虑模 360 的情况,该值介于 120° 到 360° 之间?我们来计算:若 θ1 = 0°,θ2 = 240°,差值为 240°,相当于较小夹角为 120°(因为最大差值为 180°,超过 180° 时可取 360° 减去该值)。实际上,我们考虑较小夹角 δ = min(|θ2 − θ1|, 360° − |θ2 − θ1|)。当 |θ2 − θ1| ≥ 180° 时,δ = 360° − |θ2 − θ1|。在此例中,|θ2 − θ1| = 240°,因此 δ = 120°。因此,任意两个分别来自两个红色扇形的点,其最小角度分离最多为 120°(因为扇形位于对侧)。事实上,最大最小分离角出现在一点位于第一个红色扇形的下边界(0°),另一点位于第二个红色扇形的上边界(360°)时,尽管属于不同扇形,但角度相同(0° 与 360° 相同)。它们的差值为 360°,δ = 0°,因此它们可能相距很近?等等,但我们还需考虑径向距离;即使角度相同,若半径不同,仍可能相距较远。
但能够相距大于 √3 的关键在于,这些点可以位于红色扇形内部的对侧边界上:例如,一个扇形中的点位于角度 0°、半径 1 处,另一个扇形中的点位于角度 240°、半径 1 处。它们之间的角度差为 240°,但较小的夹角为 120°,对应弦长为 √3。这恰好等于 √3。若要获得大于 √3 的距离,需要角度分离大于 120°,但因为扇形将圆周分成了三段,这是无法实现的。尽管角度分离可以大于 120°,但此时较小的夹角仍为 120°,而欧几里得距离依赖于较小夹角,而非较大角;弦长由较小夹角决定:s = 2 sin(δ/2)。当 δ = 120° 时,s = √3。若两点角度上相隔很远(例如 200°),较小夹角则为 160°(因为 360° − 200° = 160°),大于 120°,导致 sin(80°) > sin(60°),弦长大于 √3。确实,若两点位于不同扇形中,其间夹角可以大于 120°。例如,θ1 = 10°,θ2 = 240°,则角度差为 230°,较小夹角 δ = 130°,产生弦长大于 √3。因此,来自不同红色扇形的两个红色点之间的距离可以大于 √3。也就是说,距离恰好为 d(大于 √3)的情况在红色点之间是可能存在的。因此,即使将扇形划分为 120° 并进行染色,也不能避免对某个恰好为 d(大于 √3)的距离出现同色点对。
因此,如果我们选择在120°区间内交替着色的多个扇形,那么当 d>√3 时,可能会出现红色的距离 d。然而,也许对于给定的 d>√3,我们可以调整扇形的角度:选择一种以60°为扇形区间、按2种颜色周期性着色,使得同色扇形之间的角距离永远不会恰好等于产生弦长为 d 的某个特定角度。
或者,我们可以使用圆周上以长度 α(小于 d)为间隔的线性函数来实现着色。对于任意 d,都存在一种使用两种颜色的 2-着色方式,能够避开单色的距离 d,前提是我们可以利用“自由群”等方法将 ℝ² 映射到 ℤ₂ 上。
考虑如下方法:选择一种将 ℝ² 视作 ℚ-向量空间的处理方式;定义 f(p) = floor(a·x + b·y) mod 2,其中 a、b 是 d 的有理数倍?这是一种线性形式。对于距离向量 v = (dx, dy) 且满足 √(dx² + dy²) = d 的平移,点积 a·dx + b·dy 可能是不确定的;但我们可以选择满足 √dx² + dy² = d 的 a, b,使得 a·dx + b·dy 恒为奇数?实际上,我们可以选择 a, b,使得对于任意满足 d² = dx² + dy² 的向量 v,点积 a·dx + b·dy 都是某个数的整数倍加 1/2?但这似乎并不现实。
另一种方法是采用“模距离”着色:随机为每个点分配红色或蓝色;那么在大量地点中,存在一对距离为 d 且颜色相同的点的概率可能不为零,但我们可以对圆盘进行“有限”版本的测度论证?然而我们需要的是确定性着色。
但或许可以使用“佐恩引理”(Zorn's lemma)类型的论证来证明这种着色的存在性:考虑所有不包含单色距离 d 的圆盘的极大二着色子集构成的族。根据佐恩引理,这个族存在极大元;如果这个极大元不能覆盖整个圆盘,则存在某个点未被着色,我们可以为其分配一种颜色,同时避免产生新的单色距离 d,从而与极大性矛盾。该论证表明,对于某个 d,无单色距离 d 的二着色存在当且仅当其距离图是二分图。因此,存在此类着色的充要条件是该图是二分图(通过超图的标准极大性论证)。于是问题归结为距离图是否为二分图。对于 d > √3 的情况,我们需要证明距离图确实是二分图。所以问题最终归结为:证明当 d > √3 时,单位圆盘内的任何奇圈都不可能所有边长都恰好为 d。
潜在方法:证明 d > √3 时的任意奇圈都必然包含一个三角形作为子图?这似乎不太可能。
让我们考虑一个具有边长 d > √3 的 5-圈。假设点 p1,...,p5 位于圆盘 D 内。考虑任意三个按顺序排列的连续点:p_i, p_{i+1}, p_{i+2}。如前所述,p_i 与 p_{i+2} 之间的距离可能达到 2d 之间的任意值。然而,注意到 p_i 与 p_{i+2} 之间的距离不可能小于某个值?实际上它可能任意小:如果该圈折叠起来,它们可能非常接近。但我们能否限定其下界?不一定。
但也许我们可以证明:对于 d > √3,任意奇圈所包含的三角形边长都 ≤ √3?并不能直接得出。
或者,也许可以证明:对于 d > √3,距离图是平面图且不含三角形;平面图若不含三角形,则根据格罗茨sch定理(Grotzsch's theorem)是 3-可染的,但未必是 2-可染的。然而,可能存在不含三角形但仍含奇圈(如长度为 5 的圈)的平面图。不过平面上的不含三角形的 5-圈单位距离图是否能在 d > √3 时嵌入?可能不能。
实际上,可能存在已知结果:对于单位圆盘中的任意 d > √3,距离图是二分图;等价地说,在平面上无法构造出长度为 d > √3 的单位距离奇圈。一些文献提到:“单位距离图在平面上可嵌入的最大奇圈长度为 √3”。也就是说,任何单位距离奇圈必须满足 d ≤ √3。这可能是一个已知几何事实:唯一与凸形相交的单位距离奇圈是三角形,其边长至多为该图形直径;但所有其他奇圈向外扩展时会超出区域范围。
理论上,我们可以证明:任何单位距离奇圈必须包含一个等边三角形作为子图。这成立吗?在欧几里得平面上的任意奇圈中,至少存在三个顶点,它们之间的弦长等于边长?不一定成立。
考虑一个单位正方形(4-圈)。它不包含三角形。因此,偶圈可以不含三角形。而对于奇圈,也许任意奇圈必然包含一个三角形?在欧几里得几何中,考虑一个边长均为 d 的正五边形:它包含多个三角形:任何三个顶点可能并非两两距离均为 d;但其中存在不构成圈的三角形边。然而,我们能否找到一个三角形,其所有边长均为 d?在正五边形中,由三个连续顶点构成的三角形包含两条长度为 d 的边和一条对角线(较长)。因此,并非所有边都等于 d。
但也许任意奇圈至少包含一个三角形子图,其所有边长至多为 d?不确定。
可能已有结论:对于任意大于 √3 的距离 d,不存在所有边长均为 d 的奇圈能完全放置在单位圆盘内部。因此该距离图是二分图。于是,使得二着色可避免单色距离 d 的最大 d 值就是 √3。
因此答案为:d_max = √3。
现在我们需要提供一个严谨的论证,或至少一个合理的证明概要。
我们可以给出如下推理:对于任意 d ≤ √3,在圆盘内放置一个边长为 d 的等边三角形。根据鸽巢原理,按照任意二着色方式,至少有两个顶点颜色相同,从而得到一对距离为 d 的单色点。因此所有满足 d ≤ √3 的值都是不可避免的,故上界至少为 √3。
接下来我们需要证明,对于任意 d > √3,都存在一种二着色方式,使得不存在单色点对之间的距离恰好为 d。具体构造如下:将圆盘划分为六个中心角均为 π/3 的扇形区域。根据角度区间对点进行着色,使得相对的两个扇形区域具有相同颜色(即扇形 0、2、4 为一种颜色,1、3、5 为另一种颜色)。但我们之前已经看到,这种方案可能无法避免距离为 d > √3 的情况。然而,我们可以进一步将每个扇形区域更进一步地划分为同心的圆环(annuli)。
更好的方法是:使用一种不依赖于具体 d 的着色方案,但必须保证对于任意 d > √3,都不存在一对单色点恰好相距 d。实际上,我们需要一种适用于给定 d > √3 的着色方式;它可以依赖于 d。因此,我们可以根据所需的距离来调整着色方案,方法有很多。
一种方法是使用“三角晶格”:选择晶格间距 a,使得 a 与 d 不可通约(即 a/d 为无理数)。然后将点按晶格点位置模该晶格进行着色,使每个点被染成红色或蓝色,以满足某种模 2 的条件。由于 a/d 是无理数,距离为 d 的两个点不可能具有相同的颜色,因为这会导致该比值下的奇偶性周期为有理数?但目前还不确定。
另一种方法是,若存在满足条件的着色,则可通过贪心算法构造:以任意方式为各个点分配颜色,同时确保其颜色不会与已着色且距离恰好为 d 的点冲突。由于圆盘中距离任意给定点恰好为 d 的点集是一个一维圆(若整个半径为 d 的圆都包含在 D 内)。对于每个点,最多有连续统多个潜在的冲突点(边界)。但我们能否基于良序使用超限归纳法,持续扩展着色而不产生冲突?这种技术是标准的:对于无边的集合,使用两种颜色对顶点进行着色,使其成为正常着色(即图为二分图),可在每个连通分量中选择一棵生成树,然后按照树中距离的奇偶性分配颜色等方式实现。
因此,这种无单色距离 d 的二着色的存在性,等价于距离图为二分图。所以我们需要证明当 d > √3 时,该距离图是二分图。这可以通过证明图中不存在奇圈来实现。假设存在一个长度为 k(奇数)的奇圈,其中每对相邻顶点之间的距离均为 d > √3。考虑这些点的凸包;由于奇数性,至少有一个顶点位于其他顶点张成的凸包内部(根据Carathéodory定理)。然后考虑角度之和,我们可以证明必然存在三个顶点能够构成边长为 d 或不大于 d 的三角形,而这在 d > √3 时是不可能的?我们来尝试一下。
另一种方法是采用向量方法:设 v₁, ..., vₖ 为 k 段等长为 d 的链中连续的差向量(v_i = p_{i+1} - p_i)。由闭合条件可得:Σ_{i=1}^k v_i = 0。由于 k 为奇数,令 k = 2m+1。v_i 的平均值必须为零。对于每个 i,考虑 v_i 与某个方向之间的点积;寻找矛盾:将向量点积与 v_i 和的平方长度结合起来分析:
设 S = Σ v_i = 0,则 0 = |S|² = Σ |v_i|² + 2 Σ_{i<j} v_i·v_j = k d² + 2 Σ_{i<j} v_i·v_j。因此 Σ_{i<j} v_i·v_j = -k d²/2。
现在有 (k 选 2) 个点积,每个点积最大可能为 d²(当向量方向相同时)。但并非所有向量都可以同向,否则它们的和不可能为零。为了在 k 为奇数且等于 2m+1 时最小化总和,我们可以考虑某种构型,使得某些向量对之间具有负的点积。
我们可以估计点积之和的下界:对于任意单位向量 u,Σ (v_i·u) = 0。可以考虑 v_i 关于 u 的方向分布。
但已知一个结论:对于 ℝ² 中长度为 d 的奇数个向量的序列,其和为零的条件意味着 d ≤ √3 * R,其中 R 是任意两个顶点之间可能的最大距离,可能如此?实际上我们需要对 d 相对于区域直径进行上界估计。
可以使用组合几何中的“硬币问题”方法:对于任意三个在圆内的点,根据鸽巢原理,其中至少有两个点之间的距离至多为 √3?事实上,在单位圆盘内,任意三点之间必然存在一对点,其距离不超过 √3(由直径的拉姆齐型结论得出)。实际上,圆盘内任意三点之间必然存在一对点,其距离不超过 √3。这是一个已知结论:圆盘直径的拉姆齐数为 √3?这一点并不完全明确。但我们可利用这一性质:对于单位圆盘内任意三个点,其中至少有两个点之间的距离 ≤ √3。这就是已知结论:圆盘直径的拉姆齐数是 √3(即对于任意一组三点,总存在两点距离不超过 √3)。该结论可通过考虑包围三角形的最小圆来证明:若三角形的外接圆半径 > 1,则该三角形无法完全包含在单位圆盘内?大概如此。
如果将这一结论应用于奇圈中的任意三个顶点,我们会得到弦长 ≤ √3 的一对点。然而,奇圈中的边仅存在于连续顶点之间(距离为 d)。非连续顶点之间的距离可能更小;也许在任意三个顶点中存在一对距离 ≤ √3 的点。由于 d > √3,这将是一对距离小于 d 的点,但它们不是图中的边(即边长为 d)。然而,这对点可能属于同一种颜色类,但不一定违反关于距离 d 的条件。不过,我们可以利用这一条件推导出矛盾吗?或许可以表明,总存在某一顶点对(可能不相邻),其距离 ≤ √3 < d,并且它们的颜色相同?但实际上尚不明确。
另一种方法是考虑如下思路:取一个边长为 d > √3 的奇圈。任取其三个顶点(连续三个),构成一个两条边长为 d、第三边为某长度的三角形。该三角形的第三边长度可能小于或大于 d。若尝试将这三个顶点放置在单位圆盘内,则由于圆盘的几何特性,其中两个非连续顶点之间的距离不可能超过 √3?事实上,对于一个边长均为 d(即边 p₁p₂ = p₂p₃ = d)的三角形,其对边 p₁p₃ 的最大可能距离受到某种限制;当顶点 p₂ 位于原点,而 p₁ 和 p₃ 分别位于相对于 p₂ 的某夹角 θ 方向上时,p₁ 与 p₃ 之间的距离最远。由于 p₂ 必须在单位圆盘内,因此 p₁ 和 p₃ 也必须位于单位圆盘内部。给定 p₂ 的位置,p₁ 与 p₃ 之间的距离最大值受限于圆盘的几何结构。若 d > √3,是否仍可将它们放置在内部?考虑以 p₂ 为中心、半径为 d 的圆;d > √3 可能大于圆盘半径,导致从 p₂ 出发、半径为 d 的圆所包含的圆盘内部区域非常有限,可能只是一个很小的透镜形区域。p₁ 与 p₃ 之间的距离无法超过圆盘直径(2)。因此是可能的。
但仍然存在总长为奇数、步长为 d 的闭合路径;将它们首尾相连后,总位移必须为零。若 d > √3,每一步的长度相对于圆盘较大,可能导致总和为零变得不可能?或许可通过模运算计算:连续奇数个长度大于 √3 的向量之和不能为零,因为每个向量都相对较大,难以相互抵消。
我们可以尝试证明:对于任意三个长度均为 d > √3 的向量,其和不可能为零。事实上,若将它们首尾相连放置,最大合位移是多少?计算如下:对于三条长度均为 d 的向量,其合位移 R = v₁ + v₂ + v₃,其模长范围在 0 到 3d 之间。最小可能模长为 0(当三者可构成闭合三角形时)。何时可实现和为零?这要求这三个向量在平面上能构成一个三角形;即需满足三角形不等式:每一边 d 必须小于或等于另两边之和(2d)。由于 2d ≥ d 恒成立,因此可构成三角形。对于任意 d > 0,均可构成边长为 d 的等边三角形,三个向量首尾相连即可形成闭合回路。三个长度均为 d 的向量之和为零是可以实现的(例如等边三角形)。实际上,若 v₁ + v₂ + v₃ = 0,则三者的向量和为零,意味着它们能形成三角形。当 d 取任意值时,均可形成等边三角形,使三者之和为零。因此,三个长度大于 √3 的向量之和为零是可能的。但对五个向量而言,或许存在某种限制。
但我们仍需考虑奇循环长度大于3的情况。
也许存在一个已知结论:单位圆盘内唯一能够嵌入的奇循环是三角形,且仅当 d ≤ √3 时成立。我认为这一结论在具有恒定边长的“单位距离图”中是成立的。这让人联想到L. Moser(1950年代)关于单位距离图染色数的成果。Moser纺锤体是一种单位距离图,其色数为4,它包含两个菱形,这些菱形是否可视为4-循环?实际上,Moser纺锤体是否包含长度为7的奇循环?尚不确定,但其中确实存在奇循环。
总之,我们需要回答这个问题。我怀疑其答案是 √3。
我们将回答:上界为 √3。
同时需要提供证明:下界(必然成立)可通过嵌入等边三角形得出;上界(可以避免的构造)可通过将点按角度坐标对 π 取模划分来着色,使得任意两点间距离不小于 √3;需证明当 d > √3 时,距离图是二分图——可通过向量加法证明任何奇循环都意味着存在一个可嵌入的三角形(矛盾)。给出简要的组合证明:假设存在奇循环 {p₀, ..., p_{2k}},其中每条边的长度均为 d > √3。考虑向量 v_i = p_{i+1} − p_i,每个向量长度为 d。由于这些向量的和为零,这些向量的角度集合必须满足某些条件。接着根据距离大于 √3 时有 sin(θ/2) > √3/2,可知关于点积之和的限制导致矛盾。大致的论证思路是:对奇数 n,有 Σ_{i<j} v_i·v_j = −n·d²/2;利用每个点积的下界 cos θ ≥ −1/2?需要进一步展开。
更好的方法:使用以下已知引理:对于 ℝ² 中任意三个点 a、b、c,若对所有点对都有 |a−b| > √3 且 |b−c| > √3,则必有 |a−c| ≤ √3。这一结论源于单位圆盘的直径为2,且任意两个距离大于 √3 的点必须位于圆盘相对较小的子区域内。实际上可考虑一点周围的角度关系:若圆盘内两点之间的距离大于 √3,则它们之间的夹角超过 120°(因为它们位于以原点为中心的单位圆盘内)。因此,对于三个点若两两间距离均大于 √3,则每对点之间的夹角都必须大于 120°,但当围绕圆周累加这些角度时,总和将超过 360°,这是不可能的。因此,圆盘中不可能存在三个两两之间距离均大于 √3 的点。这是一个已知结论:在单位圆盘中,能够两两距离大于 √3 的点的最大数量为2。因为在角度分离大于 120° 的前提下,最多只能有两个点满足两两夹角均超过 120°(夹角之和不能超过 360°)。因此,不可能存在三个两两之间距离均大于 √3 的点。这就是关键性质。
因此,当 d > √3 时,距离图不包含三角形(3-循环)。此外,对于任意奇循环,我们可以考虑三个连续的点;由于它们之间并非全部两两距离大于 √3(只有连续的点之间的距离为 d),但非连续的点之间可能距离更近。然而,我们之前使用的论点可能表明:在任意三个点中,至少有一对点的距离不超过 √3;但我们将这一结论应用在整个点集中:考虑一个长度为 2k+1(奇数)的循环。由于最多只能有两个点之间两两距离大于 √3,因此该循环中至少存在三个点,它们之间的两两距离并不都大于 √3。但也许我们可以利用这一事实推导出矛盾:任选三个连续的点 p_i、p_{i+1}、p_{i+2}。我们知道 p_i 与 p_{i+1} 的距离为 d > √3,且 p_{i+1} 与 p_{i+2} 的距离也为 d > √3。根据引理,至多只能有两个点之间的两两距离大于 √3。由于我们已经拥有两对(p_i, p_{i+1})和(p_{i+1}, p_{i+2})距离大于 √3,那么任何第三个涉及 p_i 或 p_{i+2} 的点对(例如 p_i 与 p_{i+2})的距离必须 ≤ √3(否则将出现三个两两距离均大于 √3 的点)。因此 |p_i - p_{i+2}| ≤ √3 < d。这意味着存在一条点对,其距离小于 d,但这是允许的(边仅存在于距离等于 d 的点之间)。不过我们可以考虑距离 d' = |p_i - p_{i+2}| ≤ √3 所构成的图;但该图并非距离图的一部分。
尽管如此,也许我们可以利用这一点说明该循环包含一个“捷径”,从而形成一个更短的奇循环?这可能导致一个三角形?但实际上并不能。
另一种方法:使用“图收缩”方法:在任意奇循环中,存在三个连续顶点,其中第一个和第三个之间的距离小于 d(因为它们不能同时距离大于 √3)。然后将它们收缩,形成一个更短的奇循环(长度减少 2)。重复此过程,最终会归约为一个三角形(长度为 3)。这将与 d > √3 时三角形无法存在的事实相矛盾。因此,奇循环不可能存在。
我们来形式化一下:设 C 是一个长度为 n(奇数)且所有边长均为 d > √3 的循环。对于任意三个连续顶点 a、b、c,我们有 |a-c| ≤ √3(根据引理)。因此我们可以将 a 和 c 识别(收缩)为一个顶点,由于 |a-c| 可能小于 d,我们可以认为由 |a-c| 定义的边属于 d-图。然而,这种收缩可能会产生多重边,但我们可以应用归纳法:收缩后的图仍包含一个长度为奇数的循环(因为移除了 2 个顶点)。持续进行此过程,直到得到三个顶点 a、b、c,满足 |a-b| = d,|b-c| = d,|a-c| ≤ √3 < d。这形成了一个三角形,其中两条边长为 d,一条边更短。但并非所有边都是单位的(d)。因此可能不会直接产生矛盾。
但或许我们可以论证:在这种收缩之后,会得到由边长构成的一个三角形结构;然后从该三角形可以构造出一个边长为 d 的三角形(因为我们可以将第三个顶点移动到适当位置以调整其长度?),但这并不准确。
让我们看看关于单位距离图中奇循环的已知结论:对于 ℝ² 中给定的距离集合 D,存在奇循环存在一个已知阈值:在平面上的唯一可能的奇循环就是奇数长度的循环,而它们能否存在取决于具体的距离。
也许尝试用谷歌搜索“奇数长度的单位距离循环”会得到一些已知结果。
搜索:“odd cycle unit distance graph diameter sqrt(3)”。
Search
odd cycle unit distance graph sqrt(3) 10 results
最大单色点对距离为√3的上界
检索结果中提到了单位距离图的“奇圈”和“色数”,以及条带中的临界宽度 eps = sqrt(3)/2;这可能相关:eps <= sqrt(3)/2 可保证色数不超过 3。但我们当前的问题是针对阈值为 sqrt(3) 的两种颜色。不过,或许可以利用条带的结果:若将单位圆盘内接于一个宽度为 sqrt(3) 的条带中,则能够保证出现单色距离?尚不确定。
参考:B. Bauslaugh 的论文《色数与条带奇圈的最小宽度》提出了临界宽度 sqrt(3)/2。这与两种颜色是否相关?实际上该问题针对的是 3-染色;但或许可应用于对边长为 1 的条带(无限长条)进行染色。与此处问题不完全一致。
尽管如此,问题“对单位圆盘进行红蓝染色,总能找到两个距离为 d 的相同颜色点”的答案是 sqrt(3)。这是合理的。
我们来构造一个严谨的论证:
下界(必然性):
对于任意 d ≤ sqrt(3),在圆盘内构造一个边长为 d 的等边三角形 T。由于圆盘半径为 1,可在圆盘内部嵌入一个边长为 d 的等边三角形以适用于所有 d ≤ sqrt(3)。然后对这三个顶点任意进行二染色;根据鸽巢原理,至少有两个顶点颜色相同,并且它们之间的距离恰好为 d。因此,对于任意 d ≤ sqrt(3),该性质均成立。故 d 的上界至少为 sqrt(3)。
上界(可避免性):
对于任意 d > sqrt(3),我们构造一种无单色距离 d 的染色方案。赋色方式如下:对于每一点 p ∈ D,设其极角为 θ,令 f(p) = floor( (θ / (π/3)) ) mod 2。也就是说,将角度六等分(每份 60°),并交替着色红色和蓝色。对于任意一对满足 |p - q| = d > sqrt(3) 的点,我们可以证明它们不可能属于同一种颜色。事实上,由于弦长公式,两点间距离大于 sqrt(3) 意味着较小的夹角大于 120°。然而,同色扇区之间的角距离至多为 120°(因为同色的扇区被相反颜色的扇区隔开)。面积论证表明,若夹角大于 120°,则两点必然落入不同颜色的扇区。因此,任意一对距离为 d > sqrt(3) 的点必须是不同颜色。因此,这种染色方式避免了单色距离 d。故对于任意 d > sqrt(3),该性质不成立。
不过之前我们已经注意到,可将同色扇区间隔设为 120°,但夹角大于 120° 仍可能对应同色扇区?我们来验证一下:角度区间 0–60°(红色),60–120°(蓝色),120–180°(红色),180–240°(蓝色),240–300°(红色),300–360°(蓝色)。因此红色扇区位于 0–60°、120–180°、240–300°,任意两个红色扇区之间的夹角为 120° 或 240°。若考虑最小夹角,则属于不同红色扇区的两点间最小夹角可以是 0(当它们接近边界时)。实际上,点 A 位于角度 5°(红色扇区0),点 B 位于角度 125°(红色扇区2):夹角为 120°,弦长为 sqrt(3)。当夹角大于 120° 时,可达到更大的距离。因此,两个红色点之间的距离可以是任意不超过 2 的值……实际上两个红色点之间的最大距离可达 2(理论上 p 在 0° 到 300° 之间)?我们来计算极端情况:p 在 0° 且半径 r=1,q 在 180°?但 q 在 180° 属于蓝色扇区,而非红色。对于红色点,可用的最大角度是接近 180° 吗?实际上第二个红色扇区是 120°–180°,第三个红色扇区是 240°–300°。那么,红色点在角度上最远可能达到 180° 和 300°(相差 120°),或者 0° 和 300°(相差 300°,但最小夹角为 60°)。等等,0° 和 300° 相差 300°,最小夹角则是 60°,这小于 120°,但该点对颜色相同(均为红色)。因此,两个红色点之间的夹角可以小至 60°,对应弦长小于 sqrt(3)(即 1)。因此红色点之间的距离可以是任意大于 0 的值,最远可达 2,但其中部分距离可能小于或等于 sqrt(3)。
因此,对于 d > sqrt(3) 的情况,简单的扇区着色不能保证避免同色点之间的距离。确实,考虑 p = (r=1, θ=0°) 且 q = (r=1, θ=300°) = -60°,两者的角度差为 60°,弦长为 1(小于 sqrt(3))。所以不属于 d > sqrt(3) 的情况。对于 d > sqrt(3) 的情况,我们需要的是最小夹角大于 120° 的点对之间的关系(因为弦长 s > sqrt(3))。对于最小夹角大于 120° 的情况,这些点不可能同时在同一个 60° 的扇区内,也不可能位于具有小角度偏移的相邻扇区中。最小的角度偏移必须大于 120°,这意味着这些点必定落在至少相隔两个扇区的不同扇区中(即:如果考虑六个 60° 的扇区,角度间隔大于 120°,那么可能是扇区 i 和 i+3(相对),也可能是 i+2?实际上,大于 120° 的最小角度间隔可达 180°。我们来分析一下:将圆周划分为六个 60° 的扇区。角度间隔大于 120° 的情况包括:i 到 i+3(180°)、i 到 i+2(120°),但需要严格大于 120°,因此只有当角度略超过边界时,i+2 才有意义;i 到 i+4(同样是 120° 的偏移)情况相同;而 i 到 i+5(如 0° 到 300° = 60° 偏移)则不被允许。因此,唯一可能使最小角度间隔大于 120° 的扇区组合,实际上仅限于几乎完全相对的扇区(或角度接近相对的扇区)。只要两点半径接近 1,且角度偏移大于 120°,距离就大于 sqrt(3)。因此,这些点必定大致位于相对位置,可能分属颜色相同或不同的扇区。颜色分配模式可能保证相对位置的点颜色相反(例如在与边界对齐的着色中,相对点始终颜色不同)。但我们也可以设计一种着色方式,基于 floor(kθ / (2π)) 的奇偶性,使得相对点颜色相反。
思路:将平面划分为交替颜色的两个半平面,中间由一个小的中性区域分隔?定义着色规则:若点的角度 θ 满足 sinθ > 0(即在上半平面),则为红色,否则为蓝色(即 x 坐标的符号)。对于距离大于 sqrt(3) 的两点,其弧度差至少为 120°,它们不可能同时位于同一个半平面(上半或下半),因为每个半平面的角宽度为 180°,可能包含角度差达 180° 的点。实际上,角度差最大为 180° 的两个点可以同时位于上半平面,例如角度为 10° 和 170° 的点,其角度差为 160°,弦长为 2 sin(80°) ≈ 1.969 > sqrt(3),两者都在上半平面(因为 sin 为正)。因此,这种基于半平面的着色方式无法避免同色点之间出现大于 sqrt(3) 的距离。
因此我们需要更巧妙的着色方法。
另一种方法:使用以中心角为 120° 的扇区着色(划分为 3 个扇区),并将每个扇区交替染成红色和蓝色?实际上我们只有两种颜色,因此可以像之前一样将三个扇区交替染色:扇区 0(0–120°)为红色,扇区 1(120–240°)为蓝色,扇区 2(240–360°)为红色。这样,角度为 10° 的红色点和角度为 250° 的红色点之间的角度差为 240°,最小夹角为 120°,对应弦长恰好为 sqrt(3)。但若角度略有调整,最小夹角可能超过 120°,导致弦长大于 sqrt(3)。因此,红色点之间也可能出现大于 sqrt(3) 的距离。事实上,红色扇区 0 和扇区 2 以 120° 的蓝色扇区分隔,两点之间的最小可能角偏移为 0(当它们接近边界角度时),但在最大距离情况下,最小偏移是关键因素。红色点之间的最大距离可能达到 2(例如 p 在角度 0°、半径 1 处,q 在角度 180°、半径 1 处)?但角度 180° 属于蓝色扇区,因此 q 不能是红色。对于红色点,最远的情况是角度 0° 的红色点和角度 240° 的红色点?角度差为 240°,最小夹角为 120°,弦长为 sqrt(3)。实际上,获得大于 sqrt(3) 的最小夹角需要大于 120°,这意味着点必须位于几乎相对的扇区位置(角度差接近 180°)。在三个扇区的染色方式中,不存在完全相对的扇区(只有 120° 的间隔)。因此,红色点之间的最大距离为 sqrt(3)。实际上,红色点不能精确地处于相对位置(180° 分离),因为相对的角度位于蓝色扇区中。因此,任意两个红色点之间的最小夹角至多为 120°,无法超过 120°,因此它们之间的距离不能超过 sqrt(3)。同理适用于蓝色点。因此,这种三个扇区的染色方式保证了每个颜色类别内的所有点对的距离都不超过 sqrt(3)。这提供了一种避免单色距离大于 sqrt(3) 的染色方案。事实上,在同一个颜色类中,任意两点之间的角度差至多为 120°,而半径不超过 1,因此最大距离不超过 sqrt(3)。我们来验证:设有两个红色点,其角度分别为 θ1 ∈ [0,120°) 和 θ2 ∈ [240°,360°)。它们之间的最小角度差 δ 是否可能低至 0?实际上,θ2 也可以表示为 [−120°,0°)(模 360)。因此,θ1 和 θ2 可能接近,例如 θ1 = 10°,θ2 = −10°(即 350°)。那么 δ = 20°?实际上两者接近:若一个点在 10°,另一个点在 350°,角度差为 20°,最小夹角为 20° < 120°,两点距离是否大于 sqrt(3)?不需要考虑。因此,两个红色点可能位于角度 10° 和 350°(均在红色扇区内吗?),但 350° 属于扇区 2(红色),因为其角度范围为 240°–360°。是的,350° 是红色。因此,两点可以非常接近(20° 的角分离),距离很小。没问题。关键是:它们能否达到大于 sqrt(3) 的距离?我们来计算当两点位于各自扇区边界附近时可能出现的最大距离:点 A 在 0°(扇区 0 的边界),点 B 在 240°(扇区 2 的边界),角分离为 240°,最小夹角为 120°,弦长为 sqrt(3)。若点 A 在 120°(扇区 0 的边界)且点 B 在 240°(扇区 2 的边界),角分离为 120°,弦长同样为 sqrt(3)。因此两点间最大距离为 sqrt(3)。由此可见,三个扇区(每种颜色 120°)的染色方式确保了每个颜色类中任意两点之间的距离至多为 sqrt(3)。因此,它避免了在距离 d > sqrt(3) 处出现单色点。很好!
因此,三个扇区的染色方式对任意 d > sqrt(3) 均有效!我们来测试 d = 1.8 > sqrt(3) 的情况;是否存在两个红色点距离恰好为 1.8?由于红色点之间的最大可能距离为 sqrt(3) ≈ 1.732 < 1.8,因此不可能存在距离为 1.8 的红色点对。蓝色点同理。因此,这种染色方式确实避免了距离大于 sqrt(3) 的单色点对。
因此,阈值恰好为 sqrt(3)。若将圆盘划分为围绕原点的三个 120° 扇区并将交替的扇区染成相同颜色(颜色模式为红、蓝、红),则该染色方案适用于任意 d > sqrt(3)。因为每个颜色类中的点被限制在两个不相邻的 120° 扇区中。由于任意两个位于不相邻扇区(扇区中心夹角为 120°)内的点之间的最大距离为 sqrt(3),因此不可能存在距离大于 sqrt(3) 的点对。事实上,同一颜色类中两点间可能的最大距离正是当两点分别位于其扇区远端点(边界)时,即角分离为 120°,弦长为 sqrt(3)。因此 d 的上界为 sqrt(3)。
最终结论:d 的上界(最大保证距离)为 √3。
此外还需注意:距离 d 是否恰好等于 √3?根据上界定义,若长度为 √3,是否仍存在一种染色方式可避免单色点对处于该距离?实际上,对于 d = √3,我们能否避免?上述染色方案是否避免了距离恰好为 √3 的单色点对?我们来检验:是否存在距离恰好为 √3 的红色点对?我们已论证,当两点位于同一颜色类中且角分离为 120° 时,红色点之间的最大距离恰好为 √3,这种情况出现在两点分别位于各自扇区的边界角上时。例如,红色点位于 0° 和 240°(两者均为红色)时,距离恰好为 √3。因此,在这种染色方案下,存在距离为 √3 的单色点对(红色)。这意味着我们无法避免 d = √3 的情况。但根据题目要求,“无论怎么染色,必然存在两个同色点距离恰好为 d”,因此对于 d = √3,任何染色方式都必然存在一对距离为 √3 的单色点。这是一个保证性质,而我们的染色方案恰好体现了这一点(存在这样的点对)。因此不可能避开 d = √3,这与保证性一致。
因此,上界恰好为 √3;那么对于 d > √3 是否就存在避免的可能?我们可以使用上述的三扇区染色法;对于任何 d > √3,都不存在距离为 d 的单色点对,因为同色点之间的最大距离为 √3。因此 d > √3 是不被保证的。故 sup D_good = √3。
最终答案:√3。
现在给出最终答案,包含严谨推理。
我们需要提供以下两个方面的严格论证:
- 证明下界:对于任意 d ≤ √3,存在一种染色方式,使得必然出现同色点对且其距离恰好为 d。实际上,我们需要证明的是,对于任意 d ≤ √3,任何红蓝染色都会迫使出现一对同色且距离为 d 的点。正如我们之前所述,在单位圆盘内嵌入一个边长为 d 的正三角形,该三角形的三个顶点均在单位圆盘内。根据鸽巢原理,至少有两个顶点颜色相同,且它们之间的距离恰好为 d。
- 上界:对于任意 d > √3,我们可以构造一种染色方式,使得不存在距离为 d 的同色点对。采用前述的扇形划分方法:将单位圆盘划分为三个中心角均为 120° 的扇形区域 S₁、S₂、S₃(半径均为 1),其中 S₁ 和 S₃ 染成红色,S₂ 染成蓝色。那么对于每一对同色点(均在红色区域中),它们之间的夹角最多为 120°,因此两点之间的距离 ≤ √3(最大距离出现在两个点分别位于各自扇形边界上、夹角为 120° 时)。因此,不存在一对同色点,其距离恰好为 d > √3。因此在任何染色方案中都不存在距离为 d 的同色点对。这说明上界至多为 √3。
因此,该上界恰好为 √3。
我们还可以指出,该上界是紧的:当 d = √3 时,无法再避免单色距离的出现,即任何一个等边三角形的顶点都会导致出现一对同色点。
因此答案为:√3。
但需注意:题目所问“任意染色后必然存在一对同色点,其距离恰好为 d。求 d 的上界”——可能他们希望得到上确界,即 √3。这里的“上界”指的是使该命题对所有染色都成立的最大 d 值,因此答案为:√3。
或者,他们也可能是在询问最小的这样的上界?但“上界”通常指的是上确界,因此答案仍是 √3。
我们还应指出,这一结果被称为“Erdos–Moser 问题”或“单位圆盘内距离的上确界”,答案是 √3。
我们应清晰地表述:
证明:
- 对任意 d ≤ √3,在半径为1的圆盘中可以放置一个边长为 d 的正三角形。对该三角形的三顶点任意红蓝着色,必有两顶点同色,而这两点之间的距离恰好是 d。于是对任意 d ≤ √3,命题成立。
- 对于任意 d > √3,给出一种不含单色距离 d 的染色。把圆盘分成三个中心角均为 120° 的扇形 S₁、S₂、S₃(依次排列),把 S₁、S₃ 染成红色,S₂ 染成蓝色。设两点 p、q 同色且均落在红色区域,则它们的极角之差至多为 120°,因而在单位圆盘内的距离不超过 √3。同理蓝色区域中的任意两点距离也不超过 √3。因此在这类着色下不存在距离为 d (>√3) 的同色点。
因此,使得命题对所有红蓝染色都成立的最大 d 正好是 √₃。即 d 的上界(上确界)为 √3。
如果想更全面,还可以指出,当 d = √3 时命题仍然成立(因为上面的构造在 d = √3 时仍然存在一对同色点)。所以该上界是紧的。
因此最终答案为 d_max = √3。
考虑过 d = √3 的情况
- 是否存在一种染色方式,使得不存在距离恰好为 √3 的单色点对?我们之前的染色方案表明,存在多个距离为 √3 的红色点对(例如位于扇区边界上的点)。因此该染色方案在 d = √3 时产生了正面对。但是否存在另一种不同的染色方案可以避免?可能不存在,但必须始终存在这样的一对点;我们的构造仅是一种存在性证明,而非不可能性的反例。因此 d = √3 是不可避免的。
综上所述,答案成立。
现在配合解释给出最终答案。
答案:
dmax=3 1. 下界(必然出现的距离)
设 ∣d∣≤3 。把边长为 d 的正三角形放在单位圆盘内部是可行的:只要把三角形的中心放在圆盘的中心,顶点到中心的距离为
R=3d≤1. 于是正三角形的三个顶点均在单位圆盘里。
对这三点任意进行红‑蓝染色,只有两种颜色,而根据抽屉原理必有两顶点同色。同色的两点恰好相距 d 。
对这三点任意进行红‑蓝染色,只有两种颜色,而根据抽屉原理必有两顶点同色。同色的两点恰好相距 d 。
因此,对所有 d≤3 ,任意二染色都必然出现一对同色点,其距离恰为 d 。
这说明
dmax≥3. 这说明
2. 上界(可以避免的临界距离)
设 d>3 。把单位圆盘划分为三个中心角均为 120∘ 的扇形
S1,S2,S3 (按逆时针方向依次排列)。
S1,S2,S3 (按逆时针方向依次排列)。
- 把 S1 与 S3 染成 红色,
- 把中间的 S2 染成 蓝色。
下面说明在这种染色下不存在两同色点的距离恰为 d 。
取任意两点 P,Q 同色。若它们都在蓝色区域 S2 中,则它们的极角之差不超过 120∘ 。
设两点离中心的距离分别为 rP,rQ≤1 ,则它们的欧氏距离
∣PQ∣=rP2+rQ2−2rPrQcosΔθ≤12+12−2⋅1⋅1cos120∘=3. 设两点离中心的距离分别为 rP,rQ≤1 ,则它们的欧氏距离
同理,若 P,Q 都在红色区域(S1 或 S3 )中,极角之差同样不超过 120∘ ,于是 ∣PQ∣≤3 。
于是 任意两同色点的距离至多为 3 。因为事先取定的 d>3 ,在这种染色下根本不存在两同色点的距离恰为 d 。
因此,当 d>3 时,存在一种二染色使得没有同色点对的距离恰好是 d 。这说明
dmax≤3. 3. 结论
结合上下界得到
dmax=3. - 对于所有 d≤3 ,任意红‑蓝染色必有一对同色点相距恰为 d (等边三角形的抽屉原理)。
- 对于任何 d>3 ,上述把圆盘分成三个 120∘ 扇形并交替染色的方案可以避免出现同色点对的距离恰为 d 。
因此,题目所求的“上界”正是 3 ,即在该值(及以下)必定出现同色点对的距离,而超过该值则可以有染色方式避免。