介绍一个数学中非常有趣，有点搞笑又有点意外的问题：稀疏尺问题。

这里的“稀疏”是指尺子的刻度稀疏。你有没有想过，一把尺子上的刻度中，有很多是不必要的。

比如，一把长 10 厘米的尺子，如果只要求量出整数厘米的长度，那么这把尺就只需要在 0,1,3,7,8,10 厘米处，这 6 个位置有刻度可以了。

如果要量 1 厘米的长度，就把被测物体放在 0 和 1 两个刻度之间。量 2 厘米，那么就是 0 和 2 两个刻度之间。需要量 3 厘米时，虽然在 3 厘米处没有刻度，但可以把被测物体放在 7 和 10 厘米刻度之间，这样就得到了 3 厘米。

量 4 厘米的话，可以把被测物体放在 3 和 7 厘米之间；5 厘米的话，放在 3 和 8 厘米之间等等。请自行验证，用以上这样一把尺子，可以量出全部的，1 到 10 厘米的整数长度。

这把尺子刻度虽然“稀疏”，但确实是一把合格的尺子。能够看出，问题的要点在于，对任何一个被测的整数，需要找到两个数字，使得它们的差等于这个数字。当然，我们希望刻度越稀疏越好，因为刻度越多越没有难度，不稀奇嘛。

那我们可以在脑子里，构造另一个长度的稀疏尺，来加深一下理解。比如，我们要构造一把长度为 9 的稀疏尺，需要量出 1 到 9，所有的整数长度，最少需要几个刻度？这里我省略单位了，因为无关紧要。

首先，传统上我们把 0 也作为一个刻度，总是需要的。另外，可以确定 9 这个刻度也是需要的。因为尺子总长度规定为 9，那么必须有 9 这个刻度，才能量出 9 这个长度。那么，其他刻度的话，哪些需要呢？我们可以可以推演一下。

首先，“1”这个刻度，要还是不要？相信多数读者会选择要。因为我们总需要量出“1”这个长度。否则你需要有另外两个相邻刻度才能解决的问题。所以，看起来，“1”加进来总没错。

那么“2”这个刻度，要还是不要？你可能认为不要“2”，要“3”更好。因为，有“3”的话，“1”和“3”就能量出 2，并且“3”也顺便把自己解决了。

但有“2”这个刻度的话，它也顺便解决了“7”这个长度。因为“2”和“9”之间距离为 7。如果把“2”跳过，那么“7”或“8”就变成必须的了，因为只剩下“0”和“7”或者“1”和“8”之间之间能量出“7”。

到这里，事情开始变得的无比复杂了。光用脑子想，已经很难想清楚了。所以，你可能会想用编程来解决。但对稀疏尺问题来说，用蛮力搜索的难点在于指数爆炸，即需要枚举的可能性太多，以至于等不到出结果的那天。

比如，对长度为 l 的稀疏尺，编程搜索的话，你是想从刻度数从最多往下减还是最少往上加呢？如果我们希望得到刻度数最少的结果，感觉上从少往上增加比较划算。

但也不用从 1 个刻度开始搜索。因为我们知道条 n 刻度的话，它们的两两组合有

种可能。所以，我们从使得

的那个 n 开始搜索。

比如，长度 l=10 时，可以发现至少需要 5 条刻度。另外，0 和 10 这两个刻度是必须得，所以可以从 1 到 9,共 9 种可能的刻度中，取 3 个数字，有 84 种组合。

然后对每一种组合，你需要两两匹配，再检查匹配的两个数字的差是否覆盖 1 到 9 所有的数字，这本身又是一个计算量很大的过程。

如果 84 种组合都不行，你就需要增加一个刻度，改为搜索 9 个数字里取 4 个数字的组合，有 126 种可能等等。

当然，对长度为 10 的问题，电脑的计算能力没有任何问题。但是，如果长度达到几百以后，需要搜索的组合数是以指数方式增加的，电脑枚举法就很快失效了。后面我们会看到，人类已经构造出来的最长的稀疏尺长度仅为 213。

到此，已经可以看出，对这个稀疏尺问题，其概念非常简单，但无论是推理法还是电脑蛮力搜索都有困难，那么这道题目就有意思了。这里留个思考题，请你设计一把刻度最少的，长度为 9 的稀疏尺（答在文中）。

以下会介绍一下，目前关于稀疏尺问题，人类都知道了些什么结果。但我先得定义几个概念，这几个概念也是帮我们理清思路的一个过程。

