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

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

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

如果要量 1 厘米的长度，就把被测物体放在 0 和 1 两个刻度之间。量 2 厘米，那么就是 1 和 3 两个刻度之间。需要量 3 厘米时，可以把被测物体放在 0 和 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[1] 一文中所使用的概念。在其他文献中，请自行甄别术语的定义，可能会有所不同。）

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

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

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

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

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

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

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

（长度 10 以内的稀疏尺刻度位置表。Length 是长度，Marks 是刻度数，Number 是数量，Wichmann 是威克曼公式）

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