标签 科普 下的文章

上海疫情封在家中有三个月,辅导了小孩子功课,每每小孩遇到不会做的题目,比她更着急。有时也会想起自己学生时代的样子,遇到难题,心中升起必须克服难题的决心,现在自己娃,怎么没有我当年的风采了。哈哈,扯远了,这两天网上看到一道小学二年级的题目,其实我之前做过类似的题目,但是当下还是震惊了,怎么现在小学二年级题目有这么难?

题目是这样的:
赛车比赛题目.jpeg

配合网友的回复,我马上想到了之前类似的问题,说是25匹马,5个赛道,至少比几场保证找出最快的2匹马。赛马这题答案我记得很清楚7场比赛,先分组进行小组赛:

赛马比赛分组.png

首先一个虚线框就是一场比赛,上来25匹马,分5组,进行5场预赛。5组比赛会得到组内的名次,比如A组,A1->A2->A3->A4->A5,每组第一名就是A1,B1,C1,D1和E1,然后第一名之间安排一场决赛:
赛马比赛决赛.png

假设结果就是A1->B1->C1->D1->E1(真正结果不重要,不管怎么样,总能推理出最后的结论),这时候我们就通过4场比赛,知道了第一名是A1,那第二名是谁呢,是不是B1,不一定哦,有可能是在小组赛中被A1淘汰的A2,所以安排场附加赛吧,A2 vs B1:
赛马附加赛.png

附加赛之后,就能知道前两名了。话说回小学二年级赛车这道题目,其实思路一模一样,就是通过小组赛->决赛->附加赛,完成前两名的确认,也就是说赛车的话,通过至少5场比赛,保证找出前两名的赛车。

作为小学二年级的题目很变态了吧,但是出题的人还多问了一句,怎么证明这件事情呢,为什么通过4场比赛一定不能保证找出前两名呢?这个证明难倒我了,抓耳挠腮半天,没想出来。然后我就看了下出题老师的分析,茅塞顿开,原来还可以使用图论+反正法来证明。大致的过程如下:
首先把每一辆赛车想象成点,那么我们一共有9辆赛车,一共9个点,每场比赛,只能进行3辆赛车的比拼,每次比拼完,我们会有一个名次,紧挨着的前后两名之间,使用一条有向边连接,这个我文字讲得有点绕口,一图解千愁:
赛车比赛顺序图.png

圆圈表示赛车,1号比2号快,2号比3号快,所以每次比赛,我们仅仅能得到2条有向边,如果进行4场比赛,那么总共的有向边数量是4*2 = 8条,而赛车的数量是9,也就是节点数量是9,8条边,9个点,如果要保证所有边都连接到一张图中,不能出现环,否则边的数量不够。
环.png

出现环就意味着9个点形成了若干个分开的子图,上面图中9个节点,分为了两个子图,那么就会有一个问题,第一名都不知道是谁,为什么?因为在1~8节点所在的图中,1号赛车最快,9号赛车单独成子图,9号赛车和谁都没有比过,那么到底9号和1号赛车谁快呢?不知道。所以8条边,安排的比赛结果,划分为多个子图,这样是无法确认前两名的。

那我们4场比赛的结果,如何是可以前两名的图形呢,如下:
树形图.png

左边就是分3场比赛(1、4、7,2、5、8和3、6、9分别比赛),得到结果后,4、2、3比一次,结果是4->2->3,转化这张单图,得到右侧的结果,其实就是一个树形的图,那么前两名就是1、4号赛车。

这样我们很容易举出反例,你不是就8条边么,我最后4、2、3的结果是2->4->3,图就变成非树形图,如下:
多个根结点图.png

这样又回到之前多个子图的问题,我们是没法确认1号赛车和2号赛车谁快的,也就没法真正确认前两名是哪两辆赛车。

