主題
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. 貢獻 (作者連結)

使用 探索

參考文獻

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. "稀疏標尺。" 來自 -- 資源,由 Eric W. Weisstein 建立。 https://mathworld.tw/SparseRuler.html

主題分類