Matrix67 |
2011-06-13 22:16 | 
某大公司有这么一个规定：只要有一个员工过生日，当天所有员工全部放假一天。但在其余时候，所有员工都没有假期，必须正常上班。这个公司需要雇用多少员工，才能让公司一年内所有员工的总工作时间期望值最大？
假设一年有 365 天，每个员工的生日都概率均等地分布在这 365 天里。
Jun
13
May
23
最近忙于写学年论文，一直没时间更新 Blog 。不过，我却并没有停止在网上闲逛的习惯。这几天会慢慢把最近看到的有意思的东西写下来。今天学到的一个比较有趣的东西就是：平均等待时间往往大于平均间隔时间的一半。
比方说，有这么一趟公交车，平均每 10 分钟发一班车，但具体的发车时间是很不固定的。如果你在某个时刻来到车站，等到下一班车平均要花多久呢？很多人或许都觉得，平均等待时间应该是 5 分钟，毕竟平均间隔时间是 10 分钟嘛。然而事实上，平均等待时间是大于 5 分钟的。这是因为，10 分钟的发车间隔只是一个平均值，实际间隔有时是几分钟，有时是十几分钟。如果你出现在车站的时刻，正好位于几分钟的间隔中，你的平均等待时间显然就会小于 5 分钟；但如果你出现在车站的时刻，正好位于较长的间隔中，那么你的平均等待时间就会大于 5 分钟。关键就在这里：你出现在车站的时刻，更有可能落在了较长的发车间隔中。因而，平均等待时间会偏向于大于 5 分钟的情况。
那么，如果公交车发车的时间足够随机，概率均等地分布在时间轴上（假设平均间隔仍是 10 分钟），那么当你来到车站时，平均需要多久才能等到公交车呢？答案或许很出人意料——平均等待时间就是 10 分钟。下面我们就来证明这一点。
Feb
7
依次考虑下面三个问题。
1. 一根单位长的木棒。随机在中间选取一点，把这根木棒折断。那么，短的那一截木棒平均有多长？
2. 一根单位长的木棒。随机在中间选取一点，把这根木棒折断。那么，长的那一截木棒平均有多长？
3. 一根单位长的木棒。随机在中间选取一点，把这根木棒折断。那么，短的那一截与长的那一截的长度之比平均是多少？
Aug
8
数学常数最令人着迷的就是，它们常常出现在一些看似与之毫不相干的场合中。 随便取一个 0 到 1 之间的数，再加上另一个 0 到 1 之间的随机数，然后再加上一个 0 到 1 之间的随机数⋯⋯直到和超过 1 为止。一个有趣的问题：平均需要加多少次，才能让和超过 1 呢？答案是 e 次。
Jan
6
偶然读到一个非常帅的证明：用信息熵可以瞬间证明素数有无穷多个。这个证明比本 Blog 之前讲过的五种非主流证明 (282, 539, 1678) 看上去都要帅，并且更重要地，它道出了素数无穷多的根本原因：只有无穷多的素数，才有能力表达出如此丰富的自然数世界。
假设我们从所有不超过 n 的自然数中随机选取一个数 N ，并把它分解成质因数的乘积 N = P1^X1 * P2^X2 * ... * Pm^Xm，其中 m 是不超过 n 的素数的个数。注意到由于 2^Xi ≤ Pi^Xi ≤ N ≤ n 对所有 i 都成立，因此我们有 Xi ≤ log(n) 。真正帅的地方来了。考虑随机选取一个 N 带来的信息熵，我们有：
log(n) = H(N)
= H(X1, X2, ..., Xm)
≤ H(X1) + H(X2) + ... + H(Xm)
≤ log(log(n)+1) * m
上面的第一个等号是由信息熵的定义直接得出的。第二个等号是由唯一分解定理得到的：由于一个数可以唯一地分解为质因数的乘积，因此 N 和 (X1, X2, ..., Xm) 是一一对应的，知道了前者也就确定了后者，它们的信息熵是相同的。第三行的不等式是由于我们放开了 Xi 的取值条件（每个 Xi 独立取值可能会导致它们的乘积超过 n ），必然会增加结果的不确定性。而每个 Xi 的取值范围不会超出 0 到 log(n) ，最多 log(n)+1 种情况，因此 H(Xi) ≤ log(log(n)+1) ，这就得到了第四行的那个不等式。
整理上式，我们得到了 m ≥ log(n) / log(log(n)+1) ，这不但告诉我们当 n 趋于无穷大时不超过 n 的素数个数也是趋于无穷的，还给出了不超过 n 的素数个数的一个下界。
Dec
27
如果你身上没有任何可以使用的工具（手机、mp3、手表、尺子、纸和笔等等），也无法寻求别人的帮助，碰巧这时你突然急需获取一个小于10的随机自然数，你该怎么办？
先抛砖引玉，说说我自己想到的一些办法：
- 取当前年月日之和的个位数（理论上随机性不佳）
- 憋住呼吸并循环慢念0到9这十个数，在吸下一口气之前看念到多少（潜意识会导致随机性不佳）
- 拔10根头发，看第几根最长（可以边拔边比并不断更新最大值）
- 回忆一下看有多少天没来那个了，取个位数（只适用于女性）
- 看身上一共有多少块钱，取个位数
- 完整地唱完一首歌，取歌词字数的个位数
- 随意想一个英文单词，算出所有字母的ASCII码之和并模10
你还能想到哪些有趣的算法？欢迎在下面留言讨论，我会把有意思的留言在这里更新出来。
Nov
6
重要通告：最近多次发现我的tom邮箱发出的邮件被识别成了垃圾邮件，是什么原因我还不是很清楚。最近向我的tom邮箱发过邮件但迟迟没有收到回复的朋友麻烦检查一下垃圾邮件箱，或者重新给我发一次邮件，我换一个邮箱回复您。
数学学习真正悲哀的就是，记住了某个神奇而伟大的定理，看懂了其最严密的推导过程，但却始终没能直观地去理解它。虽然严密的推导是必要的，直观理解往往是不准确的，但如果能悟出一个让定理一瞬间变得很显然的解释，这不但是一件很酷的事，而且对定理更透彻的理解和更熟练的运用也很有帮助。我惊奇地发现，国内的每一本高数课本上都严格地讲解了微积分基本定理的证明，但几乎没有任何一个课本上讲过积分等于函数下方的图形面积究竟是为什么。事实上，这几乎是显然的，但还是有不少人学完微积分后仍然没有意识到。每当谈到这个问题时，我更愿意首先提出一个非常有启发性的事实——圆的周长是2·pi·r，圆的面积就是pi·r^2，后者的导数正好就是前者。这个现象是很容易理解的，因为圆的半径每增加一点，面积增加的就是周长那么一圈，换句话说面积的变化就等于周长。类似地，如果你能找到一个函数g(x)，它的导数正好就是f(x)，那么当x每增加一点，g(x)就增加了一条小竖线段，显然g(x)就应当是f(x)下方的面积。看清了这一点之后，我们才能欣赏到微积分基本定理真正牛B的地方。原先大家都是用分割求极限的办法来求函数下方的面积，但Leibniz却把面积看作一个可变的整体，用一种办法“一下子”就把它求了出来。有趣的是，这种现在看来如此自然的神奇办法，一千多年来居然没有任何人想到。
Jul
20
假设我们俩各自独立地随机选取一个有无穷多个顶点的图（两点之间1/2的概率有边1/2的概率没有边）。那么，我们俩选到相同的图的概率是多少？
令人难以置信、但想通了之后又异常显然的是，两个图相同的概率为1。并且，我可以精确地告诉你，这个相同的图是什么样子的。考虑这样一个无穷大的图，我们用自然数1, 2, 3, ...给所有顶点标号，然后如果y的二进制表达中的右起第x位为1，就在顶点x和顶点y之间连一条线。比如，顶点5就和顶点1、顶点3相连。我可以证明，我们俩都100%地会选取到上述这个图。
