晚上好!2024年的第35周!
本周的啊哈数是:43到48之间的某个整数。
不好意思,这周的啊哈数不是一个准确数字,而是一个模糊的范围。不过,这个范围也大有来头。房间里有一群人,有些人之间是朋友,有些人之间不是朋友。如果不管这群人之间的朋友关系是什么样,都能保证找出5个互相都是朋友或者5个互相都不是朋友的人,那么房间里至少有多少人?这个问题至今仍未解决。数学家们只知道一个模糊的范围:答案介于43到48之间。
i人聚会的烦恼
你的MBTI人格是什么?是社牛E人,还是社恐i人?你喜欢组局聚会或者参加聚会吗?我们来看看下面这个和聚会有关的问题。
假如你邀请了6位朋友来家里玩,可由于精力有限,你只能陪其中3个人,剩下的3个人就顾不上了,只能让他们自由社交。作为主人,你当然不想招待不周,可眼下有这么个问题:这6位朋友都是有点社恐的i人,他们很不擅长主动加入到陌生人的对话中。如果剩下3个人本来就很熟就不用担心了,他们很容易玩到一块儿去;如果这3个人都不太认识也还好,你在一开始互相介绍一下挑个头,三个人一起聊起来就不怕谁落单了;可如果这3个人里只有两个关系很好,剩下一个人和谁都不是很熟,那么这位i人朋友只能尴尬地缩在角落里,不敢加入另外两人的对话,最后整个聚会都不自在。所以,你希望能从6个人里找出其中3个人,他们互相之间都是朋友,或者互相之间都还不是朋友,并把他们安排在一起。
一定有这样的安排方法吗?6个人里会不会无论如何也找不到三个人互相都是朋友,或者找不到三个人互相之间都不熟呢?答案是:不管这6个人之间的好友关系是什么样,我们总能找出满足要求的三个人。
最少需要几个人
我们先简单地说明一下6个人里为什么总能找到互为朋友或者互相都不是朋友的3个人。
我们先从6个人中随便选一个当代表,方便起见就叫他A吧。剩下的5个人可以根据他们和A是不是朋友分成两组。那么,其中一组至少有3个人。
假设和A是朋友的那组有3人以上。我们把其中3个人分别记作B、C、D。
A和B、C、D都是朋友
如果B、C、D这3个人之间有任何两个人是朋友(比如下图里的B和C),那这两个人和A就组成了互相都是朋友的3人组。
如果B、C、D这3个人之间没有任何两个人是朋友,那这3个人就直接组成了互相都不是朋友的3人组。
当然,也有可能是和A不是朋友的人超过3人。这种情况也是一样的,你可以自己画一画:其中3个人分别记作B、C、D。如果B、C、D中有任意两个人不是朋友,那这两个人和A就组成了互不相识的3人组;如果B、C、D互相之间都是朋友,那他们直接就形成互为朋友的3人组。
不过,如果把6人改成5人,这事就不一定了。我们让5个人围坐在圆桌旁,使得相邻的两人是朋友,不相邻的人都不是朋友。那我们无论如何也找不出3个两两相邻的人,也找不到3个两两互不相邻的人,所以我们无法找出3个互相都是朋友的人,也找不到3个互相都不是朋友的人。因此,想要在一群人里找出3个互为朋友的人,或者3个互相都不是朋友的人,至少也需要6个人。
拉姆齐定理
数学家们用R(3, 3)表示,要想保证存在3个互相都是朋友或者3个互相都不是朋友的人,至少需要多少人。上一小节我们解释过了,至少有一种情况下5个人是不够的,而6个人无论是什么朋友关系都足以保证这样的3个人一定存在。所以,我们证明了R(3, 3)=6。
我们可以用类似但更复杂的方法证明R(3, 4)=9,R(4, 4)=18,R(4, 5)=25……英国数学家弗兰克·拉姆齐(Frank Ramsey)提出了组合数学中的重要结论——拉姆齐定理(Ramsey's theorem):对于任意正整数r和s,R(r, s)都是一个有限的数。
这意味着,即使我们把目标升级为“找出100个互相都是朋友或者1000个互相都不是朋友的人”,那么我们也能找出某个正整数M,使得任意M个人能保证实现这一点,但M−1个人就不行。这个M的值就是所谓的R(100, 1000)。
模糊的范围
好了,现在我们知道R(100, 1000)是什么意思了。那R(100, 1000)等于多少呢?抱歉啊,还不知道。
拉姆齐定理只能告诉我们,R(100, 1000)是一个有限的、确定的数,但并不能告诉我们这个值是多少。别说R(100, 1000)了,就连R(5, 5)的值我们都还不知道。目前,我们只知道一个模糊的范围——43到48之间的某个数,再具体一点就不知道了。R(6, 6)的值就更不确定了,我们现在只知道它在102到161的范围内。
你可能要疑惑了,这么个看似简单的问题,竟然到现在还只能给个范围?这范围又不是大到天文数字,而且还肯定是整数,不就那几个数吗,试都试不出来?可别低估了这个问题的复杂度!我们的老朋友埃尔德什曾经研究过这类问题。为了说明求出R(5, 5)和R(6, 6)的具体值有多困难,他曾经打过一个形象的比方:
假如有一支远远超过人类实力的外星军队降临地球,要求人类给出R(5, 5)的准确值,否则就要摧毁地球,那我们应该集结全世界所有数学家的智慧和全世界所有计算机的力量,试着求出R(5, 5)来。但是,假如外星人要的是R(6, 6)的准确值,那……我们还是选击退外星军队吧。
关于这周小数点的主题,我们在上周五给了大家一个模模糊糊的提示。你猜到了吗?这周我们的主题正是“模糊”。提到数学,一般大家会想到“严谨”、“精确”这样的形容词,但其实数学中也有不少和“模糊”相关的问题,让我们在这一周一起探索吧!
这里是小数点同学会,小伙伴的数学据点。关注我们,每天五分钟,聊点儿小孩也能看懂的趣味数学。