SGi's Blog

所有人都应该学学经济学和概率论这两门课，这代表着两种在生活中的思维方式。

来测试一下你的概率论学得怎么样吧，做完的话，回复以后我会把答案发到你留下的邮箱里的。对8题以上的话，我请你吃饭。

题目作者: wzz12346@newsmth, 原发表于Mathematics@newsmth。

如果有题不会的话，就用你的直觉吧，看看最后你的直觉与真实的概率相差有多大。

1、给一个1-n的排列，与原来位置相同的数字的个数的期望大约是 （如 n=5 则51324 与原来位置比较，只有一个数”3″是位置相同的）
A.  1
B.  log(n)
C.  ln(n)

2、如果有3个门，有一个背后有大奖。你选中一个，主持人知道哪个门后面有奖，并且总会打开另外两个中的某个没奖的。现在你有一次换得机会，你应该
A.  换
B.  不换
C.  换不换都一样

3、以下那件事情发生的期望时间最短
A.  在第0秒，一个物体从原点出发，每一秒以概率1/2向左走，1/2向右走，第一次回到原点的时间
B.  一只猴子，每秒种随便按键盘上的一个键，第一次打出”Beijing Welcomes You”的时间
C.  在第0秒，一个物体从原点出发，每一秒以概率1/2向左走，1/2向右走，第一次到达1的时间

4、美国的25分硬币共有50种，上面有50个州的图案，如果我们每次得到的硬币是随机的，则期望大约收集多少可以收集全
A.  200
B.  300
C.  400
D.  500

5、假设有1000次100m短跑大赛，每次比赛的冠军成绩都在9.7-10之间均匀分布，问期望有多少次比赛打破了之前的纪录
A.  7
B.  10
C.  15
D.  32

6、在打桥牌的时候，如果你和对家共持有某门花色的9张牌，则剩余的4张牌怎样分布的概率最大
A.  2-2
B.  3-1
C.  4-0

7、如果一个物体在3维随机游动，也即每一刻他可以向左，右，上，下，前，后等概率的走，长久来看，则会发生什么情况
A.  此物体无穷多次回到原点
B.  此物体无穷多次回到任何一条坐标轴上，但不会无穷多次回到原点
C.  此物体不会无穷多次回到任何一条坐标轴上

8、扔10000次硬币，其中最长一次连着正面的次数大约会是多少
A.  100
B.  13
C.  9
D.  4

9、有一支股票，初始价为1，每天的价值变化率独立同分布，且期望为0，不恒为0。则
A.  股票在任何时刻期望价值为1
B.  股票以概率1变成0
C.  A和B都对
D.  A和B都不对

10、当我们考虑一种可能重复发生的事件时，哪种方式更科学
A.  按照第一次发生这个事件的时间作为一个起点，考虑从其本身出发之后的性质
B.  按照最后一次发生这个事件的时间作为一个起点，考虑从其本身出发之后的性质
C.  以上都可以
D.  以上都不可以

11、100个球随机的放在100个箱子里，最后空箱子的数量大约是
A.  0-0.1
B.  0.1-0.2
C.  0.2-0.3
D.  0.3-0.4

12、打10000副拱猪，总共持有9500-10500个A的概率大约在
A.  80%-90%
B.  90%-95%
C.  95%-99%
D.  99%以上

13、有以下几个国家，每个国家有自己的习俗。问哪个国家长期以后男人最多
A.  每个家庭不断的生孩子直到得到第一个男孩为止
B.  每个家庭不断的生孩子直到得到第一个女孩为止
C.  每个家庭不断的生孩子直到得到一男一女为止
D.  以上几个国家最后男女比例基本一样

14、实验室测试灯泡的寿命，在灯泡不断的换新灯泡。灯泡寿命约为1小时。考察10000小时时亮着的那个灯泡
A.  那个灯泡的寿命期望也约为1小时
B.  那个灯泡的寿命期望约为其他灯泡的2倍
C.  那个灯泡的期望寿命约为其他灯泡的1/2
D.  以上说法都不对

15、如果一个群体里，每个个体以0.2的概率没有后代，0.6的概率有1个后代，0.2的概率有两个后代，则
A.  这个群体最后会灭绝
B.  这个群体最后将稳定在一个分布，即种群大小在一定范围内震荡
C.  这个群体最后将爆炸，人口将到无穷
D.  不一定会发生什么

