查看“︁稀疏尺”︁的源代码

{{Translating|[[:en:Sparse_ruler]]||tpercent=80|time=2023-06-26T15:21:41+00:00}}

'''稀疏尺'''（Sparse ruler）指的是去掉了一些刻度的尺子。抽象来说，一个长度为<math>L</math>，有<math>m</math>个刻度的稀疏尺可以被记为整数序列<math>a_1, a_2, ..., a_m</math>(<math>0 = a_1 < a_2 < ... < a_m = L</math>)。刻度<math>a_1</math>和<math>a_m</math>对应尺子的首尾。为了能够测量长度<math>K</math>（<math>0\le K\le L</math>），我们需要存在刻度<math>a_i</math>,<math>a_j</math>使得<math>a_j-a_i=K</math> 。

如果一个稀疏尺能够测量不超过它的长度的任意整数长度，称这个稀疏尺是'''完全的'''。对于一个完全稀疏尺，如果不存在另一个长度相同但刻度数量更少的完全稀疏尺，则称它是最小稀疏尺。类似的，如果不存在另一个刻度数量相同但长度更大的稀疏尺，则称它是最大稀疏尺。如果一个稀疏尺既是最大稀疏尺，又是最小稀疏尺，则称它是最优稀疏尺。

对于<math>m</math>个刻度，不同的刻度组合共有<math>m(m-1)/2</math> 种，因此这是长度<math>L</math>的理论上界。事实上，只有在2、3或4个刻度的情况下可以取到该上界。对于更多的刻度数量，最优长度和理论上界的差距非均匀地逐渐增大。

例如，对于 6 个刻度的稀疏尺，理论上界为 15，但实际上的最大长度为 13。长度为13，刻度数为6的稀疏尺有三种可能的刻度选择。其中之一是是 {0, 1, 2, 6, 10, 13}。例如，要测量7的长度，可以使用这把尺子的刻度6和13。

[[哥隆尺问题|格伦布尺]]是一种要求所有的<math>a_j-a_i</math>都不相等的稀疏尺。通常，<math>m</math>个刻度的格伦布尺将比<math>m</math>个刻度的最佳稀疏尺长得多，因为<math>m(m-1)/2</math>是格伦布尺长度的下界。比较长的格伦布尺可能有间隙，换句话说，它可能有无法测量的距离。例如，最优格伦布尺 {0, 1, 4, 10, 12, 17} 的长度为 17，但它无法测量长度 14 或 15。

=== 威希曼尺 ===
许多最优尺符合以下形式：

<math>W(r,s) = 1^r, r+1, (2r+1)^r, (4r+3)^s, (2r+2)^{(r+1)}, 1^r,</math>

<math>a^b</math>代表<math>b</math>段长度为<math>a</math>的间隔。因此，如果<math>r = 1</math>，<math>s = 2</math> ，则<math>W(1,2)</math>有（按顺序）：

1段长度为1的间隔，

1段长度为2的间隔，

1段长度为3的间隔，

2段长度为7的间隔，

2段长度为4的间隔，

1段长度为1的间隔。