OK,至少5场比赛,而非4场比赛保证找出最快的2辆赛车得证。是不是挺难的,至少我是没有想出来,通过图论+反证法证明这个数据结论,由衷发出感慨,活学活用好难啊,能做到的大佬,真的太强了。
373d2c7114b84ac57e8b9e3ad3eb78fe.jpeg

导语

作者:李永乐老师官方 如何公平的切蛋糕

什么是公平?

在生活中我们会遇到各种纷争,小时候和兄弟姐妹争抢一份蛋糕,长大了到单位和同事互相举报。世界上的许多纷争,都来源于“不公平”和“嫉妒心”。

“不公平”就是感觉自己应得的没有得到,“嫉妒心”就是虽然自己得到了应得的,但是其他人得到的更多。如果设计一种方案,让每一个人都感觉自己拿到了最多的利益,纷争就会少很多。就好像把一个蛋糕分给几个人,如何才能让所有人都满意呢?

最近我看了一本书《如何切蛋糕以及其他数学问题》,颇受启发。许多管理者也许可以借鉴这个方法,一些社会矛盾也可以因此化解。下面,就让我带着大家了解一下“切蛋糕问题”吧!
如何公平分蛋糕.png

一. 两人分蛋糕:我切你选

两个小孩分一块蛋糕,如果父母帮着切,经常会有孩子大喊:他的那一块比我的大。甚至有的时候,两个孩子都这样喊。

这时我们可以这样做:让一个孩子决定如何把这块蛋糕切成两份,让另一个孩子先选。切蛋糕的孩子为了不吃亏会尽量把蛋糕分得均匀,选蛋糕的孩子具有优先权,谁也不会觉得吃亏了。这就是经典的“我切你选”方式。

让我们举一个更生活化的例子:一位老人去世了,留下了一套房产和一百万现金,老人有两个儿子,但并没有留下遗嘱。于是,兄弟俩决定对房子进行评估,然后把包括房产和现金的总遗产平分。
分遗产的问题.png

不过,在评估房产价格时,兄弟俩产生了不同的意见——想要房子的哥哥把房产价格评估得很低,这样他除了拿到房子,还可以获得一大笔钱;不想要房子的弟弟把房产价格评估得很高,如果哥哥要房子,还要补偿弟弟一笔钱。这可怎么办?

其实这个问题不难解决,采用经典的“我切你选”的方式就可以了。首先,哥哥将房产价格进行评估,然后将总财产分成两份。一份包含房产和一部分现金,另一部分完全是现金。然后,让弟弟先选继承哪一份,剩下的一份留给哥哥。

对于哥哥来讲,他知道自己是后选择的,为了防止吃亏,他必须将遗产分配得尽量公平。如果一边明显占优,弟弟完全可以选择这一份更优厚的遗产,让哥哥吃亏。

假如哥哥刚好要结婚买房,他去市场上看了一圈,发现买相同的房子大约需要50万元,于是他就会把房子和25万现金作为一份遗产,把另外75万现金作为另外一份遗产,这两份遗产对哥哥来讲,效用都是1/2。无论弟弟如何选择,哥哥都不会感到吃亏。

对于弟弟来说,也许他在国外读大学,以后也不准备回老家工作了,所以这个房子的作用不大,他更需要钱维持自己在国外的学业。于是他评估:老人的房子只值25万,这样,第一份遗产对弟弟来讲就值50万,第二份遗产有75万,效用分别是2/5和3/5,显然,弟弟会选择第二份遗产,把第一份遗产留给哥哥。
兄弟两人分遗产.png

兄弟二人都觉得自己拿到了至少1/2的遗产,这就是“公平”,而且,别人拿到的都不比自己更多,这就是“无嫉妒”。由于两人对房产价值的看法不同,弟弟还觉得自己比哥哥多拿了不少,非但不会有纷争,反而因为内心惭愧而让兄弟关系变得更加和睦。

这种“我切你选”的方法,从几千年前就已经有人采用了。比如《圣经》中有这样的记载:亚伯拉罕与洛特分配迦南之地,为了公平,亚伯拉罕把这块地分为东西两块,并让洛特先选。
亚伯拉罕与洛特分地.png

