抽签相互送礼物很神秘,可抽到自己的怎么办?

2019年7月17日03时00分内容来源:果壳网

中学的时候,老师组织过一次别开生面的“礼物交换”:每个人把自己的名字写在纸条上,然后把纸条放在一起,让大家各抽一张。每人要给自己抽到的那个人写一张新年卡片,或者准备一个小礼品。


那时候我就在想:我会抽到自己吗?要是有人抽到了自己,岂不是很尴尬?


这样的可能性当然是存在的。而这个游戏稍作变化,就会变成日剧《轮到你了》中出现的一个关键情节——13名公寓楼住户在参加住户大会时,所有人在一张纸条上写下自己最希望杀死的人的名字(写谁都可以,不限于现场的人),之后进行抽签,相当于“交换杀人”。但没有想到的是,之后纸条上写的人真的开始一个接一个地死去,事件开始向不可控制的方向发展……


众人抽签 | 《轮到你了》


这里有一个问题就是,所有人写纸条并抽签时,有多大的可能性没有人会抽到自己写的纸条呢?


在第7集中,202住户、数学专业学生黑岛沙和(西野七濑饰)就对这个问题进行了计算,并得出了正确答案。


数学专业学生黑岛沙和 | 《轮到你了》


“没有人抽到自己纸条”的概率约为36.7%,既至少一个人抽到自己纸条的可能性是63.3%。


黑岛计算结果 | 《轮到你了》


那这个结果是怎么算出来的呢?


我们来考虑一下,参加人数为不同的数目时,“没有人抽到自己纸条”这种情况,可能会出现多少种不同的排列方式。


1

如果参加游戏的只有1个人


如果参加游戏的只有一个人,那么ta必定会抽到自己的纸条。“没有人抽到自己纸条”的情况数是0。


2

如果参加游戏的有2个人


假设这两个人是a和b,那么“没有人抽到自己纸条”的情况数是1,a抽到b写的纸条,b抽到a写的纸条。


3

如果参加游戏的有3个人

参加游戏的a,b和c这3个人,“没有人抽到自己纸条”的情况数是2,其中,


i.a抽到b写的纸条(这时还剩下a写的纸条,和c写的纸条),b抽到c写的纸条,c抽到a写的纸条,这是第一种情况。


ii.a抽到c写的纸条(这时还剩下a写的纸条,和b写的纸条),b抽到a写的纸条,c抽到b写的纸条,这是第二种情况。


因为考虑的情况是“没有人抽到自己纸条”,能够看出,这就是全部的可能情况了。


《轮到你了》剧照



4

如果参加游戏的有4个人



要像刚才那么数,就有点复杂了。


先明确条件,A,B,C,D四个人,每个人都不能抽到自己写的纸条。比如B不能抽到自己写的条,允许抽到A、C、D写的条。


这时,我们可以改换一下思路。由于A不能抽到自己写的纸条,先假设A拿到了B的纸条。这时候,我们的问题实际上转化为了两种情况:


情况一:

BCD三个人,来抽A写的纸条(记为a)、C写的纸条c、D写的纸条d这3张纸条,抽的时候都没有抽到对应的纸条;BCD三个人抽acd三张纸条,其实跟BCD三个人抽bcd三张纸条是一个意思。只不过,原来我们规定的是,B不能抽到b纸条,而现在我们把这个规定改为了,B不能抽到a纸条.

情况二:

B当然是可以抽到a纸条的,这种情况要单独计算,这时B抽到了a纸条,CD两个人抽纸条,没有抽到自己。


仔细想想,这不就是“3个人抽签没有抽到自己”+“2个人抽签没有抽到自己”?这两者我们前面都算过了,加起来,这就是“A拿到了B的纸条”这种情况下的全部可能情况数。然后把前置条件“A拿到了B的纸条”再推及到别的情况,一共有三种(A拿到了B、C、D的纸条)。


于是,4个人的游戏中,“没有人抽到自己纸条”的情况数,就是3*(2+1)=9。


以此类推,若参加游戏的是5个人,“没有人抽到自己纸条”的情况数是4*(9+2)=44,6个人,则是5*(44+9)=265,7个人是6*(265+44)=1854。


现在我们来计算一下概率。7张纸条随意排列,排列情况总数是7!共5040种。而1854/5040=0.367857……


这个数字,已经很贴近剧中数学系住户算出来的数字了。而当 n 继续增大时,这个概率数字会快速收敛到 1/e = 0.367879……(e为自然对数的底)。


装错信封问题



这种排列,数学上叫做“全错位排列”。或许你也发现了,我们刚刚其实是使用了递推的方式,把全错位排列可能数目记为Dn推导出了Dn=(Dn-1 + Dn-2)*(n-1)。


实际上,这个问题属于组合数论的范畴,又称为“装错信封问题”。“装错信封问题”是由瑞士数学家约翰·伯努利(Johann Bernoulli,1667-1748)的儿子丹尼尔·伯努利(DanidBernoulli,1700-1782)提出来的,瑞士数学家欧拉(Euler)等也研究过这个问题。大意为:


n封不同的信及相应的n个不同的信封,把这n封信都装错了信封,问都装错信封的装法有多少种?


可以看出,这个描述中蕴含的数学问题,其实跟写字条后抽签是一样的,也可以用多种不同的方法来描述。比如我把n 张扑克牌打乱,然后发牌,如果出现发牌次序数=牌面数字的情况,我就赢了,比如发第3张牌时,牌面是3,那么我有多大可能赢?




这个概率,你现在知道了——如果牌足够多,那可以说这个概率约等于1-0.367 ,即0.633,且会向1-1/e无限靠近。


还可以再换个说法,这个描述等价于:


把数字1 ~ n放入序号1 ~ n的格子中,数字1不能放入序号1的格子,数字2不能放入序号2的格子……数字n不能放入序号n的格子。


一下就想起中学时的组合数学题了是不是。


推导开始



好了!以下是数学学霸专用高能时间,请准备好之后再打开。


/*

别怕,其实运算只有加减乘除和阶乘,往下看就知道了!

*/


剧中,202室住户、数学系学生黑岛沙和写的公式,正是全错位排列的排列数目的计算公式。


黑岛沙和的公式 |《轮到你了》


排列数目= n! *( 1/2! - 1/3! + 1/4! - 1/5! + ... + (-1)n *1/n! )


由于n个纸条随机排列,分给n个人的总的排列可能数目是n!。


全错位排列数目/总的可能排列数目,就是全错位排列的概率,也就是:


( 1/2! - 1/3! + 1/4! - 1/5! + ... + (-1)n*1/n! )


实际上,这正是 1/e 的麦克劳林展开式 (泰勒展开式的一种特殊形式),当n增大时,这个数字会迅速收敛到 1/e。


作者供图


这也就是剧中黑岛沙和写的这个公式了,剧中参与游戏的有13个人,n为13。


《轮到你了》剧照


n! * ( 1/2! - 1/3! + 1/4! - 1/5! + ... + (-1)n *1/n! ) ,这个全错位排列的出现数目的公式,可以有多种证明。把全错位排列可能数目记为Dn,我们上面已经使用递推的证明方法,证明了Dn=(Dn-1+ Dn-2)*(n-1)。这时,其实证明已经大体完成了。


有了Dn=(n-1)(Dn-1+ Dn-2)就可以比较容易地推出Bernoulli-Euler装错信封问题的通项公式:




由于Dn=(n-1)(Dn-1 + Dn-2),


Dn + Dn-1= (n-1)(Dn-1 + Dn-2)+ Dn-1 = n*Dn-1 -Dn-1 + (n-1)Dn-2 + Dn-1 = n*Dn-1+ (n-1)Dn-2


也就是,Dn - n*Dn-1 = - Dn-1 + (n-1)Dn-2


Dn -n*Dn-1 = - [Dn-1 - (n-1)Dn-2 ],


从这个式子,我们有,


D3 - 3*D2= - [D2 - 2D1 ]

D4 - 4*D3= - [D3 - 3D2 ] = -1 * -1 * [D2 - 2D1 ]

D5- 5*D4 = - [D4- 4D3 ] = -1 * -1 * -1 * [D2 -2D1 ]


这表明,Dn- n*Dn-1 ,是以D2 - 2D1 = 1(因为D1=0D2 = 1D3= 2D4=9 ......为首项,公比为-1的等比数列。


于是Dn- n*Dn-1 = -1n-2,故Dn= n*Dn-1 +-1n,n≥2 n为正整数。



作者供图



Dn/n! = (-1)2 * (1/2!) + (-1)3 * (1/3!) + ...... +(-1)n-1* (1/n-1!) + (-1)n * (1/n!)




这个公式实际上可以进一步化简为 Dn = (n!/e + 0.5),e为自然对数的底。


回过头来看一下,这正是第8集里202住户、数学系学生黑岛沙和写的公式。


《轮到你了》剧照


在第二季中,入住304房间的新人物二阶堂忍与202住户黑岛沙都就读于国际理工大学,二阶堂忍是研究生,正在研究AI人工智能。第二季剧情中,他在帮助男主角用AI程序分析目前的数据,对凶手特征做测写。


新来的研究人工智能的住户和黑岛 |《轮到你了》


总之,让我们期待两名学生的表现吧,也希望之后给大家带来更多数学科普,大家准备好小铅笔一起来算吧!


作者:小青

编辑:李子,樟脑玩

数学审核:gsx



本文来自果壳,未经授权不得转载.

如有需要请联系sns@guokr.com

(欢迎转发到朋友圈~)



果壳

ID:Guokr42

靠谱科普

就看果壳




概率问题谁不会啊?AI喊你来群落做题啦——


请听题:四个同学将各自的一张明信片随意放在一起互相交换,恰有一个同学拿到自己写的明信片的概率是多少?快写出你的答案!


BTW,我们设置了小小的门槛,相信热爱科学的你肯定会通过考验!扫描下面的二维码,在42秒内答对尽可能多的题,达到一定分数才可以加入,每24小时仅能答题一次。呼~深吸一口气,然后好好答题吧!


AI和同事们等你来玩哦~




最值得关注的微信公众号