（需要注意的是，因为这个问题在数学中比较冷门，不同的文章所定义的名词和概念都有所不同。以下介绍的定义取自 Wolfram 公司的研究员 Ed Pegg Jr.在Hitting All the Marks: Exploring New Bounds for Sparse Rulers and a Wolfram Language Proof 一文中所使用的概念。在其他文献中，请自行甄别术语的定义，可能会有所不同。）

第一个概念，尺（ruler)：本文所说的尺，就是 0 到 n 之间的整数的子集，其中包括 0 和 n，因为我们需要量出“1”到“n”这 n 个长度。并且我们说，这把尺子的长度是 n。

第二个概念：完全(complete)尺：这把尺可以量出 0 到 n 之间，所有的整数长度，没有遗漏。

第三个概念：最小完全尺（ minimal complete ruler）：长度为 n 的完全尺中，刻度最少那把尺。任何长度下，总有 1 把或几把最小完全尺。最小完全尺，是长度一定的情况下，刻度最稀疏的完全尺，所以也简称它为“稀疏尺”（Sparse Ruler)。本文后面提到的稀疏尺，都是最小完全尺。

第四个概念：最优尺（optimal ruler）。它的意思是，在刻度数量确定的情况下，长度为最长的完全尺。稀疏尺是长度确定，刻度最少。那现在固定刻度数，我们能设计出最长的完全尺有多长呢？

此时最长的完全尺，就叫它最优尺，因为它是这个刻度数量下最长的尺了。再增加长度的话，刻度数肯定要增加。可以想见，肯定有些稀疏尺不是最优尺。即可以增加这把尺子的长度，但是不增加刻度数量的情况。

最后一个概念：完美尺（Perfect Ruler）。它是稀疏尺，且比它长的稀疏尺中，没有比它的刻度数更少的了。粗听这个概念有点多余，只有一种情况下，稀疏尺可能不是完美尺，那就是长度增加后，尺子的刻度变少了，这可能吗？这里先买个关子，后面会看到一个非常意外的情况。

定义过这些名词后，我们可以回顾一下关于这个问题研究的历史。稀疏尺问题的研究历史上发生了很多趣事和让你意外的地方。

首先，关于稀疏尺问题，匈牙利的数学家保罗·埃尔德什（Paul Erdős，1913-1996）就研究过。

我的读者应该都很熟悉埃尔德什了。要说我的节目中最常提到的数学家，前两位必定是保罗·埃尔德什和约翰·康威（John H. Conway，1937 - 2020），但两位的风格有所不同。

对康威提出的问题，我的第一反应一般是：啊，原来这也是一个数学问题（比如“外观数列”问题）？

对埃尔德什提出的问题，我的第一反应一般是：啊，原来这个问题数学家还没解决（比如“埃尔德什偏差问题”，虽然它已经被解决了）？因为埃尔德什提出的问题，往往都是很容易理解，但是却意外得困难的问题。

这个稀疏尺问题就太有埃尔德什的风格了，所以毫不意外，埃尔德什就研究过这个问题。在 1948 年，埃尔德什就与另一位数学家一起证明了，稀疏尺的刻度数与长度的平方根之间的比值，是有极限的。

这个结论并不意外，因为如果原来有 n 个刻度，那么每增加一个刻度，这个刻度就可能增加 n 个不同的差值。所以总体上，刻度数量不需要随尺子长度正比例增加，它只需要随尺子长度的平方根增加就可以了。当然，怎么严格证明两者比值的极限存在就是另一个难度的问题了。不管怎样，埃尔德什证明了这个极限存在，并且给出了这个极限的上下界，大约是 1.557 到 1.633 之间。

1956 年，数学家约翰·利奇（这个里奇就是发现利奇格（Leech Lattice)的那位）把下界提高了一丁点，到 1.56。1972 年，数学家马塞尔·戈莱(Golay, Marcel)，又把上界压低了一丁点，到 1.63。而这两个数字就是到目前为止关于这个极限所知的最佳上下界。

1963 年，有一位名叫威克曼（B. Wichmann)的数学家对这个问题有过重大贡献。他发现了一个公式，通过这个公式，可以构造任意长度的稀疏尺。这个公式长这个样子：

它是这样解读的:

是指有 a 段长度为 b 的距离，r 和 s 则是任意两个正整数。比如，取 r=1，s=2，分别带入上面的公式，依次得到：

1 个长度为 1 的线段， 1 个长度为 2 的线段， 1 个长度为 3 的线段， 2 个长度为 7 的线段， 2 个长度为 4 的线段， 1 个长度为 1 的线段。

把以上线段作为刻度之间的间隔，可以得到一把长度为 29 的完全尺：{0, 1, 3, 6, 13, 20, 24, 28, 29}。

