生日悖论外传：任取两个人生日相同的概率是50%

    对原题的误读，有时竟会产生一些更有意思的问题。果壳问答上，网友 qxx 提问说：

一个房间里面有很多人，我想让房间里面任意两个人的生日相同的概率是 50% 的话那房间里面应该最少有多少人？

    当然，几乎可以肯定，提问人原本是想说“至少两个人”的，而问题的答案就是 23 ——生日悖论带来的惊人的答案。不过，如果把“至少两个人”误说成“任意两个人”，题目意思就完全变了，并且变得明显更有意思了。

    大家很快便会想到，如果任取两个人，他们的生日相同的概率恰好是 50% ，那么房间里最少有四个人，其中三个人的生日是同一天，另外一个人的生日跟他们都不同 。从四个人里选出两个人有 6 种方案，选出生日相同的两人则有 3 种方案，恰好是 6 的一半。

    继续看下去之前，大家不妨来猜猜看，这个问题还有其它的解吗？下一个解有多大？


    问题的本质就是，把 n 拆分成 n1 + n2 + … + nk ，使得 C(n1 , 2) + C(n2 , 2) + … + C(nk , 2) 正好等于 C(n, 2) 的一半。下一个解发生在 n = 9 的时候，其中有 6 个人拥有共同的生日，另外 3 个人拥有另一个共同的生日。我们不妨把这个解简记作 9 ＝ 6 + 3 。
    我用 Mathematica 进行了一些简单的搜索，得到了 n < 40 时全部的解：

4 = 3 + 1
9 = 6 + 3
13 = 9 + 3 + 1
16 = 10 + 6
17 = 12 + 2 + 2 + 1
20 = 14 + 3 + 2 + 1
21 = 15 + 1 + 1 + 1 + 1 + 1 + 1
24 = 17 + 2 + 2 + 1 + 1 + 1
25 = 15 + 10
28 = 19 + 6 + 3 = 18 + 9 + 1
29 = 20 + 5 + 3 + 1
32 = 22 + 6 + 2 + 2
33 = 23 + 5 + 2 + 1 + 1 + 1
36 = 25 + 6 + 1 + 1 + 1 + 1 + 1 = 25 + 4 + 4 + 3 = 24 + 9 + 3 = 21 + 15
37 = 26 + 4 + 2 + 2 + 1 + 1 + 1 = 26 + 3 + 3 + 2 + 2 + 1

    当 n ＝ 40, 41, 44, 45, 48, 49 时也是有解的，解的个数分别为 5, 3, 6, 3, 5, 8 。 n > 50 时我就没算了，不过估计解会越来越多。

    看上去，问题的解似乎很没规律， n = 8 时竟然无解想必会让不少人大吃一惊，而 n 是某些质数时却反而有不少解，这使得问题变得非常有趣。是否能找到一种构造解的方法，从而说明问题有无穷多解？解的个数与 n 之间存在什么关系？能否找到一种生成全部解的方法？这个问题之前有研究过吗？得出过什么有趣的结论吗？欢迎大家在下面一起来讨论。

37 条评论

发表评论

6  ×    =  6