稀疏标尺是一种 标尺,其整数长度为 ,并具有最少的
刻度,允许测量所有距离 1, 2, 3, 4, ... 直到
(可能重复)。 因此,它们与 Gardner (1985, pp. 65-67 和 261-262) 所考虑的标尺类型非常相似。
考虑一个长度为 13 的稀疏标尺。 显然,五个刻度是不够的,因为可能的刻度之间最多有 个差值。 另一方面,六个刻度就足够了,但由于这会产生
个差值,因此必须有两个重复值。 这样一组刻度的示例是
0, 1, 6, 9, 11, 和 13
,它给出了高达 13 的所有距离,但包括距离 2 和 5 各两次 (
和
;
和
)。 事实上,对于五个或更多刻度,不存在 完美 稀疏标尺,即唯一测量直至其长度的所有距离的稀疏标尺 (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
。 像这样具有重复值的标尺有一个缩写形式,写为
。 这种表示法导致了主要的
和次要的
Wichmann 构造
具有 个刻度的 Wichmann 标尺的最大长度为
。 对于
, 2, ...,这些长度为 3, 6, 9, 12, 15, 22, 29, 36, 43, 50, 57, 68, 79, ... (A289761)。 最优稀疏标尺对于给定数量的刻度具有最大长度。 除了长度为 1、13、17、23 和 58 (A349978) 之外,所有已知的最优稀疏标尺都是 Wichmann 构造。 最优标尺猜想认为,除这些例外情况外,所有最优稀疏标尺都是 Wichmann 构造。
长度为 的稀疏标尺具有
个刻度,其中
称为超额量,等于 0 或 1。
对于
, 51, ... 的值由 1, 0, 0, 0, 0, 0, 0, 0, 1, ... (A326499) 给出,这是一个偏移量为 50 的序列,因为对于所有
而言
。 计算机搜索的难度随着长度呈指数级增长。 事实上,甚至没有排除超额量对于某些 (较大) 的
值可能是
的可能性。
主要的和次要的 Wichmann 构造彼此之间是简单的修改,并且大多数解决方案可以通过多种方式进行修改。 对于超过 880 个刻度,在 Wichmann 构造的末尾添加单个刻度可以为任何大于 257992 的长度产生超额量为 0 或 1 的解决方案。 这使得稀疏标尺在组合数学问题中显得不寻常,因为较小(而非较大)的情况最难找到,其中长度为 1792 的稀疏标尺尤其具有挑战性。
绘制最大 Wichmann 标尺批次中的超额值导致了一种模式,N. J. A. Sloane 称之为“阴天下的黑暗撒旦磨坊”。 黑暗磨坊中的所有窗口都是 Wichmann 构造。 由于这种模式,人们认为 Wichmann (1963) 解决了这个问题,并带有上述警告。