尺最少需要多少条刻度?(尺是如何做到统一刻度)


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

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

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

(长度为 10 的一把稀疏尺)

如果要量 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)。它是稀疏尺,且比它长的稀疏尺中,没有比它的刻度数更少的了。粗听这个概念有点多余,只有一种情况下,稀疏尺可能不是完美尺,那就是长度增加后,尺子的刻度变少了,这可能吗?这里先买个关子,后面会看到一个非常意外的情况。

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

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

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

(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)的数学家对这个问题有过重大贡献。他发现了一个公式,通过这个公式,可以构造任意长度的稀疏尺。这个公式长这个样子:

它是这样解读的:

是指有 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}


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

(稀疏尺长度与刻度数的关系图。横轴为尺的长度,纵轴为尺子所需刻度数。可以看到,它不是单调递增的,在横轴为 137 的位置处,第一次减少 1。此后偶尔可以减少 1,并且间隔似乎很有规律。)

这太反直觉了。因为在我看来,减法是一个可以“微调”的操作。那么,难道是 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 上市。这本书距离我上一本书《老师没教的数学》过去了三年半。写一本数学书很不易,而现在流量驱动的情况下,作为一个数学内容的博主很难取得流量。所以,你买我的书就是对我最大的支持,也能让我把这个栏目继续坚持下去。

参考文献(注意不同文献中所采用的术语各有不同,请仔细甄别):

luschny.de/math/rulers/

blog.wolfram.com/2020/0

web.archive.org/web/202

erdosproblems.com/searc

en.wikipedia.org/wiki/S

old.renyi.hu/~p_erdos/1

查看知乎讨论
有哪些看似汉语实为音译的地名?(林冲相关地名有哪些)
上一篇
「音色」是什么?
下一篇
本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。

相关推荐

  • 苹果手机各个功能介绍,iphone必须关闭的十个功能

    1、关闭蓝牙。现在已经很少有人用蓝牙传输文件了,而且iPhone与安卓的蓝牙并不兼容,所以,可以在设置中,关闭蓝牙功能。2、关闭通知功能。关于APP推送,无非也就是一些更新提醒,关了也不会有什么影响,还能多省点电。3、关闭自动调节亮度功能。一般来说,可以将屏幕亮度在15%-30%之间,在强光环境中,在进行手动调整就可以了。4、禁止后台刷新。在设置—通用中,关闭后台自动刷新功能,也可以对省电起到一点...

  • 高德打车怎么设置途经地,高德如何添加途经路线

    1、点击高德地图APP界面底部的“导航”按钮,进入导航模式。2、点击右下角的“路线”,进入路线设定页面,根据要求输入起点、终点进行路线规划。3、点击“添加途经点”,弹出添加途经点页面,点击右上角,可以添加或者删除途经点,乘客可以手动输入要添加的途经点。4、当添加完途经点时,点击“确定”按钮,即可添加途经路线。此时地图会显示出这条路线上所有的途经点,以及当前途经点的地点信息。怎么设计高德地图设置要经...

  • 高中必修二物理知识点总结,高一物理必修2重点知识点归纳

    您好,1.运动学-位移、速度、加速度的概念及计算方法-相关运动的分析方法,如相对运动和抛体运动-牛顿运动定律及其应用2.力学-力的概念及种类,如重力、弹力、摩擦力等-牛顿第一、二、三定律及其应用-力的合成与分解-能量、功、动能定理、功率的概念及计算方法-动量、冲量定理及其应用3.热学-温度、热量、热能的概念及计量单位-热传递的方式及其特点,如传导、对流、辐射-热力学第一、二定律及其应用,如热机效率...

  • 电脑菜单在哪 电脑菜单怎么打开(电脑菜单在哪里找到)

      最近有不少小伙伴说不知道电脑菜单在哪,想要打开电脑菜单却不知道怎么做,于是来系统城求助小编,为了帮助到大家,小编到网上查阅了相关资料,总算找到了电脑菜单的打开方法,具体内容全部在下文中了,大家如果...

  • 电脑如何录屏 电脑录屏的操作步骤(电脑怎么录屏分享实用的录屏方法)

      在使用电脑的时候总会碰到需要记录电脑内容的时候,像会议记录、电影片段、游戏操作等等。那么电脑如何录屏呢?其实我们的win10系统就有自带的录屏的功能,今天小编就给小伙伴们分享下关于电脑录屏的操作步...