问题描述：

有N根柱子，现在有任意正整数体积的球各一个，请你把尽量多的球放入这N根柱子中，满足：

1.同一根柱子中，体积小的球在体积大的球的下面；
2.同一根柱子中，相邻两个球的体积和为完全平方数；
3.放入的球的体积必须从1开始连续。

请问，你最多能放多少个球在这N根柱子上？

解题报告

图论法：

逆向思维，转而判断N个球最少需要几根柱子。
构造图G，G有N个顶点，代表标号为1..N的球；如果i<j并且i+j是整数平方，那么顶点i存在指向顶点j的边。图G的最小覆盖路径数即是最少所需的柱子数目。
最后二分求解当有k根柱子时，最多能放几个球。

贪心法：

结论：对于N根柱子，最多可以放的球数 f(n) = Trunc((n^2+2n-1) div 2)

证明：

首先证明最优性，

故此n+1个球中，任两个的编号之和M满足

故M不可能为完全平方数，从而这n+1个球不能有两个在一根柱子上，这与至少需要n+1跟柱子矛盾，得证。

然后证明可行性，
利用数学归纳法证明
命题：
对于N根柱子，存在一种队f(n)个球的方法，使得N根柱子最顶上的那个球的编号依次为f(n)、f(n)-1、…、f(n)-n+1
证明：
当N=1时，f(N)=f(1)=1，命题显然成立。
假设当N=k时（k为正整数），命题成立。
则当N=k+1时，想加编号1、2、…、f(k)的球放入k根柱子，使得这k根柱子最顶上的一个球的编号分别为f(k)、f(k)-1、…、f(k)-k+1。
不妨设第i(1<=i<=k)根柱子最顶端的球的编号为f(k)-i+1。

这样每根柱子顶上的球的编号依次为f(k+1)、f(k+1)-1、…、f(k+1)-k，得证。

综上所述，f(n) = Trunc((n^2+2n-1) div 2) 为最优解

构造方法：
当n=1时，把小球1放在第1根柱子上；当n=2时，第一根柱子上放入小球1、3；第二根柱子上放入小球2；当n>2时，先构造出n-1根柱子放入f(n-1)个球的方案；然后添加一根柱子，把f(n-1)+1…f(n)这些球放进来，放的方法如下：

若n为奇数，则按类似n=7时这种顺时针回旋的放法放入：
把f(n-1)+1和f(n-1) +2放在第n根柱子上；然后把f(n-1)+3.. f(n-1)+(n+3)/2依次放在第(n-2)、(n-4)..1根柱子上；再把f(n-1)+(n+5)/2..f(n)依次放在第2、4..(n-1)根柱子上。

当n为偶数时，则按类似n=8时这种逆时针回旋的方法放入：
填放方法的具体描述和n为奇数时大同小异，可以根据图中的箭头找出规律。

（N=31是的填入情况）

（N=39时的填入情况）

按这种方法填放，是否一定满足题中的所有条件呢？

1.先“同一根柱子中，体积小的球在体积大的球的下面”这一条件很明显满足；
2.另一个条件“同一根柱子中，相邻两个球的体积和为完全平方数”这一条件也很容易证明：根据填放的规律，很容易知道当n为偶数时只要满足[f(n)]+[f(n-2)+2]为完全平方数、当n为奇数时[f(n-1)+1]+[f(n-1)+2]为完全平方数即可；而根据f(n)的定义可算出他们恰巧都为n^2；

通常我们认为人们在作出决定前已较好的了解了情况，比如投票支持的对象，但事实并非总是如此。缺乏信息是一方面，但在另一方面，如果有大量人口在涉及到全国争论或民主进程的问题上被积极的误导，假如政治学家的发现是正确的话，纠正不实的信息除了增强错误信念外什么也得不到。
纠正错误信息只会加强错误信念也许是有些争议的提法，但这一说法是基于多种研究，有许多研究调查了政治影响或意识形态偏见在修正事实后的表现。例如在研究中，志愿者首先被展示包含错误信息的政治广告或新闻，然后被告知正确信息。令人感兴趣的是，许多人会坚持错误观点，即使被告诉它是错误的。在现实中我们也能得到印证，比如相信奥巴马是穆斯林的人数在增长，而在中国，相信西方媒体对中国有偏见的观点显然得到了加强。

