译言精选-最具争议的12个数学事实

译言精选-最具争议的12个数学事实

总有些出人意料的数学题，目的就是为了测试和提升人的智力极限。

下面这12个简单的数学题，在学生中引起了巨大的争议，但却都是无可争辩的事实。

他们都具有悖论和概率的特性，而且总是能引起一些争论。

如果你想通过数学的方法来打动朋友或迷惑敌人的话，那就往下看吧。

Read full article from 译言精选-最具争议的12个数学事实

明天太阳照常升起的概率是多少？

明天太阳照常升起的概率是多少？

在第三章"概率计算的一般原则"最后提到一个日出问题：

如果我们不了解太阳运行的基本规则，根据统计，在过去的N天里，太阳每天都正常升起。那么，太阳明天照常升起的概率是多少呢？

拉普拉斯在书中，指出蒲丰在著作《政治算术》中的结果 1 - (1/2) ^ N 是错误的。

正确的结果应该是 (N + 1) / (N + 2) 。 下面， 我尝试推导了一下。

推导过程，应用到第三章中提交的一些概率计算原则：

1. 第六个原则： 假定我们观测到一个经常发生的事件， 每一个被认为是导致它的原因成立的可能性被这个事件发生的概率显示。于是某一原因成立的概率是一个分数，其分子是这个原因导致此事件的概率， 而其分母是所有各原因的类似概率的和； 如果这些不同的原因被事先考虑为不是等可能时，就必须将由每个导致此事件的原因的概率代之以它与此原因本身的可能性的乘积。这就是由事件到原因的机会分析这一分支的基本原则。

2. 第七个原则： 将来的事件发生的概率是，所有引起被观测事件的原因发生的概率乘以在此原因下该事件发生的概率的乘积之和。

在我们这个问题中，

1. 观察到的现象(事件)为：过去的N天里太阳每天升起。 记为 Observation

2. 将来要估计的事件为： 明天太阳升起的概率。 记为Prediction

其实，我们希望求出 P(Prediction | Observation).

我们了解的背景知识不多， 太阳升起的概率假设为p， p是0到1之间任意一个值。 根据上面两条计算原则， 可以如下推导出答案：

Read full article from 明天太阳照常升起的概率是多少？

几道抛硬币问题 | 四火的唠叨

几道抛硬币问题 | 四火的唠叨

只是记录一下遇到的几道抛硬币的概率问题。

 

1、平均需要抛掷多少次硬币，才会首次出现连续的两个正面？

假设连续两个正面的期望是E，那么，先看第一次抛硬币：

1. 如果抛到反面，那么还期望抛E次，因为抛到反面完全没用，总数就期望抛E+1
2. 如果抛到正面，那么要看下一次，如果下一次也是正面，那抛硬币就结束了，总数是2；如果下一次是反面，那么相当于重头来过，总数就期望抛E+2

于是可以得到如下关系式：

E = 0.5(E+1) + 0.25*2 + 0.25(E+2)

得到所求期望E=6

现在把题目拓展，不是说"连续两个正面"，而是"连续n个正面"呢？

这个问题Matrix67有非常有趣的解答《用数学解赌博问题不稀奇，用赌博解数学问题才牛B》，下面我简述一下：

假设有一个赌场，赌博的方式就是猜正反，每来一个玩家来的时候都只带了1元，每次都会全部下注，然后赌正面，庄家抛硬币，如果猜错就是全部输掉，如果赢了就得到下注的两倍，玩家会一直玩一直玩直到钱输光；而赌场老板会看，如果有人赢到2^n元，就下令关闭赌场。

于是直到n次正面朝上的情况发生，赌场关闭，只有最后那n个人才赚到了钱，最后一人得到了2元（没算成本价1元），倒数第二人是4元……倒数第n人是2^n元，所以，一共得到（等比数列求和）：

2+4+8+…+2^n = 2*(1-2^n)/(1-2) = 2^(n+1) �C 2

赌场有多少钱流入，自然就有多少钱流出，所以到赌场倒闭，玩家赢得的钱的总数，就应该等于赌场期望的收入。而因为每个人来的时候都只带了1元，因此这个数正好等于期望的人数。于是这就是最终答案。

 

2、一堆硬币，每天都随便捡一枚抛，如果抛到正面，就把它翻过来；如果抛到反面，就再抛一下，问很长很长时间以后，硬币正面和反面的比例会趋近于多少？

假设正面的比例是x，那么反面就是1-x，对于任意一次操作：

• 如果抛到正面，那么得到的就一定是反面了；
• 如果抛到反面，那么得到正面的可能性为0.5，反面的也为0.5。

所以得到正面的综合起来的概率为：

x*0 + (1-x)*0.5 = x

所以x = 1/3，因此硬币正面和反面的比例会趋近于x/(1-x) = 1/2

 

