踢球分组中的概率

以前暑假经常找同学一起踢足球，一般都能找到8个固定的同学，分成两组对抗。分组的方法是8个人围在一起，出示手心或手背，直到4个手心，4个手背的情况，就算分组成功。有时候会出现很多次都不成功的情况，很浪费时间，有个同学就想了个办法：他自己先站出去，由剩下的7个人先分，分成一组3个，一组4个的情况，最后他就直接加入3人的那一组，这样就会容易成功一点。

这样分组的方法真的会更容易吗？下面用计算概率的方法来验证。

方法一：排列组合

首先使用排列组合的思想来计算。对于原始的分组方式，每个人都有出示手心或手背两种选择，所以共有$2^8$种可能，但其中存在重复的情况，例如前2个人手心、后6个手背，与前2个手背、后6个手心的情况导致最后的分组是一样的，所以实际的情况共有$2^8/2$。只有当4个人出手心，4个人出手背，分组才成功，相当于从8个人中选出4个，为$\mathrm{C}_8^4$，但同样也存在重复情况，选择前4个人与选择后4个人的情况是一样的，所以成功的情况有$\mathrm{C}_8^4/2$。成功情况的数目除以所有情况的数目，得出成功的概率为：

$$\mathcal{P}_{old} = \frac{\mathrm{C}_8^4/2}{2^8/2} = \mathrm{C}_8^4(2)^{-8} = \frac{8\times7\times6\times5}{4\times3\times2\times1}(2)^{-8} \qquad \qquad (1)$$

现在，来计算新的分组方法成功的概率。新的方法实际上相当于7个人分组，分成一组3个和一组4个。使用相同的方法分析，可得所有可能的情况为$2^7/2$，成功的情况为$\mathrm{C}_7^3/2$。因此，新的分组方法成功的概率为：
$$\mathcal{P}_{new} = \frac{\mathrm{C}_7^3/2}{2^7/2} = \mathrm{C}_7^3(2)^{-7} = \frac{7\times6\times5\times2}{3\times2\times1}(2)^{-8} \qquad \qquad (2)$$
比较以上两个式子，不难发现两者是相等。

方法二：独立事件概率

下面使用独立事件的思想来计算概率。在没有人作弊的情况下，一个人出示手心或手背是一个独立事件，且出示手心或手背的概率各占50%（假设没有个人偏好）。那么，使用原始的分组方法，成功的情况为4个人出示手心，剩下的4个人出示手背，概率为：
$$\mathcal{P}_{old} = \mathrm{C}_8^4(\frac{1}{2})^4(\frac{1}{2})^4 = \mathrm{C}_8^4(2)^{-8} \qquad \qquad (3)$$
新的方法的概率为：
$$\mathcal{P}_{new} = \mathrm{C}_7^3(\frac{1}{2})^3(\frac{1}{2})^4 = \mathrm{C}_7^3(2)^{-7} \qquad \qquad (4)$$
以上两个式子的结果也是相等的，且也等于(1)，(2)。

推广到2n

现在将此推广到有N个人的情况，要分组成功，总人数必定为偶数，设为2n。使用独立事件的方法，可计算出原始方法的成功概率为：
$$\mathcal{P}_{old} = \mathrm{C}_{2n}^{n}(\frac{1}{2})^n(\frac{1}{2})^n = \mathrm{C}_{2n}^{n}(2)^{-2n} \qquad \qquad (5)$$
新方法成功的概率为：
$$\mathcal{P}_{new} = \mathrm{C}_{2n-1}^{n-1}(\frac{1}{2})^{n-1}(\frac{1}{2})^n = \mathrm{C}_{2n-1}^{n-1}(2)^{-(2n-1)} \qquad \qquad (6)$$
比较一下，两者也是相等。

由此可见，无论多少人踢球，新方法并不比原始方法更容易成功。

Liar Paradox and Halting Problem

Liar Paradox
首先来看一下什么是liar paradox。Liar paradox的雏形来自于一个叫作Epimenides的克里特人，他说：“所有克里特人都是说谎者。”这常常被认为等同于liar paradox，其实不然，因为如果他说的是真话，那么他就在说谎；如果他在说谎，说明至少还有一个克里特人说的是真话，这并不矛盾。最早的liar paradox版本是由生活在公元前4世纪希腊的麦加拉学派（Megarian）哲学家Eubulides提出的。他说：

A man says that he is lying. Is what he says true or false?

如果他说的是真的，那么他在说谎；如果他说的假的，那么他没在说谎。

后来又出现了一些liar paradox的变种，比较有名的有：

This sentence is false.

下面的悖论又名"Jourdain's Card Paradox"：有一张卡片，一面写着：

The sentence on the other side of this card is true.

而在卡的另一面却写着：

The sentence on the other side of this card is false.

Halting Problem
Halting Problem是计算理论中的经典问题。它的意思，简而言之就是：对于一段程序和有限的输入，决定其是终止还是永久运行。说白了就是设计一个算法来判断一段程序是否会进入死循环。Alan Turing在1936年证明了不存在这样的算法。

在SICP课程的最后一讲[4]中，为了说明不是任何事物都是可计算的，使用了这样一个例子来证明不存在halting problem的算法。

首先，假设存在这样的算法，则存在函数(halts? p)：

（halts? p)
=> #t if (p) terminates
=> #f if (p) does not terminates

现在有如下程序：

(define (contradict-halts)
    (if (halts? contradict-halts)
        (loop-forever)
        #t))

(contradict-halts)
=> ???????

很容易，我们可以定义(loop-forever)为：

(define (loop-forever)
    ((lambda (x) (x x))
    (lambda (x) (x x))))

这就是著名的Y combinator。

这里使用的就是liar paradox的精髓，如果这段程序会终止，则让它无限循环；如果程序不终止，则让它返回#t。

Resources
[1]. Liar paradox on Wikipedia.org
[2]. Some paradox
[3]. Halting problem on Wikipedia.org
[4]. Video courses of SICP

Russell's Paradox

Russell's Paradox是set theory中非常有名的悖论。

先来看一下set theory中一个有意思的集合：属于自己本身的集合，也就是说一个集合它包含了自己。例如，以所有集合为作用域来考虑，包含所有正方形的集合R，那么集合R并不包含自己，因为R是一个集合，而不是正方形。但是，取R的补集S，即所有非正方形的集合，那么S不是正方形，所以S是自己的一个元素，即S属于自己。可见，世界上存在很多这种包含自己本身的集合。

现在，令R为所有不属于自己的集合的集合（好绕阿！集合R中的元素也是集合），也就是说：

R ＝ {A | A不属于A}

那么，现在考虑R是否属于R。如果R属于R，那么这违背了R不属于自己的集合属性；如果R不属于R，那么根据集合R的属性，R应该是集合中的一个元素。这就是Russell's Paradox。

有一个与Russell's Paradox相关的理发师的故事。理发师在理发店前的牌子上写道：“我给镇上所有不给自己理发的人理发，而且我也只给这些人理发。”于是，有人问他：“那你自己怎么办呢？如果你不给自己理发，那么照你的说法就应该给自己理发；如果你给自己理发，那么你又不应该给自己理发，因为你只给不给自己理发的人理发。”理发师不知如何回答。

A cool proof of Pythagorean Theorem

More proofs are here: Pythagorean Theorem and its many proofs.