(Read on …)

以下转载自北大BBS

刚才看到这里的帖子，谈到工作的，我来写一点把。

1，我刚工作的时候，在一家小公司，很小很小的。和我一起进去的另外2个都是普通一点的学校的。我们刚去的时候，基本上有了电话都是我站起来跑过去接，其它人根本就不动身。以至于到了后来，电话一响，如果我不起身，大家就会一直等着，一直等到我终于忍不了了起身去接。每天下班以后，我要检查办公室的垃圾袋，看看是不是需要把垃圾袋提走。而其他人，比如老员工和另外的实习生，他们根本不会去提垃圾袋。我是北大人。我不狂。

2，工作形势非常严峻。尤其是对于刚毕业的学生。如果是大公司，它们可能有能力支付生手的培训时间和金钱，也有能力承受生手因不熟悉业务而给公司带来的损失，但是对于绝大部分小公司，它们根本就不愿意或者说无法承受这些。所以在一个大专毕业的熟手和一个北大毕业的生手中间，他们宁可选择前者。

3，中关村乃至海淀乃至北京，是一个廉价高等教育人才市场。这个大环境决定了我们在用人单位眼里，都是金属，而不是金子。在这里，大学生就是廉价劳动力，商人看刚毕业的大学生的感觉，和建筑工地上包工头看民工的眼光没有任何区别。尤其在以赚钱为唯一目的的大部分小公司。所以，刚毕业的同学最需要做的，就是赶紧让自己成为一个熟工。

4，在学校的时候，多交几个真心的朋友。因为工作以后，你可能就永远丧失了交朋友的权力和勇气。特别是同事，你可能一直到离开某个单位的时候，你都恋恋不舍，觉得这个单位的同事很不错。但是没准在后来的某一天，你突然因为偶然的机会发现，每天对你温柔微笑的同事曾经在你背后捅了一刀或n刀，而这些刀的直接后果就是你滚蛋。

5，在学校的时候，好好享受自尊的感觉。有人说，他读大学的时候，以为他毕业后要变成一条狗只需要3年的时间，但是工作后，他发现对自己真是太不自信了，其实要变成一条狗根本不用3年，半年就足够了。这话是我大4时看见的，过了2年后，我发现这条伟大真理完全可以和牛顿定律媲美。我们在北大里，享受的是中国最大的自由和民主，这是个可怕的甜蜜。因为当你第一次受到指着鼻子的责骂时你一下子无法接受。

6，你在北大的时候，可能会觉得某人很俗。离开北大的时候，你可能会立志你绝对不要俗。但是过了几年后，你会发现只有那些完成了由不俗到俗的成功转变的同学才能衣着不俗地叁加聚会，而那些尚未完成转变的同学则可能潦倒落魄地出现在你面前。所以，当你在学校的时候，千万不要讥笑（哪怕是在心里）身边那些俗又俗的同学，因为他们很可能就是将来同学聚会上的主角，也是你mm对你进行再教育的榜样。

7，当你在北大的时候，千万不要看不起那些在西门外那排小平房租房准备以考研方式杀进北大的年轻人，他们中的某些人在你看来可能很功利、没有道德观、为了目的不达手段。但是你工作后你会发现这3点恰恰是北大没有教给我们的生存技能。如果我们能够掌握这3点，再加上我们的学历背景，北大人一定会战无不克。事实上，我们中的大部分人在离开学校后都会往这个方向努力，所以，他们其实是很值得尊敬的，因为他们比我们成熟得要早。他们可能在更年轻得时候就受过挫折，所以他们懂得从此以后拼命。而我们一直是幸福宝宝，等到毕业的时候才开始接受人生中第一次真正意义上的挫折，所以我们拼命得比他们要晚了很多。