3、连续抛硬币，直到第一次出现连续两次正面为止，恰好抛了N次的概率是多少？

考虑"恰好"抛N次硬币，到底有多少种情况可以得出最后两次是连续出现了正面，而之前没有出现过连续正面。

• 假设f(x)表示第一次出现连续正面的时候，已经抛了x次，并且整个过程的第一次抛出的结果是反面；
• 假设g(x)表示第一次出现连续正面的时候，已经抛了x次，并且整个过程的第一次抛出的结果是正面。

所以f(1)=f(2)=0，g(1)=0，g(2)=1，而当x>2，

• 求f(x+1)，因为第一次是反面，所以这新添加的第一次不影响结果，因此f(x+1)=f(x)+g(x)
• 求g(x+1)，因为第一次是正面，必须要保证第二次不能为正，所以g(x+1)=f(x)

于是得到：

f(x+2)=f(x+1)+g(x+1)=f(x+1)+f(x)

g(x+1)=f(x)

其中，求f(x)的递推式可以看出f(x)是斐波那契数列，根据它的通项公式：

得到f(N)，也就得到了g(N)，而总抛的可能性共有2^N次方，因此，概率为：

(f(N)+g(N))/2^N

 

 

4、抛硬币N次，出现连续M次正面的概率是多少？

这个问题也很常见，但是做起来没那么容易，这里有一个非常详细的讨论过程（链接），我就不搬过来了。

 

5、抛N次硬币，正反两面出现次数相同的概率是多少？

其实就是从N个硬币的空位中，选出N/2个作为正面，余下N/2个作为反面，应用组合公式可得到：

C(N,N/2)/2^N=N!/((N-N/2)!(N/2)!)/2^N

继续，

正面出现次数超过反面的概率？

因为正反情况相同，因此正面次数超过反面的概率应当等于反面次数超过正面的概率，因此结果为1减去上面那一问的结果之后除以2：

(1-C(N,N/2)/2^N)/2

Read full article from 几道抛硬币问题 | 四火的唠叨

智力题以及概率题 - Backyard of LixinZhang

智力题以及概率题 - Backyard of LixinZhang

一个是如果两个质数中间只有一个数，那么证明他能被6整除？

分析

G,E,A,B,C,D,F

• 设三个数为A,B,C。因为A,C为质数，一定不是偶数，则B一定为偶数。
• 因为不长为三的一定会出现被3整除的数字，由于A,C为质数不能被三整除，因此A的左边E和C的右边D一定不能被三整除。
• 那么E的左边G必须能被3整除，因为不能可能连续的3个数都不能被三整除，因此B=G+3，能被3整除，其又能被二整除，因此必须能被6整除，证毕。

Read full article from 智力题以及概率题 - Backyard of LixinZhang

Coupon collector's problem

https://en.wikipedia.org/wiki/Coupon_collector%27s_problem
the coupon collector's problem describes the "collect all coupons and win" contests. It asks the following question: Suppose that there is an urn of n different coupons, from which coupons are being collected, equally likely, with replacement. What is the probability that more than tsample trials are needed to collect all n coupons? An alternative statement is: Given n coupons, how many coupons do you expect you need to draw with replacement before having drawn each coupon at least once? The mathematical analysis of the problem reveals that the expected number of trials needed grows as .^[1] For example, when n = 50 it takes about 225^[2] trials to collect all 50 coupons.

赠券收集问题

赠券收集问题的特征是开始收集时，可以在短时间内收集多种不同的赠券，但最后数种则要花很长时间才能集齐。例如有50种赠券，在集齐49种以后要约多50次收集才能找到最后一张，所以赠券收集问题的答案t的期望值要比50要大得多。

http://www.cnblogs.com/lailailai/p/4886389.html

以一个例子来说明：有种食品每袋都会附赠一张卡片，共有10种卡片，每种卡片出现的概率相等。

首先来求当拥有i种卡片时，再拆开一袋得到不同卡片的概率Pi：

a. 当我们没有任何卡片时，随意拆开就能得到一种不同的卡片，即第一种得到的卡片P0 = 1

b. 当有了一种继续拆，此时得到新的种类的概率为P1 = 9 / 10
...当有了i种，此时得到新种类的概率为Pi = (10 - i) / 10

我们知道了Pi的值，那么对于拆了i包后，拆开发现新卡片的次数期望为E = Pi * Ni，由于只需要然其发生一次即可令E=1反过来求对应的Ni，Ni = 1 / Pi，即拆1 / Pi包时可以发现一种新卡片（相对于已经拥有i种卡片）。

那么发现全部卡片总共需要的包数 = N0 + N1 + N2 ... N9 = 10 / 10 + 10 / 9 + 10 / 8 ... 10 / 1 = 29.289682539682538

即按期望来，买30包可以集齐卡片。

下面给出了卡片等概率出现时，集齐卡片的期望次数：