另一个应用是在《联合国海洋法公约》里。发达国家具有对公海矿藏进行开采的能力,但是公海矿藏应该属于全人类。于是,联合国设计了这样一种方案:如果有国家申请对公海区域进行矿产开发,需要提交两个类似区域的评估报告,联合国将在两个区域中选择一个,保留给发展中国家,另一个允许发达国家进行开采。为了自身利益,发达国家必须公正地分割区域,并如实提交报告——否则,联合国可能选择那个矿产资源更丰富的海域保留给发展中国家。
海上油田.png

一个好的制度,不光能让人说实话,还能让所有人都觉得自己占了便宜。现在,你应该了解如何让两个人分配利益了。

二. 三人切蛋糕:公平但是有嫉妒

现在我们把问题升级:假如三个人要分一块蛋糕,又该怎么做呢?1961年,数学家杜宾斯和斯巴尼尔提出了一种“移动刀法”,可以让三人“公平的”分蛋糕。
Lester Dubins & Edwin Spanier.png

假如蛋糕是一个长条,左侧有更多的草莓,而右侧有更多的奶油。现在让一个人拿着刀,缓慢地从左向右移动,三个等着分蛋糕的小朋友A、B和C紧紧盯着刀的位置,计算着自己最喜欢的蛋糕部分。

突然,小朋友A喊“停”!于是刀就在这里切下一块,并把这一块分给喊停的小朋友。随后,刀口继续移动,小朋友B又喊了一声“停”,刀又会在这儿切下一块给B,余下的一块就是C拿到的蛋糕了。
三人切蛋糕.png

让我们来分析一下三个人的内心活动:每个人都希望自己拿到不少于1/3的蛋糕,这才是公平的。

A可能特别喜欢草莓,而草莓位于蛋糕的左边。当刀移动时,A看到自己喜欢的部分被包含进来,内心激动万分,当他认为这一部分的蛋糕效用已经超过了1/3时,就会迫不及待地喊停,他已经不吃亏了。

B对草莓和奶油具有同样的喜好,当A喊停时,在B的眼中,这一块蛋糕只1/4的效用,所以B会选择继续等待。A拿走第一块后,B认为余下的蛋糕还有3/4,只剩下2个人,每人一半,自己可以拿到3/8。当刀口移动到余下的蛋糕一半的位置时,B就会喊停,拿走这一部分。

C特别讨厌草莓,又特别喜欢奶油,所以他认为A拿走的蛋糕只有1/5的效用,B拿走的蛋糕只有1/4的效用,余下的部分有11/20,结果全都被自己拿走了,C是最高兴的。
三个人切蛋糕.png

有人会有疑问:为什么A在刀口到达1/3效用的位置时一定要喊停呢?假如他再等一会儿,不就能拿到更多的蛋糕了吗?

他这样做是有风险的,因为在这个时刻,对A来讲,左侧蛋糕价值1/3,右侧蛋糕价值2/3。A喊停,可以保证拿走1/3的蛋糕;如果A选择等待,右侧部分将会少于2/3,假如此时被B喊了停,A将只能和C一起分配不到2/3的蛋糕,很有可能,A将没有机会获得1/3的蛋糕了。因此,A一定会诚实地说出自己的感受,这样他才能获得确定的、公平的蛋糕,对于B来讲,情况也是类似。

可是如果我们继续分析,就会发现这种方法尽管“公平”,却不是“无嫉妒”的。设想:在蛋糕分配完毕后,三个人重新检视了别人拿到的部分。

  • C感觉A拿到1/5,B拿到1/4,自己拿到11/20,自己拿到的最多,非常开心;
  • B感觉A拿到1/4,自己拿到3/8,C拿到3/8,自己和C拿到的并列最多,心情也不错。
  • A看了看B和C拿到的部分,假如他觉得B拿到的部分实在糟透了,价值只有1/4,但是C因为一直没有喊停,反而拿到了最大的一块,价值是5/12(=1-1/3-1/4),比自己的1/3(=4/12)还要大!
    三人切蛋糕2.png