8，在我们所受到的教育里，师长一直告诉我们要诚实、对人真诚。还有，中国的老话叫“买卖不成仁义在”。这在企业竞争已经到人性化程度的西方世界可能还是真理，但是在现在的中国商场上那是……胡说。举个例子吧，我的诚实让公司失去了一个客户，让我个人赢得了一个朋友；当这个朋友因我的诚实而给我带来一个大买卖时，我已经被公司老板因那次业务失败而炒了鱿鱼；所以最后我把这宗大买卖带到了新服务的公司。
这件事的结果最后是好的；但是这只是一个幸运的偶然。我想大部分人不会这麽幸运。工作以后，如果你每天统计一下，你会惊讶于自己现在从早晨走进办公室的那一刻起就开始说假话，这假话对同事说、对老板说、对客户说、一直说到家里，如果你的女友or男友还没有工作，而是留在学校上研上博（就像我的情况），你会让他们大为震惊，他们很可能悲痛欲绝地对你说“你怎麽能这麽说？”然后，你可能更加愤慨地对她or他说：“这只是交际的
手段/业务的需要/如果你能给我提供一个饭碗我肯定不这麽说……”最后的最后，你们很可能对彼此失望，比如，对方觉得你变了；你觉得对方too naive，too simple，不理解你，在你每天承受压力的同时还要给你放一把火；然后最后的最后，你们很可能分道扬镳。

(Read on …)

所谓素数筛法就是那个求小于n的所有素数最简单的算法：

1
2
3
4
5
6
7
8
9
10

bool* prime(int n)
{
  bool *p = new bool[n];
  memset(p, 0, sizeof p);
  for (int i = 2; i < n; i++)
    if (!p[i])
      for (int j = 2*i; j < n; j+=i)
        p[j] = true;
  return p;
}

我直接用C写了一下，我想看一下程序能有多快。程序运行得飞快，能在两秒钟内筛出一百万以内的所有素数。

我想知道这个时间复杂度到底是多少，只能通过通过一些设定点采样的方法来测出它。我从100,000开始到5,000,000，每间隔100,000运行一次这个算法采样，然后把这些采样点绘在了一个图上，得出的图像竟然是线性阶的。

这个算法怎么可能是线性阶呢？它有一个循环嵌套，难道不应该是类似于O(N^2)，或者至少也应该是O(N log N)啊。突然发现，刚才的程序竟然不是最优的，外循环其实最多只要sqrt(n)就可以了，我想原来导致线性阶的原因就在于此。这个简单的改变应该不仅仅能在采样图表上展现出原本的曲线形状，算法的性能也应该能提高不少。

不过图像显示的却不是这样。

首先，在图上的sqrt(n)没有展现出曲线来；其次，sqrt(n)的性能仅仅是原先的两倍，一个函数的外循环上限在指数级别上变为的一半，可是速度的提升却怎么可能只有2倍？

随着我对这个算法理解的加深，我认识到外层循环的迭代次数的增加，内层循环所耗用时间会因为两个因素而减少。首先，步长增大了；其次，在筛选过程中出现了更多的’false’值，因此判断语句会更少频率的被执行。这两个导致时间耗用降低的因素一定是导致算法保持线性阶的某种平衡因素。

其实，这个算法真正的时间复杂度是。在可以测试的范围内，的确是接近线形的。更精确的，，这个复杂度在Pritchard, Paul Linear prime-number sieves: a family tree. Sci. Comput. Programming 9 (1987), no. 1, 17–35.中被提及。

Update:

最新的研究表明这个算法的时间复杂度是O((nlogn)(loglogn))。

Dear teachers,

Today is teacher’s day and I’d like to express my thankfulness to you.

Teachers are often regarded as candles or gardeners, they help students to solve problems and never lose their passion and duty.

For all the things what you say and do are like spring that nurtures new green sprouts and encourage us whenever we have doubts.

You are like summer whose sunny temperament makes studying a pleasure. Your guidance makes us go far and do things differently. Inspire a love of knowledge and truth.

You light the path which leads our youth and teaches us to aim for success and accept failure with courage.

Sending great love to the greatest teacher all of the world.

Thank you!

Yours, XXX

评语：文章虽用词华丽，但显得过于疏远，不如一些亲切朴实的语言能感动读者。

内容：8/10 语言：8/10 结构：3/5

PS: 其实..这篇文章用词很基础，几乎都是考纲词汇，可惜秋天和冬天的是在写不下去了只能再辟一段不相干的做结尾了，败笔啊..虽然最后的分数不低，但是不提倡模仿，还是规规矩矩的摆事实讲“证据”吧..