1 1.0
2 3.0
3 5.5
4 8.33333333333
5 11.4166666667
6 14.7
7 18.15
8 21.7428571429
9 25.4607142857
10 29.2896825397
11 33.2186507937
12 37.2385281385
13 41.3417388167
14 45.5218725719
15 49.7734348984
16 54.0916638917
17 58.4723928849
18 62.9119454075
19 67.4070534857
20 71.9547931429
21 76.5525328
22 81.1978915048
23 85.888704755
24 90.6229962661
25 95.3989544438
26 100.214912622
27 105.069332338
28 109.960789091
29 114.88796013
30 119.849613928
31 124.844601059
32 129.871846254
33 134.930341449
34 140.019139675
35 145.137349666
36 150.284131085
37 155.458690281
38 160.660276505
39 165.888178519
40 171.141721557
41 176.420264596
42 181.723197879
43 187.049940686
44 192.399939306
45 197.7726652
46 203.167613315
47 208.584300561
48 214.022264403
49 219.481061578
50 224.960266916
51 230.459472255
52 235.978285436
53 241.516329387
54 247.073241262
55 252.648671656
56 258.242283868
57 263.853753223
58 269.482766437
59 275.129021031
60 280.792224777
61 286.47209519
62 292.168359046
63 297.880751933
64 303.609017837
65 309.352908741
66 315.11218426
67 320.886611294
68 326.675963702
69 332.480021991
70 338.298573035
71 344.131409792
72 349.978331057
73 355.839141211
74 361.713649994
75 367.601672291
76 373.503027922
77 379.417541447
78 385.345041986
79 391.285363037
80 397.238342316
81 403.203821595
82 409.181646553
83 415.171666632
84 421.173734905
85 427.18770794
86 433.21344568
87 439.250811328
88 445.299671228
89 451.359894765
90 457.431354256
91 463.513924859
92 469.607484473
93 475.711913652
94 481.827095519
95 487.952915684
96 494.089262165
97 500.236025313
98 506.393097739
99 512.560374246
100 518.737751764
101 524.925129282
102 531.122407789
103 537.329490219
104 543.546281386
105 549.772687938
106 556.008618299
107 562.253982622
108 568.50869274
109 574.772662118
110 581.045805807
111 587.328040405
112 593.619284012
113 599.919456191
114 606.228477927
115 612.546271593
116 618.872760911
117 625.207870919
118 631.551527936
119 637.903659528

E = n / n + n / (n-1) + n/ (n-2) ... n / 1

当卡片出现的概率不是相等的时候，Pi的计算过程就麻烦许多

Inclusion–exclusion principle

https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as

The principle is more clearly seen in the case of three sets, which for the sets A, B and C is given by

http://math.illinoisstate.edu/day/courses/old/305/contentderangements.html

Suppose we want to determine the number of derangements of the n integers 1,2,...,n for n bigger than 2. Let us focus on k and move it into the first position. We thus have started a derangement, for 1 is not in its natural position. Where could 1 be placed? There are two cases we could consider: either 1 is in position k or 1 is not in position k.

If 1 is in position k, here's what we know: The integers 1 and k have simply traded positions.

Prohibited Value	1	2	3	...	k-1	k	k+1	...	n
Derangement	k	?	?	...	?	1	?	...	?

Indicated by the question marks, there are (n-2) integers yet to derange. This can be done in D(n-2) ways.

If 1 is not in position k, we don't know as much. Note that we have shown 1 as a prohibited value twice. This is required for this case, because we cannot have 1 appear in the first position (its natural position) nor can 1 appear in position k.

Prohibited Value	1	2	3	...	k-1	1	k+1	...	n
Derangement	k	?	?	...	?	?	?	...	?

Indicated by the question marks, there are now (n-1) integers yet to derange. This can be done in D(n-1) ways.

Putting this together, we have D(n-1) + D(n-2) possible derangements when k is in the first position. How many different integers could we put in position 1 and carry out this process? All the integers except 1. that is, (n-1) different integers.

This yields the recursive formula D(n) = (n-1)[D(n-1) + D(n-2)]. As long as we know D(1) = 0 and D(2) = 1, we can generate subsequent values for D(n).

Puzzles, Maths and Algorithms: Innocents and Criminals: Finding Minority Entity

Puzzles, Maths and Algorithms: Innocents and Criminals: Finding Minority Entity

Innocents and Criminals: Finding Minority Entity

Problem: There are two types of people in a particular city, innocents and criminals. All you know is that innocents are in majority and would like to get rid of criminals and criminals would like to protect themselves from persecution. You can ask any number of questions, with yes/no type answer, from any person in the city. Propose an algorithm which requires asking the minimum number of questions.

Read full article from Puzzles, Maths and Algorithms: Innocents and Criminals: Finding Minority Entity