对应稀疏尺 {0, 1, 3, 6, 13, 20, 24, 28, 29}。威希曼尺的长度为<math>4r(r+s+2)+3(s+1)</math>，刻度数为<math>4r+s+3</math> 。需要注意的是，并非所有 威希曼尺都是最优稀疏尺，且并非所有最优稀疏尺都可以通过这种方式得到。长度为 1、13、17、23 和 58 的最优稀疏尺均不符合该形式。如果 Peter Luschny 的[[oeis:wiki/User:Peter_Luschny/PerfectRulers#The_optimal_ruler_conjecture|最优尺猜想]]为真，则最长的不符合该形式的最优稀疏尺长度为58。目前为止，该猜想在长度为 213以下均被验证为真。 <ref>Robison, A. D. Parallel Computation of Sparse Rulers. Intel Developer Zone. https://web.archive.org/web/20210330141047/https://software.intel.com/content/www/us/en/develop/articles/parallel-computation-of-sparse-rulers.html</ref>

=== 渐近分析 ===

{{TransH}}
For every <math>n</math> let <math>l(n)</math> be the smallest number of marks for a ruler of length <math>n</math>. For example, <math>l(6)=4</math>. The asymptotic of the function <math>l(n)</math> was studied by Erdos, Gal<ref>Erdös, P.; Gál, I. S. On the representation of <math>1, 2,\cdots, N</math> by differences. Nederl. Akad. Wetensch., Proc. '''51''' (1948) 1155--1158 = Indagationes Math. '''10''', 379--382 (1949)</ref> (1948) and continued by Leech<ref>Leech, John. On the representation of <math>1,2,\cdots,n</math> by differences. J. London Math. Soc. 31 (1956), 160--169</ref> (1956) who proved that the limit <math>\lim_{n\to\infty}{l(n)^2}/n</math> exists and is lower and upper bounded by<br> <math>2+\tfrac{4}{3\pi}=2.424...<2.434...=\max_{0<\theta<2\pi}2(1-\tfrac{\sin(\theta)}{\theta})\le \lim_{n\to\infty}\frac{l(n)^2}n \le\frac{375}{112}=3.348...</math>

Much better upper bounds exist for <math>n</math>-perfect rulers. Those are subsets <math>A</math> of <math>\mathbb N</math> such that each positive number <math>k\le n</math> can be written as a difference <math>k=a-b</math> for some <math>a,b\in A</math>. For every number <math>n</math> let <math>k(n)</math> be the smallest cardinality of an <math>n</math>-perfect ruler. It is clear that <math>k(n)\le l(n)</math>. The asymptotics of the sequence <math>k(n)</math> was studied by Redei, Renyi<ref>Redei, L.; Ren′i, A. On the representation of the numbers <math>1,2,\cdots, N</math> by means of differences. (Russian) Mat. Sbornik N.S. 24(66), (1949). 385--389.</ref> (1949) and then by Leech (1956) and Golay<ref>Golay, Marcel J. E. Notes on the representation of <math>1,\,2,\,\ldots ,\,n</math> by differences. J. London Math. Soc. (2) 4 (1972), 729--734.</ref> (1972). Due to their efforts the following upper and lower bounds were obtained:<br> <math>
\max_{0<\theta<2\pi}2(1-\tfrac{\sin(\theta)}{\theta})\le \lim_{n\to\infty}\frac{k(n)^2}n=\inf_{n\in\mathbb N}\frac{k(n)^2}n\le\frac{128^2}{6166}=2.6571...<\frac83.</math>

Define the excess as <math>E(n) = l(n)- \lceil \sqrt{3 n+\tfrac{9}{4}} \rfloor</math>. In 2020, Pegg proved by construction that <math>E(n)</math> ≤ 1 for all lengths <math>n</math>.<ref>Pegg, E. Hitting All the Marks: Exploring New Bounds for Sparse Rulers and a Wolfram Language Proof. https://blog.wolfram.com/2020/02/12/hitting-all-the-marks-exploring-new-bounds-for-sparse-rulers-and-a-wolfram-language-proof/ {{Wayback|url=https://blog.wolfram.com/2020/02/12/hitting-all-the-marks-exploring-new-bounds-for-sparse-rulers-and-a-wolfram-language-proof/ |date=20230626152152 }}</ref> If the Optimal Ruler Conjecture is true, then <math>E(n) = 0 | 1</math> for all <math>n</math>, leading to the ″dark mills″ pattern when arranged in columns, OEIS A326499.<ref name=oeis>{{Cite OEIS|1=A326499}}</ref> None of the best known sparse rulers <math>n > 213</math> are proven minimal as of Sep 2020. Many of the current best known <math>E = 1</math> constructions for <math>n > 213</math> are believed to non-minimal, especially the "cloud" values.

{{Gallery|height=200|width=360
|File:Sparseruler.png|Fig 1. Light numbers +0, dark numbers +1 for the minimal mark excess pattern in a sparse ruler. All minimal values to length 213 are proven.
|File:Darkmills.png|Fig 2. "Dark mills on a cloudy day"  -- N. J. A. Sloane.  Excess pattern for sparse rulers, best known values for L>213.
}}

{{TransF}}

=== 例子 ===
以下是一些最小稀疏尺的例子。高亮标出了最优尺。如果要列出的内容太多，则不会全部包含在内。不包括镜像。
{| class="wikitable" border="1"
!长度
!刻度数
!数量
!例子
|- style="background:#dedeff"
|1
|2
|1
|II
|-
|2
|3
|1
|III
|- style="background:#dedeff"
|3
|3
|1
|II.I
|-
|4
|4
|2
|III.I
II.II
|-
|5
|4
|2
|III..I
II.I.I
|- style="background:#dedeff"
|6
|4
|1
|II..I.I
|-
|7
|5
|6
|IIII...I
III.I..I
III..I.I
II.I.I.I
II.I..II
II..II.I
|-
|8
|5
|4
|III..I..I
II.I...II
II..I.I.I
II...II.I
|- style="background:#dedeff"
|9
|5
|2
|III...I..I
II..I..I.I
|-
|10
|6
|19
|IIII..I...I
|-
|11
|6
|15
|IIII...I...I
|-
|12
|6
|7
|IIII....I...I
III...I..I..I
II.I.I.....II
II.I...I...II
II..II....I.I
II..I..I..I.I
II.....II.I.I
|- style="background:#dedeff"
|13
|6
|3
|III...I...I..I
II..II.....I.I
II....I..I.I.I
|-
|14
|7
|65
|IIIII....I....I
|-
|15
|7
|40
|II.I..I...I...II
II..I..I..I..I.I
|-
|16
|7
|16
|IIII....I...I...I
|- style="background:#dedeff"
|17
|7
|6
|IIII....I....I...I
III...I...I...I..I
III.....I...I.I..I
III.....I...I..I.I
II..I.....I.I..I.I
II......I..I.I.I.I
|-
|18
|8
|250
|II..I..I..I..I..I.I
|-
|19
|8
|163
|IIIII....I....I....I
|-
|20
|8
|75
|IIIII.....I....I....I
|-
|21
|8
|33
|IIIII.....I.....I....I
|-
|22
|8
|9
|IIII....I....I....I...I
III.......I....I..I..II
II.I.I........II.....II
II.I..I......I...I...II
II.I.....I.....I...II.I
II..II......I.I.....I.I
II....II..I.......I.I.I
II....I..I......I.I.I.I
II.....II........II.I.I
|- style="background:#dedeff"
|23
|8
|2
|III........I...I..I..I.I
II..I.....I.....I.I..I.I
|-
|24
|9
|472
|IIIIII......I.....I.....I
|-
|25
|9
|230
|IIIIII......I......I.....I
|-
|26
|9
|83
|IIIII.....I....I.....I....I
|-
|27
|9
|28
|IIIII.....I.....I.....I....I
|-
|28
|9
|6
|III..........I....I..I..I..II
II.I.I.I..........II.......II
II.I..I..I......I......I...II
II.I.....I.....I.....I...II.I
II.....I...I........I..I.II.I
II.......II..........II.I.I.I
|- style="background:#dedeff"
|29
|9
|3
|III...........I...I..I..I..I.I
II.I..I......I......I...I...II
II..I.....I.....I.....I.I..I.I
|-
|35
|10
|5
|III..............I...I..I..I..I..I.I
II.I..I..I......I......I......I...II
II.I..I..I.........I...I......I...II
II..II..........I.I......I.I.....I.I
II..I.....I.....I.....I.....I.I..I.I
|- style="background:#dedeff"
|36
|10
|1
|II.I..I......I......I......I...I...II
|- style="background:#dedeff"
|43
|11
|1
|II.I..I......I......I......I......I...I...II
|-
|46
|12
|342
|III..I....I....I..........I.....I.....I.....III
|- style="background:#dedeff"
|50
|12
|2
|IIII...................I....I...I...I...I...I..I..I
II.I..I......I......I......I......I......I...I...II
|-
|57
|13
|12
|III..I....I....I..........I..........I.....I.....I.....III
II.I..I......I......I......I......I......I......I...I...II
|- style="background:#dedeff"
|58
|13
|6
|IIII.......................I....I...I...I...I...I...I..I..I
III...I.I........I........I........I........I..I......I..II
III.....I......II.........I.........I.........I..I...I.I..I
II.I..I..........I..I......I.......I.........I...I...I...II
II.I..I..........I......I..I..........I......I...I...I...II
II...I..I...I........I........I........I........I....II.I.I
|- style="background:#dedeff"
|68
|14
|2
|III..I....I....I..........I..........I..........I.....I.....I.....III
III.....I......II.........I.........I.........I.........I..I...I.I..I
|- style="background:#dedeff"
|79
|15
|1
|III..I....I....I..........I..........I..........I..........I.....I.....I.....III
|- style="background:#dedeff"
|90
|16
|1
|<small>III..I....I....I..........I..........I..........I..........I..........I.....I.....I.....III</small>
|- style="background:#dedeff"
|101
|17
|1
|<small>III..I....I....I..........I..........I..........I..........I..........I..........I.....I.....I.....III</small>
|- style="background:#dedeff"
|112
|18
|1
|<small>III..I....I....I..........I..........I..........I..........I..........I..........I..........I.....I.....I.....III</small>
|- style="background:#dedeff"
|123
|19
|2
|<small>IIII...I......I......I......I..............I..............I..............I..............I.......I.......I.......I.......IIII</small>
<small>III..I....I....I..........I..........I..........I..........I..........I..........I..........I..........I.....I.....I.....III</small>
|- style="background:#dedeff"
|138
|20
|1
|<small>IIII...I......I......I......I..............I..............I..............I..............I..............I.......I.......I.......I.......IIII</small>
|}

=== 非完全稀疏尺 ===
有些非完全尺可以完全测量比具有相同标记数量的最优稀疏尺更长的距离。 <math>\{0, 2, 7, 14, 15, 18, 24\}</math>, <math>\{0, 2, 7, 13, 16, 17, 25\}</math>, <math>\{0, 5, 7, 13, 16, 17, 31\}</math> ， 和<math>\{0, 6, 10, 15, 17, 18, 31\}</math>，这些非完全尺最多可以测量 18 个不同的长度，但 7 个刻度的最优稀疏尺最多只能测量 17 个不同长度。

下表列出了一些非完全尺，最多有 13 个刻度。不包括镜像。能够测量的不同长度数量比最优稀疏尺还要多的非完全尺被高亮标出。
{| class="wikitable"
!刻度数
!长度
!可测长度
!Ruler
|- style="background:#dedeff"
|7
|24
|18
|{0, 2, 7, 14, 15, 18, 24}
|-
|7
|25
|18
|{0, 2, 7, 13, 16, 17, 25}
|-
|7
|31
|18
|{0, 5, 7, 13, 16, 17, 31}
|-
|7
|31
|18
|{0, 6, 10, 15, 17, 18, 31}
|- style="background:#dedeff"
|8
|39
|24
|{0, 8, 15, 17, 20, 21, 31, 39}
|- style="background:#dedeff"
|10
|64
|37
|{0, 7, 22, 27, 28, 31, 39, 41, 57, 64}
|-
|10
|73
|37
|{0, 16, 17, 28, 36, 42, 46, 49, 51, 73}
|- style="background:#dedeff"
|11
|68
|44
|{0, 7, 10, 27, 29, 38, 42, 43, 44, 50, 68}
|- style="background:#dedeff"
|11
|91
|45
|{0, 18, 19, 22, 31, 42, 48, 56, 58, 63, 91}
|- style="background:#dedeff"
|12
|53
|51
|{0, 2, 3, 6, 9, 17, 25, 33, 41, 46, 51, 53}
|-
|12
|60
|51
|{0, 5, 9, 13, 19, 26, 33, 48, 49, 50, 51, 60}
|-
|12
|73
|51
|{0, 2, 3, 10, 17, 23, 35, 42, 46, 47, 51, 73}
|-
|12
|75
|51
|{0, 2, 10, 13, 29, 33, 36, 45, 50, 51, 57, 75}
|-
|12
|82
|51
|{0, 8, 28, 31, 34, 38, 45, 47, 49, 50, 74, 82}
|-
|12
|83
|51
|{0, 2, 10, 24, 25, 29, 36, 42, 45, 73, 75, 83}
|-
|12
|85
|51
|{0, 8, 10, 19, 35, 41, 42, 47, 55, 56, 59, 85}
|-
|12
|87
|51
|{0, 12, 24, 26, 37, 39, 42, 43, 46, 47, 75, 87}
|- style="background:#dedeff"
|13
|61
|59
|{0, 2, 3, 6, 9, 17, 25, 33, 41, 49, 54, 59, 61}
|-
|13
|69
|59
|{0, 6, 10, 15, 22, 30, 38, 55, 56, 57, 58, 59, 69}
|-
|13
|69
|59
|{0, 6, 11, 15, 22, 30, 38, 55, 56, 57, 58, 59, 69}
|-
|13
|82
|59
|{0, 4, 5, 9, 25, 27, 39, 42, 50, 53, 56, 63, 82}
|-
|13
|83
|59
|{0, 1, 2, 24, 34, 36, 38, 43, 51, 54, 57, 82, 83}
|-
|13
|88
|59
|{0, 1, 3, 9, 16, 26, 36, 40, 47, 54, 58, 59, 88}
|-
|13
|88
|59
|{0, 1, 5, 29, 34, 36, 47, 48, 50, 56, 58, 73, 88}
|-
|13
|90
|59
|{0, 7, 12, 16, 37, 38, 43, 55, 56, 57, 58, 66, 90}
|-
|13
|91
|59
|{0, 5, 9, 12, 16, 32, 38, 42, 55, 56, 57, 63, 91}
|-
|13
|92
|59
|{0, 6, 10, 13, 25, 34, 39, 54, 55, 56, 57, 65, 92}
|-
|13
|94
|59
|{0, 1, 3, 16, 28, 37, 45, 48, 54, 55, 59, 78, 94}
|-
|13
|95
|59
|{0, 4, 32, 37, 38, 40, 48, 53, 54, 56, 63, 83, 95}
|-
|13
|96
|59
|{0, 3, 7, 27, 37, 39, 50, 55, 56, 58, 72, 81, 96}
|-
|13
|101
|59
|{0, 4, 24, 37, 43, 45, 52, 54, 55, 59, 77, 81, 101}
|-
|13
|108
|59
|{0, 8, 17, 40, 50, 53, 64, 65, 69, 71, 91, 99, 108}
|- style="background:#dedeff"
|13
|113
|61
|{0, 6, 22, 36, 45, 47, 57, 60, 64, 65, 91, 97, 113}
|-
|13
|133
|60
|{0, 26, 29, 40, 42, 46, 67, 74, 79, 89, 97, 98, 133}
|}

==参考资料==
{{refs}}

[[Category:数论]]
[[Category:尺子]]
[[Category:组合数学]]