稀疏尺（Sparse ruler）指的是去掉了一些刻度的尺子。抽象来说，一个长度为L，有m个刻度的稀疏尺可以被记为整数序列a_1, a_2, ..., a_m(0 = a_1 )。刻度a_1和a_m对应尺子的首尾。为了能够测量长度K（0\le K\le L），我们需要存在刻度a_i,a_j使得a_j-a_i=K 。
如果一个稀疏尺能够测量不超过它的长度的任意整数长度，称这个稀疏尺是完全的。对于一个完全稀疏尺，如果不存在另一个长度相同但刻度数量更少的完全稀疏尺，则称它是最小稀疏尺。类似的，如果不存在另一个刻度数量相同但长度更大的稀疏尺，则称它是最大稀疏尺。如果一个稀疏尺既是最大稀疏尺，又是最小稀疏尺，则称它是最优稀疏尺。
对于m个刻度，不同的刻度组合共有m(m-1)/2 种，因此这是长度L的理论上界。事实上，只有在2、3或4个刻度的情况下可以取到该上界。对于更多的刻度数量，最优长度和理论上界的差距非均匀地逐渐增大。
例如，对于 6 个刻度的稀疏尺，理论上界为 15，但实际上的最大长度为 13。长度为13，刻度数为6的稀疏尺有三种可能的刻度选择。其中之一是是 {0, 1, 2, 6, 10, 13}。例如，要测量7的长度，可以使用这把尺子的刻度6和13。
格伦布尺是一种要求所有的a_j-a_i都不相等的稀疏尺。通常，m个刻度的格伦布尺将比m个刻度的最佳稀疏尺长得多，因为m(m-1)/2是格伦布尺长度的下界。比较长的格伦布尺可能有间隙，换句话说，它可能有无法测量的距离。例如，最优格伦布尺 {0, 1, 4, 10, 12, 17} 的长度为 17，但它无法测量长度 14 或 15。
威希曼尺
许多最优尺符合以下形式：
W(r,s) = 1^r, r+1, (2r+1)^r, (4r+3)^s, (2r+2)^{(r+1)}, 1^r,
a^b代表b段长度为a的间隔。因此，如果r = 1，s = 2 ，则W(1,2)有（按顺序）：
1段长度为1的间隔，
1段长度为2的间隔，
1段长度为3的间隔，
2段长度为7的间隔，
2段长度为4的间隔，
1段长度为1的间隔。
对应稀疏尺 {0, 1, 3, 6, 13, 20, 24, 28, 29}。威希曼尺的长度为4r(r+s+2)+3(s+1)，刻度数为4r+s+3 。需要注意的是，并非所有 威希曼尺都是最优稀疏尺，且并非所有最优稀疏尺都可以通过这种方式得到。长度为 1、13、17、23 和 58 的最优稀疏尺均不符合该形式。如果 Peter Luschny 的最优尺猜想为真，则最长的不符合该形式的最优稀疏尺长度为58。目前为止，该猜想在长度为 213以下均被验证为真。
渐近分析
For every n let l(n) be the smallest number of marks for a ruler of length n. For example, l(6)=4. The asymptotic of the function l(n) was studied by Erdos, Gal (1948) and continued by Leech (1956) who proved that the limit \lim_{n\to\infty}{l(n)^2}/n exists and is lower and upper bounded by
2+\tfrac{4}{3\pi}=2.424...
Much better upper bounds exist for n-perfect rulers. Those are subsets A of \mathbb N such that each positive number k\le n can be written as a difference k=a-b for some a,b\in A. For every number n let k(n) be the smallest cardinality of an n-perfect ruler. It is clear that k(n)\le l(n). The asymptotics of the sequence k(n) was studied by Redei, Renyi (1949) and then by Leech (1956) and Golay (1972). Due to their efforts the following upper and lower bounds were obtained:
\max_{0
Define the excess as E(n) = l(n)- \lceil \sqrt{3 n+\tfrac{9}{4}} \rfloor. In 2020, Pegg proved by construction that E(n) ≤ 1 for all lengths n. If the Optimal Ruler Conjecture is true, then E(n) = 0 | 1 for all n, leading to the ″dark mills″ pattern when arranged in columns, OEIS A326499. None of the best known sparse rulers n > 213 are proven minimal as of Sep 2020. Many of the current best known E = 1 constructions for n > 213 are believed to non-minimal, especially the "cloud" values.
例子
以下是一些最小稀疏尺的例子。高亮标出了最优尺。如果要列出的内容太多，则不会全部包含在内。不包括镜像。
非完全稀疏尺
有些非完全尺可以完全测量比具有相同标记数量的最优稀疏尺更长的距离。 \{0, 2, 7, 14, 15, 18, 24\}, \{0, 2, 7, 13, 16, 17, 25\}, \{0, 5, 7, 13, 16, 17, 31\} ， 和\{0, 6, 10, 15, 17, 18, 31\}，这些非完全尺最多可以测量 18 个不同的长度，但 7 个刻度的最优稀疏尺最多只能测量 17 个不同长度。
下表列出了一些非完全尺，最多有 13 个刻度。不包括镜像。能够测量的不同长度数量比最优稀疏尺还要多的非完全尺被高亮标出。
参考资料
评论 (0)