这个公式强大在，它构造出来的完全尺经常是最小完全尺，或者非常接近最优，它现在被叫做“威克曼公式”。

那么，这里有个有两个意思的情况，在某些长度下，威克曼公式产生的不是最小完全尺。并且，也不是所有的最小完全尺都符合威克曼公式。

你想过没有，在特定长度下，并不一定只有一种稀疏尺，它可以有好多种刻度组合。比如长度为 13 的情况下，有 3 把稀疏尺，没有一把符合威克曼公式。

---

长度为 9 的两把稀疏尺（也是之前思考题的答案）：

{0, 1, 2, 6, 9}

{0, 1, 4, 7, 9}

后者可以用 W(0,2)生成。同时也能看出，刻度“2”可以有，刻度“3”在这里却总是不好的。

长度为 13 的三把稀疏尺，它们无法用威克曼公式生成：

{0, 1, 2, 6, 10, 13}

{0, 1, 4, 5, 11, 13}

{0, 1, 6, 9, 11, 13}

---

那威克曼公式看上去不太有用嘛？真不能这么说。因为目前为止只发现，在 5 种长度下，其稀疏尺全都不符合威克曼公式。这 5 个长度是 1、13、17、23 和 58。而其他长度的稀疏尺，至少有一把符合威克曼公式。

所以现在有一个猜想就是，长度大于 58 的情况下，威克曼公式至少产生一把稀疏尺。也就是尺子够长之后，威克曼公式总是能产生最小刻度数的完全尺。目前这是一个猜想，称为“最优尺猜想”（The optimal ruler conjecture）。

2013 年，关于威克曼公式，发生了一件趣事。当年有一次国际编程竞赛（Al Zimmermann's Programming Contests），竞赛的题目其本质上是构造一组稀疏尺的刻度。当然，原题目的形式并不是直接问稀疏尺的刻度，否则出题者应该可以发现威克曼公式。

而组委会并没有意识到这个问题，而有两组参赛者发现，这个竞赛题目可以直接用威克曼公式解决。所以毫无意外，这两组选手获得了竞赛前两名。因为用威克曼公式，根本谈不上计算复杂度，它可以以常数时间输出结果。后来，这两组选手还是很大度地谢绝了比赛奖品。

我还发现有很多公司面试程序员的时候喜欢用以下这道面试题，它也是 2021 年国内一次编程比赛的问题：

你有一架天平，请你设计设计一组最少的砝码的重量，使其能称出从 1 到 N 的所有重量。

能看出，这道题如果增加一个条件，要求每个托盘上最多只能放一个砝码，那么它就是稀疏尺问题。

此时，你可以直接给面试官甩出威克曼公式，虽然它不一定给出最少砝码的设计，但效率绝对是最优秀的。 当然，如果面试官因为不懂威克曼公式而拒绝你的话，不能怪我，只能说这家公司配不上你。

好了，回到正题。2013 年，Intel 公司的研究员艾奇·罗宾逊（Arch D. Robison ）注意到了当时的这个编程比赛的错题事件，他就想用自家公司的计算资源来算算稀疏尺问题。在当时，已知的最长的稀疏尺长度只有 123。

罗宾逊使用了 Intel 公司的 CPU 的计算集群，用了优化的算法，经过了几个月时间计算，最后确认了长度 213 以内的所有的稀疏尺的刻度数，其中长度为 213 的尺子需要 25 个刻度，其中一把可以用威克曼公式生成：

:

并且，长度 214 到 300 的尺子，25 个刻度不够，但具体需要几个刻度，罗宾逊没有时间去计算了。

在计算长度为 208 的最优尺的过程中，他使用 256 个 CPU，计算了 51 个小时才得出结果，可见该问题的计算复杂度。

在罗宾逊的计算过程中，他还有了一个让人吃惊并且非常有趣的发现。前面我说了稀疏尺和完美尺的概念。

稀疏尺是说，长度固定的情况下，我的刻度数最少。完美尺是说，比我长的尺当中，刻度不会比我少。

那么，就只有一种情况，才会使得稀疏尺不是完美尺。这种情况就是，某个长度下，某把稀疏尺有若干刻度。但是，当尺子长度变长时，另一把稀疏尺的刻度反而变少了。

那么，前面这个稀疏尺就不是完美尺。但是会有这种情况发生吗？看上去不会，直觉中，我们会认为，尺子变长，刻度数至少持平，不会减少。

但是，罗宾逊计算发现，长度为 135 和 136 的稀疏尺都需要 21 个刻度，而长度为 137 和 138 的稀疏尺却只要 20 个刻度！