这时,A的内心就不平静了。虽然我拿到了全部蛋糕的1/3,我并没有吃亏,但是居然有人比我拿得多,这就不行!于是嫉妒心就产生了。

这样的情景在生活中并不少见。一伙儿匪徒去抢劫,大赚了一笔,每个人都到分了不少钱,远远超过了自己的预期。可是,还是有匪徒认为别人拿到的超过了自己,于是产生了内讧。有些领导干部,明明自己贪污,反而去纪委举报同事,因为他觉得别人比自己贪污得更多,自己很冤枉。

也许你在单位中是一名兢兢业业的技术工人,有一天获得了一点荣誉或者奖金,立刻就有人红着眼睛在背后议论你,你感觉到很委屈,自己明明只拿到了应得的部分啊!为什么还会被人嫉恨呢?还是那句话,因为每个人对利益的看法不同。你认为你只拿到了自己应得的部分,但是其他人却可能觉得你比他拿的多得多。现在,你明白了吗?

三. 如何消灭嫉妒心?

三个人还有更好的分蛋糕方法吗?既要公平,还要没有嫉妒,让每个人都觉得自己拿到的部分最大?

这并不是一个容易的数学问题。在1960年代,数学家塞尔福里奇和康威提出了一个方案——三人公平无嫉妒的分蛋糕方法。
John selfridge  &John Conway.png

首先,让A将蛋糕分成三份,并且让B和C先选,A拿余下的那一块。因为A知道自己将会最后选择,所以他一定会尽力将三块蛋糕分成均等效用的三份,否则吃亏的一定是自己。
三人切蛋糕3.png

由于每个人的喜好不同,在B和C眼中,三块蛋糕并不是均等的,而是有大有小,他们都会选择自己认为最大的那一块。如果B和C的选择不同,A拿余下的一块,那么问题就解决了。此时B和C都认为自己占了最大的便宜,而A认为三块一样大,也没有人超过自己。三个人都非常开心,这种分配方案是公平且无嫉妒的。
三人切蛋糕4.png

不过,如果B和C都看上了同一块蛋糕,那问题就复杂了。比如,B和C都认为右边的一块蛋糕最大,他们就必须遵循下面的步骤分蛋糕:

  • 由B操刀,将最大的一块(右侧蛋糕块)再切下来一小条,使得这块蛋糕余下的部分与B眼中第二大的蛋糕块一样大。
    三人切蛋糕5.png
  • 不考虑切下来的小条,按照C、B、A的顺序选择三个大块的蛋糕。
  • 如果C没有选择B切过的那一大块蛋糕(右侧蛋糕),那么B必须自己拿走这一块。

这个过程类似于新闻上4S店的新车争夺战。一名男顾客和一名女顾客同时看中了一台新车争执不下,此时男顾客飞起一脚把新车的车灯踹碎了,并问女顾客:这辆车你还要不要?你要的话我还继续踹。此时,如果女顾客选择退出,男顾客就必须自己把这辆车买走,否则4S店是不会同意的。

按照这个步骤,三人在第一次分配的过程中,都感觉自己是占便宜的。

  • C先选,C一定选择自己心目中最好的一块,他没有理由嫉妒别人;
  • B再选,因为经过自己操刀,三块蛋糕中有两个蛋糕相同而且最大(比如中间的和右侧的),C不可能把两块都拿走,所以B总有机会拿走最大的两块中的一个;
  • A最后选,原本他将蛋糕切成了三个一样大的,现在由于B将最右侧的蛋糕又切下来一块,最右侧的蛋糕变小了,左侧和中间的蛋糕一样大。不过好在,如果C没有把最右侧的蛋糕拿走,按照规则B就会把这一块拿走,这块小的蛋糕一定不会留给A,A也非常开心。
    大家好才是真的好.png

