主题
Search

稀疏标尺


稀疏标尺是一种 标尺,其整数长度为 n,并具有最少的 k 刻度,允许测量所有距离 1, 2, 3, 4, ... 直到 n (可能重复)。 因此,它们与 Gardner (1985, pp. 65-67 和 261-262) 所考虑的标尺类型非常相似。

考虑一个长度为 13 的稀疏标尺。 显然,五个刻度是不够的,因为可能的刻度之间最多有 (5; 2)=10 个差值。 另一方面,六个刻度就足够了,但由于这会产生 (6; 2)=15 个差值,因此必须有两个重复值。 这样一组刻度的示例是 {0, 1, 6, 9, 11, 和 13},它给出了高达 13 的所有距离,但包括距离 2 和 5 各两次 (11-913-11; 6-111-6)。 事实上,对于五个或更多刻度,不存在 完美 稀疏标尺,即唯一测量直至其长度的所有距离的稀疏标尺 (Golomb 1972; Gardner 1983, p. 154)。

稀疏标尺出现在 Erdős 和 Gál (1949) 的差分表示问题中。 寻找给定长度的稀疏标尺的问题部分由 Leech (1956) 解决,主要由 Wichmann (1963) 解决。 然而,直到 Robinson (2014) 和 Pegg (2020) 进行现代计算机分析后,Wichmann 解决方案的强大之处才被认识到。

一个稀疏标尺的例子可以通过刻度 {0, 1, 2, 3, 27, 32, 36, 40, 44, 48, 52, 55, 58} 给出,刻度之间的差值为 {1, 1, 1, 24, 5, 4, 4, 4, 4, 4, 3, 3}。 像这样具有重复值的标尺有一个缩写形式,写为 1^324^15^14^53^2。 这种表示法导致了主要的 W(r,s) 和次要的 w(r,s) Wichmann 构造

 W(r,s)=1^r,r+1,(2r+1)^r,(4r+3)^s,(2r+2)^(r+1),1^r
 w(r,s)=1^r,r+1,(2r+1)^(r+1),(4r+3)^s,(2r+2)^r,1^r.

具有 k 个刻度的 Wichmann 标尺的最大长度为 (k^2-(k (mod 6)-3)^2)/3+k。 对于 k=1, 2, ...,这些长度为 3, 6, 9, 12, 15, 22, 29, 36, 43, 50, 57, 68, 79, ... (A289761)。 最优稀疏标尺对于给定数量的刻度具有最大长度。 除了长度为 1、13、17、23 和 58 (A349978) 之外,所有已知的最优稀疏标尺都是 Wichmann 构造。 最优标尺猜想认为,除这些例外情况外,所有最优稀疏标尺都是 Wichmann 构造。

长度为 n 的稀疏标尺具有 nint(sqrt(3n+9/4))+E 个刻度,其中 E 称为超额量,等于 0 或 1。 E(n) 对于 n=50, 51, ... 的值由 1, 0, 0, 0, 0, 0, 0, 0, 1, ... (A326499) 给出,这是一个偏移量为 50 的序列,因为对于所有 n<=49 而言 E=0 。 计算机搜索的难度随着长度呈指数级增长。 事实上,甚至没有排除超额量对于某些 (较大) 的 N 值可能是 E=-1 的可能性。

主要的和次要的 Wichmann 构造彼此之间是简单的修改,并且大多数解决方案可以通过多种方式进行修改。 对于超过 880 个刻度,在 Wichmann 构造的末尾添加单个刻度可以为任何大于 257992 的长度产生超额量为 0 或 1 的解决方案。 这使得稀疏标尺在组合数学问题中显得不寻常,因为较小(而非较大)的情况最难找到,其中长度为 1792 的稀疏标尺尤其具有挑战性。

DarkSatanicMillsOnACloudyDay

绘制最大 Wichmann 标尺批次中的超额值导致了一种模式,N. J. A. Sloane 称之为“阴天下的黑暗撒旦磨坊”。 黑暗磨坊中的所有窗口都是 Wichmann 构造。 由于这种模式,人们认为 Wichmann (1963) 解决了这个问题,并带有上述警告。


另请参阅

阴天下的黑暗撒旦磨坊, 戈隆标尺, 优美标号, 标尺, 维奇曼标尺

此条目由 Ed Pegg, Jr. 贡献 (作者链接)

使用 Wolfram|Alpha 探索

参考文献

Erdős, P. 和 Gál, I. S. "关于用差分表示 1,2,...,N。" Proc. Nederl. Akad. Wetensch. 51, 1155-1158, 1948. 也发表为 Indagationes Math. 10, 379-382, 1949。Gardner, M. 轮子、生命和其他数学娱乐。 New York: W. H. Freeman, pp. 153-155, 1983。Gardner, M. Dr. Matrix 的魔术数字。 Buffalo, NY: Prometheus, pp. 65-67 和 261-262, 1985。Golomb, S. W. "如何给图编号。" 收录于 图论与计算 (Ed. R. C. Read)。 New York: Academic Press, pp. 23-37, 1972。Granville, A. 和 Roesler, F. "给定集合的差分集。" Amer. Math. Monthly 106, 338-344, 1999。Leech, J. "关于用差分表示 1,2,...,N。" J. London Math. Soc. 31, 160-169, 1956。Pegg, E. "击中所有刻度:探索稀疏标尺的新界限和 Wolfram 语言证明。" 2020. https://blog.wolfram.com/2020/02/12/hitting-all-the-marks-exploring-new-bounds-for-sparse-rulers-and-a-wolfram-language-proof/Pegg, E. Jr. "Excess01Ruler。" Wolfram Function Repository. https://resources.wolframcloud.com/FunctionRepository/resources/Excess01Ruler/Pegg, E. Jr. "稀疏标尺。" Wolfram Demonstrations Project. 2019. https://demonstrations.wolfram.com/SparseRulers/Pegg, E. Jr. "类维奇曼标尺。" Wolfram Demonstrations Project. 2019. https://demonstrations.wolfram.com/WichmannLikeRulers/Robison, A. D. "稀疏标尺的并行计算。" 2014。Saarela, A. 和 Vanhatalo, A. "无边界部分词与稀疏标尺之间的联系。" 2024 年 8 月 29 日. https://arxiv.org/abs/2408.16335Sloane, N. J. A. “整数序列在线百科全书”中的序列 A289761, A326499, 和 A349978Wichmann, B. "关于受限差分基的注释。" J. Lond. Math. Soc. 38, 465-466, 1963。

引用为

Pegg, Ed Jr. "稀疏标尺。" 来自 MathWorld -- Wolfram Web 资源,由 Eric W. Weisstein 创建。 https://mathworld.net.cn/SparseRuler.html

主题分类