（1985 年，埃尔德什与 10 岁的陶哲轩的合影）
我的读者应该都很熟悉埃尔德什了。要说我的节目中最常提到的数学家，前两位必定是保罗·埃尔德什和约翰·康威（John H. Conway，1937 - 2020），但两位的风格有所不同。
对康威提出的问题，我的第一反应一般是：啊，原来这也是一个数学问题（比如“外观数列”问题）？
对埃尔德什提出的问题，我的第一反应一般是：啊，原来这个问题数学家还没解决（比如“埃尔德什偏差问题”，虽然它已经被解决了）？因为埃尔德什提出的问题，往往都是很容易理解，但是却意外得困难的问题。
这个稀疏尺问题就太有埃尔德什的风格了，所以毫不意外，埃尔德什就研究过这个问题。在 1948 年，埃尔德什就与另一位数学家一起证明了，稀疏尺的刻度数与长度的平方根之间的比值，是有极限的。
(1948 年，埃尔德什与 A Renyi 合作发表的关于稀疏尺问题的论文摘要)
这个结论并不意外，因为如果原来有 n 个刻度，那么每增加一个刻度，这个刻度就可能增加 n 个不同的差值。所以总体上，刻度数量不需要随尺子长度正比例增加，它只需要随尺子长度的平方根增加就可以了。当然，怎么严格证明两者比值的极限存在就是另一个难度的问题了。不管怎样，埃尔德什证明了这个极限存在，并且给出了这个极限的上下界，大约是 1.557 到 1.633 之间。
1956 年，数学家约翰·利奇（这个里奇就是发现利奇格（Leech Lattice)的那位）把下界提高了一丁点，到 1.56。1972 年，数学家马塞尔·戈莱(Golay, Marcel)，又把上界压低了一丁点，到 1.63。而这两个数字就是到目前为止关于这个极限所知的最佳上下界。
1963 年，有一位名叫威克曼（B. Wichmann)的数学家对这个问题有过重大贡献。他发现了一个公式，通过这个公式，可以构造任意长度的稀疏尺。这个公式长这个样子：
它是这样解读的: 是指有 b 段长度为 a 的距离，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}
哇，当时我看到这个结果的第一反应是一惊，第二反应是乐了。因为我深深感到，这是数学宇宙的设计者跟人类开的一个玩笑。数学宇宙的设计者想：你们人类不是没事做嘛，我给你们一点事做，你们来算算这个最优尺。你们不要简单得以为稀疏尺刻度数随长度是单调递增，偶尔可以减一下哦。