大块分完了,现在开始分切下来的一小条。如果刚才,C拿走了最右侧的一块(那个被B切过的)蛋糕,那么就继续由B将这一小条分成均匀的三块,并且按照C、A、B的顺序选择这三块,这样同样是无嫉妒的。
三人切蛋糕6.png

  • C第一个选,所以他会选择自己心目中最好的那块,不会嫉妒别人。
  • A比B先选,所以A不会嫉妒B;又因为在A心中,现在分的这一小条,本来就是从刚刚被C选走的那一块(最右侧)的蛋糕上分割下来的,在A的眼中,C这个傻子上一次选了最小的,现在就算把这三个部分全都给C,C也只是拿到跟自己一样多的蛋糕而已。于是,A也不会嫉妒C。
  • B最后选,他一定会尽力将三块分得均匀——无论自己拿到哪一块,都不会嫉妒别人。

这样,整个蛋糕被分配完毕。三个人都觉得自己拿到了最大的一块,这样就不会有人嫉妒别人,也不会有人到上级部门举报了。这真是一个精妙绝伦的方法!
没看懂.png

如果刚才是B选择了被切过的蛋糕块(最右侧),那么就由C来分配这小块,再按照B、A、C的顺序选择,结论和刚才一样。

如果人数比三个人还多,又该怎么做才能公平且无嫉妒的分蛋糕呢?1995年,数学家布拉姆斯和泰勒证明了无论有多少人,都存在这样的分配蛋糕方案。只是,在人数比较多的时候,这个分配方法非常的复杂。
史蒂文·布拉姆斯& 阿兰.泰勒.png

到了2016年,阿奇兹和麦肯奇又证明了N个人公平且无嫉妒的分配一个蛋糕,所需要的方法数的上界是:
N人切蛋糕.png
这么多种。

尽管这个问题在数学上的解非常复杂,但是它依然能给我们看待社会问题很多的启发。比如作为公司员工,我们会明白自己为何会嫉妒别人,以及为何会被别人嫉妒;作为公司管理者,我们自认为是客观公正的,但是员工却都觉得自己偏心。

家长们自认为自己是客观公正的,呕心沥血地设计方法分蛋糕,反而经常会落个里外不是人的结局。相反,设计一个合力的制度,让孩子们参与到分蛋糕的过程中,没准能获得一个让所有人都满意的结果。

导语

记得上初中的时候,我们就学了地理,里面涉及到很多有意思的知识,比如地球是太阳系九大行星(当时冥王星还是算太阳系大行星,2006年被降为矮行星),地球的大小、质量都是知识点,需要我们记住,地理会考知识点,还有地球的寿命,40多亿年(这个印象最深刻)。当时觉得特别神奇,究竟谁算出这些值,又是使用什么方法的呢?尽管有疑问,但是一直没有搞懂,甚至到了高中、大学,陆续学习了物理、数学更多的知识后,这个疑问才慢慢解开。这篇文章一方面重温下对知识“茅塞顿开”的感觉,另一方面致敬那些对科学真理孜孜不倦追求的科学家(太敬佩他们了)。

地球质量怎么算

显然,我们没法实际测量地球质量,哪怕现在,我们也没法直接测量,那么只能间接测量。通过已知量和公式,计算求得地球质量。

1687年,牛顿的万有引力定律在他的著作《自然哲学的数学原理》中。牛顿的万有引力定理,大家都很熟悉,两个物体之间的引力公式:F=G(m1m2)/r^2,其中m1和m2是两个物体的质量,r是两个物体之间的距离,而G是其中的万有引力常数。
地球质量的计算.png

人站立在地球上,重力的计算公式:重力 = mg,其中m是人体重量,而g是重力加速度。两个力相等,得到如下等式:

G(Mm)/R^2 = mg,变化下等式得到地球质量M = (gR^2)/G,其中g为重力加速度,R为地球半径,G是万有引力常数。所以只要知道这三个值,地球的质量也就可以计算出来。

地球半径

以上三个量,人们最早通过科学方法计算出来的是地球半径,早在古埃及时代,希腊数学家希腊数学家厄拉托塞(约公元前274~前194年)在夏至这一天的中午,于埃及的希耶乃(现在的阿斯旺水坝附近)看到深井发现阳光直接照到井底(因为这个在北回归线上,而且还是夏至)。然后在某年同一天,,他在希耶乃正北805公里的亚历山大处,直立一杆,却出现了日影.于是他根据杆长和影长,算出杆和太阳的夹角是7°12′,然后根据角度与圆的关系,算得地球周长:L=805360/7°12′=40000, 再根据R=L/(23.14)=6300公里左右。
地球半径.png

重力加速度

1590年,意大利物理学家伽利略,进行了世界上第一次重力测量。他利用球在斜面上的滚动,测得球在第一秒内走了4.9米,第二秒时走了14.7米,第三秒时走了24.5米。由此推得球在二秒钟所走的距离比一秒钟增加9.8米;三秒钟所走的距离也比二秒钟增加9.8米。从而得出重力加速度的数值为9.8 m/s^2。

万有引力常数

虽然万有引力的公式由牛顿提出,但是G这个常数却不是,是由英国另一位著名实验物理学家卡文迪许测量出来的。

卡文迪许是怪咖科学家(据说也是贵族后代,所在的家族是一个拥有超过400年历史的英国老牌贵族,他继承了巨额的遗产,多巨额呢,达到了英国“中央银行”英格兰银行的资产总额的十分之一,其实很多科学家都是富N代),在牛顿提出万有引力定律之后的100年内,没有人能准确测出万有引力常数,但是卡文迪许通过著名的“扭秤实验”,经过三年改进实验装置和两年测算,计算求出了万有引力常数,甚至测得的值和目前的值只有1%以内的差距。经过卡文迪许改进后实验装置大概如下:
扭称实验.jpeg

一面小镜固定在石英丝上,再用一束光线照射这一小镜。小镜将光线反射到一根刻度尺上。这样,只要石英丝有极微小的扭动,反射光就会在刻度上有明显的移动。

然而,更大的麻烦还在后面。空气的流动会导致扭秤偏转,产生的误差比万有引力还大! 人根本不能在实验装置前走动,因为人走动会导致空气流动。更严重的问题是,扭秤处于运动状态,它以一定频率周期性扭动。另外一个严重问题是温度变化导致扭秤测量结果变化。

卡文迪许想了一个天才的想法,他将扭秤放在一个封闭房间里,在房间外通过窗户利用望远镜观测扭秤的偏转(直到今天,我们还在大量采用卡文迪许发明的方法来减少测量误差,提高测量精度。 例如,我们把哈勃望远镜搬到太空,大幅度提高观测分辨率),这就避免了空气流动的影响,也放大了偏转信号。同时,卡文迪许年复一年地仔细观测扭秤,有效降低了温度和扭秤周期性摆动对观察误差的影响。(很有耐心)

通过卡文迪许实验结果可以求出万有引力常数G为 6.754 × 10−11N-m2/kg2,他死后的100多年,才有更精确的测量结果出现。

地球质量

知道三个值之后,简单代入,地球质量就算出来了,大概是6*10^24 kg,地球的质量真是大,因为卡文迪许是测得万有引力常数的人,而这个常数是最后人们才知道的,所以卡文迪许也可以算数历史上第一个计算出地球质量的人。像厄拉托塞、伽利略、卡文迪许这些数学家和科学家,并不知道自己测得的地球半径、重力加速度或者万有引力常数会给当下的社会带来什么变革,他们通过自己的探索精神,为人类开拓知识的边界,做出了卓越的贡献。人类就是这样,一步一步,由这些科学家带领着走向新的未知领域。