---

长度为 135 的一把稀疏尺，它需要 21 个刻度：

{0, 1, 2, 3, 4, 5, 6, 65, 68, 71, 74, 81, 88, 95, 102, 109, 116, 123, 127, 131, 135}

长度为 138 的一把稀疏尺，它只需要 20 个刻度：

{0, 1, 2, 3, 7, 14, 21, 28, 43, 58, 73, 88, 103, 111, 119, 127, 135, 136, 137, 138}

---

哇，当时我看到这个结果的第一反应是一惊，第二反应是乐了。因为我深深感到，这是数学宇宙的设计者跟人类开的一个玩笑。数学宇宙的设计者想：你们人类不是没事做嘛，我给你们一点事做，你们来算算这个最优尺。你们不要简单得以为稀疏尺刻度数随长度是单调递增，偶尔可以减一下哦。

这太反直觉了。因为在我看来，减法是一个可以“微调”的操作。那么，难道是 138 这个数字有什么魔力，使得我们可以用 20 个小于等于 138 的数字，得到全部从 1 到 138 的差值。而当最大值为 135 和 136 时，却需要 21 个数字？这真的像一个玩笑，但也使这个问题一下子有趣起来。

并且，罗宾逊发现，这种情况在后面还多次出现，比如在长度 153,168 附近，看上去是存在无穷多把稀疏尺不是完美尺了。以上是 Intel 的研究员罗宾逊的发现。

2019 年到 2020 年，Wolfram（Mathematica 软件的开发公司）公司的研究员艾徳·佩格（Ed Pegg Jr.)也对这个问题产生了兴趣，进行了一番研究。他得到了一个有意思的结论，如果

是长度为 n 的稀疏尺的刻度数，则定义 E(n)如下：

其中

是四舍五入到整数。佩格证明了，对所有的 n:

，也就是 E(n)等于 0 或者 1。也就是说，

是计算稀疏尺刻度数量的一个不错的公式，最终的稀疏尺刻度数要么恰好是它，要么多 1。

Pegge 的证明过程很有意思，用了很多可视化方法来提示思路。他先是绘制了这样一张图：

横轴是刻度数量，纵轴是需要这么多刻度数量的稀疏尺长度。粗体表示那些长度位置上，实际所需刻度数要加 1。看上去是不是感觉有些规律？

他又根据当时已知的猜想的稀疏尺刻度数，把上图扩展到长度至 10501，得到了如下这张图：

OEIS的站长， Neil Sloane 称这张图为：乌云笼罩下的阴暗魔鬼磨坊（“Dark Satanic Mills on a Cloudy Day”）。用 AI 生产了一张图，还有真有点像：

根据“磨坊图”，Pegg 猜想出了

这个数字，并且他分别对长度大于 257992 和小于等于 257992 的稀疏尺进行讨论，最终证明了前述结果。

并且，根据这个结果，Pegg 分析说那个“最优尺猜想”基本上是对的，并且很可能当尺子长度足够长以后，所有的稀疏尺都符合威克曼公式，都是威克曼尺。

Pegg 写了一篇关于稀疏尺问题的blog，有很多图片，值得一读：

关于这个稀疏尺的话题就到这里了。我发现这个问题非常有趣，它确实是小学生可以理解的数学问题，因为它只用到减法。但以目前人类的计算能力，也只能只构造出长度为 213 的最优尺，这是挺让人吃惊的。

而更有趣的情况是，稀疏尺的刻度数不是单调递增的，这个情况有点意外，但太有趣了。 （并且中文领域中，我居然是第一个科普这个话题的？）

再最后，我给自己做个广告。我的新书“学数学会上瘾”已经在各大网络书店 app 上市。这本书距离我上一本书《老师没教的数学》过去了三年半。写一本数学书很不易，而现在流量驱动的情况下，作为一个数学内容的博主很难取得流量。所以，你买我的书就是对我最大的支持，也能让我把这个栏目继续坚持下去。

参考文献（注意不同文献中所采用的术语各有不同，请仔细甄别）：

http://www.luschny.de/math/rulers/PerfectAndOptimalRulers.html

https://blog.wolfram.com/2020/02/12/hitting-all-the-marks-exploring-new-bounds-for-sparse-rulers-and-a-wolfram-language-proof/

https://web.archive.org/web/20210330141047/https://software.intel.com/content/www/us/en/develop/articles/parallel-computation-of-sparse-rulers.html

https://www.erdosproblems.com/search?query=sparse

https://en.wikipedia.org/wiki/Sparse_ruler

https://old.renyi.hu/~p_erdos/1948-09.pdf