答 案
1. 若干城市(n)之间有若干的联系，如飞机航线等，每个城市与其他城市有联系的城市个数分别为K1, K2, K3...Kn。请证明至少有两个城市与其他城市有联系的个数是相等的。即K1, K2,K3...中必有两个相等。
这个题目很容易的。
解答：因为都不相等，那么，连接数只能是0，1，2，3。。。n-2, n-1， 因为一个城市最多只能和n-1个城市联结，所以，就有谬误了，n-1是和所有的城市有联系，可是0是说这个城市和所有城市都无联系，所以，假设不成立。
2. 有12个硬币，其中有一个是假币，给你一个天平，只准称三次，必须找出假币，并且说明是轻还是重。
这个题目看起来容易，其实很复杂，因为要判断轻重啊。
解答：A: 最简单的一步：分三组，每组4个，任意取两组称。会有两种情况，平衡，或不平衡。平衡的结果最容易，先来讨
论。
1)首先，明确假币在其余的4个里面。2）从这4个里面任意取3个，并从其余8个好的里面也取3个称一下。又有
两种情况：平衡或不平衡。
a）平衡：称一下那个剩下的就行了。
b）不平衡：我们至少知道那组假币是轻还是重。
---从这三个有假币的组里任意选两个称一下，又有两种情况：平衡与不平衡，不过我们已经知道假币
的轻重情况了，自然的，不平衡直接就知道谁是假币；平衡的话，剩下的呢个自然是假币，并且我
们也知道他是轻还是重。
2)不平衡的情况很复杂，不过我们手里已经有一些有用的推论了：
假定已经确定该组里有假币时候：
推论1：在不知道该组是轻还是重时候，只称一次，能找出假币的话，那么这组的个数不超过1。（好像是废话啊！）
推论2：在知道该组是轻还是重的时候，只称一次，能找出假币的话，那么这组的个数不超过3。（想想看为什么，参考上面的过程啊！）
有着两个推论我们知道，只要我们知道了该组（3个）有假币，并且知道轻重，只要称一次就可以找出来假币了。
那么你是否猜出来我们要怎样解决问题呢？结论：问题的最小分组原则是3和1！！！
从不平衡的两组中，比如轻的一组里分为3和1表示为“轻（3）”和“轻（1）”，同样重的一组也是分成3和1
标示为“重（3）”和“重（1）”。在从另外4个剩下的，也就是好的一组里取3个表示为“准（3）”。交叉组合
为：
轻（3） + 重（1） ？=======？ 轻（1） + 准（3）
来称一下。又会有3种情况：
1）左面轻：这说明假币一定在第一次称的时候的轻的一组，因为“重（1）”也出现在现在轻的一边，
他一定是“无辜的”。（这里面有好几步推论得出来的，你想一下吧。）并且我们已经知道，假币是
轻的。（为什么？因为是第一次称的时候的轻的一组有假币嘛！）那么假币在哪里？当然在
“轻（3）” 里面，根据推论，再称一次就可以了。
2）右面轻：这里有两种可能：
-----“重（1）”是假币，它是重的，或者“轻（1）”是假币，它是轻的。这两种情况，任意取
这两个“坏蛋”中的一个和一个真币称一下就知道了。
3）平衡：假币在“重（3）”里面，而且是重的。根据推论也只要称一次就可以了。
怎么样？看懂了吗？
3. 猜一句毛主席诗词 ：
Ten thousand years are too short,
All difference to me is only one day and night.
4. 猜一物：
In the eyes of people, I am an idiot
even though I memorize more, calculate faster, think smarter than them.
Still I seem to be an idiot to them. I am only a ...
5。 离散数学的题目：
假如有一百个判断，第N个判断是“只有N个判断是假的。”那么你的结论呢？
解答：这个问题的核心在于自我否定。 首先，每个判断都与其他不相容的，于是我们知道，假如有正确的只能是其中一个判断，因为，如果同时有两个以上的正确判断，因为所有的判断都是否定其他判断的，所以，必然有谬误。其次，很简单，看一下谁在说真话：“只有一个是真的。”当然是第99个了。其实，假如把问题的否定形式改为肯定，就容易多了。
6. 爱因斯坦提出的问题，据说世界上95%的人无法解决：
Zebra Puzzle:
Five men with different nationalities and with different jobs live in consecutive houses on a street. These houses are painted different colors. The men have different pets and have different favorite drinks. Determine who owns a zebra and whose favorite drinks is mineral water(which is one of the favorite drinks) given these clues: The Englishmean lives in the red house. The Spanish owns a dog. The Japanese man is a painter. The Italian drinks tea. The Norwegian lives in the first house on the left. The green house is on the right of white one. The photographer breeds snails. The diplomat lives in the yellow house. Milk is drunk in the middle house. The owner of the green house drinks coffee. The Norwegian's house is next to the blue one. The violinist drinks orange juice. The fox is in a house next to that of the diplomat.
要做出来其实并不是真的很困难。可是，能让程序来解答吗？想知道黄教授怎样用计算机解决这个问题吗？看这里：解答。
7. 黄勇提交的puzzle,我不清楚我的解答是否对，你有兴趣判断一下吧。
5个海盗抢到了100个宝石，然后商量怎样分配，于是抽签派队排出1到5的顺序来提出方案，但是一个条件很重要，就是：提出的方案由大家投票表决来决定，只有“超过”半数的人支持才行，否则，方案判为失败，而提案者要被扔进海里为鲨鱼。于是，由下一个人体方案。即假如第一个人的方案5个人投票没有半数支持，他就被扔进海里喂鲨鱼，然后，由第二个海盗提方案，4个人投票，如果仍未得到半数支持，他也被喂鲨鱼，以此类推。。。
问题：第一个海盗能获得的最佳结果是多少个宝石？
假定：所有的海盗都是智商超群的，知道进退的理性动物，都会理性地分析自己的机会。
要求：1。 不要按照脑筋急转弯的方法去思考，这是生死攸关的问题，没有侥幸。
2。 每个海盗都是杀人成性，贪得无厌的，就像大多数MBA,和CEO一样，只追求更多。
我的答案是：第一个海盗说：“这100个宝石我出力最多，我应该得99个，老四也出了一点力得一个。”结果方案通过了。
1。 首先，你要明白一个潜在的条件，每个人都是活命第一，宝石第二。命都没有了宝石有什么用
啊？
2。 其次，每个人当然投票同意他自己的提案了，傻瓜才不这样呢！对吧。（这不是废话吗？你以为谁是傻瓜啊？）
3。 看看每个人的处境：
A. 第5个海盗处境最好，因为他最后才提方案，他一定不会死！而且，他可以反对任何人的方案，因为大家都死了，他才能独吞，他总是反对。
B. 第4个海盗很可怜，因为他很可能会死。假如前面三个都死了，轮到他和第5个海盗分，他死定了，1：1永远没有超过半数，他唯一的机会是在第三个海盗之前解决问题，活命要紧，宝石嘛，再说吧。
C.第3个海盗最牛了，他有一个铁杆的支持者---第4个海盗，因为第4个海盗要活命一定要支持他，否则，第3个海盗死了，第4个海盗也活不了。因此，第3个海盗他赢定了，2：1他想分多少就多少，第4个海盗连屁都不敢放。
D.第2个海盗也很可怜，因为他也很可能会死。假如第一个海盗死了，轮到第2个海盗提方案，他一点机会都没有，因为，第3，第5个海盗都巴不得前面的人早死掉，就算第四个想支持他，2：2，他还是死定了，所以，第2个海盗唯一的机会在第一次分配就通过。活命要紧，宝石嘛，再说吧。
E.第一个海盗他也有一个铁杆的支持者---第二个海盗，因为他们的命是连在一起的，第一个海盗不论说什么，第二个海盗都会同意的，可是，2：3怎么能赢呢？他的第三个支持者是谁？第3个，第5个海盗是不可能的，唯一的机会在争取第4个海盗的加盟，假如第四个海盗不支持他，第四个海盗正常情况下，只能保命，分宝石是没有机会的，因为，第3个海盗是心狠手辣的，不会分他一个的，而他要活命，只能答应。那么，当第一个海盗提议分第四个海盗一个宝石时候，他都会欣喜若狂地立刻接受，为什么不呢？有聊胜于无啊！所以，第一个海盗独得99个宝石，第四个得一个，第二个海盗活了命比什么都高兴，第三个，第五个海盗干瞪眼没有办法。
哈哈。。。
可惜的是这一切都不是真的，以上答案是不对的，请看这里。
以下为黄勇提供的“据说”是“微软”招聘的小问题，我挑了三个有意思的问题。
8.你让工人为你工作七天，回报是一根金条。这个金一平分成相连的7段，你必须在每天结束的时候给他们一段金条如果只许你两次把金条弄断，你如何给你的工人付费？
解答：7是一个很容易想出的数字，假如用数学的思考方法来解决呢？比如n天？
用递归的方法思考：假如，我们找到了这样一组数（k个数），他们的排列组合能够组合成所有可能的连续的组合，所谓“连续”的组合就是说，能组成1，2，3，4，5。。。直到他们的最大组合数---他们的和（p1+p2+p3+...pk).那么我们要在增加他们组合的能力的话，就只能在增加一个它们和再加1的数。所以，这样的一组数字一定有这样的特性：
P(k) = P1+P2+P3 +...P(k-1)+1 or P1+P2+P3+...+P(k-1) = P(k) -1;
我们现在再来找找起始的数，毫无疑问，1一定是第一个数，第二个数一定是P(2) = P(1) + 1=2;
P(3) = P(1) + P(2) +1 = P(2)-1+ P(2) +1 =2*P(2）; //看明白了吗？
P(4) = P(1)+P(2)+P(3)+1 = P(3)-1 +P(3) +1 =2*P(3); //因为P(3)之前的所有数值和是P(3) -1
...
P(k) = P(1) +P(2) +P(3)＋...P(k-1)+1 = P(k-1) -1 +P(k-1) +1 =2*P(k-1);
因此，我们用到了二进制中很重要的特性，完美地解决了问题．
对于本题，切断两次就是共有3段，按照以上结论，为1， 2， 4，你可以有多种方式来切：先切成1和6，在切成2和4，或者县切成2和5，在切成1和4，或者县切成3和4，在切成1和2。
不要告诉我说你不知道怎样付工钱给工人！
第一天：1根；
第二天：2根；（把第一天的一根要回来。）
第三天：再加一根。
第四天：把1+2要回来，给4；
第五天：给1；（前面的4要不回来了。5555。。。）
第六天：把1拿回来，给2；
第七天：再把1给他。
9. 烧一根不均匀的绳需用一个小时，如何用它来判断半个小时？
解答：从两头同时烧啊！要把脑筋反过来用，想象时间的中点是绳子中间的某一点，从这一点开始向两头烧，肯定会烧相同时间，而且这一点是唯一的，因此，从两头烧交汇的点一定是时间轴的中点．
10. 想象你在镜子前，请问，为什么镜子中的影像可以颠倒左右，却不能颠倒上下？
11. 也是黄勇提供的puzzle:
一个大院子里住了50户人家，每家都养了一条狗，有一天他们接到通知说院子里有狗生病了，并要求所有主人在发现自己家狗生病的当天就要把狗枪杀掉。然而所有主人和他们的 狗都不能够离开自己的房子，主人与主人之间也不能通过任何方式进行沟通，他们能做的只是通过窗户观察别人家的狗是否生病从而推断自己的狗病否。（就是说，每个主人只能看出 其他49家的狗是不是生病，单单没法看出而只能是根据逻辑推断出自己的狗是不是生病）
第一天没有枪声，第二天还是没有枪声，第三天传出一阵枪声，问有多少条狗被枪杀。
(出自微软的面试题，不是脑筋急转弯，而是推理题) .请写出详细推理过程.
50条都被杀了,假如只有一条狗有病,那么狗的主人很快就能推理出自己的狗有病.因为,当他看到所有其他的狗都健康,就知道一定是自家的狗有病.可是,没有人枪杀狗,所以,一定不止一只狗生病;同理,如果两只狗生病,两家主人可以都看到一只狗生病,利用前面的推理,他们应该可以由"没有人枪杀自己的狗推理出自己的狗一定也生病了."可是,同样没有人枪杀自己的狗,因此,可以一直推断出所有的人都是看到了别人家的狗都生病了,因此,自家的狗一定也生病了.
我认为这个题目类似于“离散数学”书上的一个例题：
A father tells his two children, a boy and a girl, to play in their backyard without getting dirty. However, while playing, both children get mud on theri foreheads. When the children stop playing, the father says "At least one of you has a muddy forehead", and then asks the children to answer "Yes" or "No" to the question. What will the children answer each time this question is asked, assuming that a child can see whether his or her sibling has a muddy forehead, but cannot see his or her own forehead? Assume that both children are honese and theat the children answer each question simultaneously.
Solution: Let s be the statement that the son has a muddy forehead and let d be the statement that the daughter has amuddy forehead. When the father says that at least one of ther two children has a muddy forehead he is stating that the disjunction "s or d" is true. Both children will answer "NO" the first time the question is asked because each sees mud on the other child's forehead. That is, the son knows that d is true, but does not know whether s is true, and the daughter knows that s is true, but does not know whether d is true.
After the son has answered "NO" to the first question, the daughter can determine that d must be true. This follows because when the first question is asked, the son knows that "s or d" is true, but cannot determine whether s is true. Using this information, the daughter can conclude that d must be true, for if d were false, the son could have reasoned that because "s or d" is true, then s must be true, and he would have answered "Yes" to the first question. The son can reason in a similar way to determine that s must be true. It follows that both children answer "Yes" the second time the question is asked.
以上为书上的解释，你看懂了吗？在这里，没有枪声就说明每个人对自己家的狗是否生病的回答是“不知道”。
黄勇提供的网上的“所谓”正确答案：
如果只有一条狗得病，那么第一天就会有一个主人看到其他人的狗都是健康的，而把自己的狗给杀了。 如果有两条狗得病，主人们第一天就都会看到有一条狗或两条狗得病了。那些只看到有一条狗得病的主人，第二天一看那条狗还没被杀，那么一定是那条狗的主人第一天也看到了病狗，那自然就是自己的狗也得病了。所以第二天，这两个只看到外面有一条病狗的主人就会把他们的狗杀了。 如果有三条狗得病，那么主人们就会看到外面有两条或三条病狗。那些只看到外面有两条病狗的主人想：那算上自己的狗，那么可能得病的狗是两条或三条。如果一共只有两条病狗，那么第二天他们就会被主人发现，并被杀了。而第二天没有人杀狗，那么就应该每人都至少看到了两条病狗。这样那些只看到两条病狗的主人就知道自己的狗也是得病的，否则自己看到的病狗的主人就看不到两条病狗了。于是第三天有三个人确定他们的狗得病了，杀了自己的狗。 如果有四条狗得病，那么主人们就会看到外面有三
我觉得这个只是问题理解的不同，“关键是观察别人家的狗是否生病从而推断自己的狗病否”这句话怎样理解呢？观察多长时间才能得出结论？因为，“必须要得到别人对问题的答案作为自己推力的依据，”可是对于别人给出答案的认定可能完全是因人而异的。我并不认为要得出别人回答问题是否需要等一天时间，这就是分歧之处。
已知：生病的狗的数目d>=1,如果病狗的主人知道自家的狗生病了，就应当在当天杀掉它的狗。
第一天：没有人开枪。
定义：D(n) = {生病的狗的数目为n，1<=n<=50}
结论：每个人在这一天结束的那一刻就已经最后确认生病的狗不止一只。理由：如果只有一只狗生病的话，那只狗的主人会看到所有其他的狗都是正常的，根据已知条件“生病的狗的数目大于一”，他就应该在这一天里开枪杀掉狗，可是没有枪声响起，说明D(1)=false；
在这一天的夜里，每个人都躲在被窝里面学习数学归纳法做出了如下推理：
因为，D(1)=false, 那么，D(2), D(3),D(4)...,D(50)里面有且只有一个是对的。不妨先假设D(2)=true,那么那两个倒霉的家伙都看到对方的狗生病，但是连傻瓜都知道在第一天平静的过去后D(1)=false，那么这两个IQ再怎么低的家伙也会在第二天举起枪杀掉自家的狗，所以，“如果D(2)=true,我们一定会在第二天结束以前听到枪声。”
想完了这些，有些人开始睡觉了，但有些人还在想第二种情况：假如第二天平静的度过了呢？那么，D(2)=false就成了有一个大家公认的事实了。那么我今天晚上要先想好呀。请注意这里就是数学归纳法：我这里为了方便人类的思维要将命题换一下，不然很多人，就是我了，脑筋转不过来。
重定义：P(n)={生病的狗的数目大于等于n}
Basis: 第一天告诉我们P(1)=false, P(2)=true。
Assume: for some 50>k>=2, P(k)=true, (因为k不可能等于50，原因见下。）
Then: P(k+1) is also true。
我们现在就来证明之，假定生病的狗的数目是k并且k<=49，那么，一定会有一个人看到k-1只生病的狗，而我们知道所有人已经公认了P(k-1)=false。那么，这个人一定会判断出P(k)=true。所以，这就像数学归纳法一样，假如我们承认了P(k)=true的假设，就一定可以推理出P(k+1)=true。唯一无法推理出的是P(50)=true，也就是50只狗都生病了，因为，这个情况下每个人看到的生病的狗的数目都是一样的49,这也就是上k=\=50的原因。所以，在第二天平静的度过以后，我们可以知道P(2), P(3),...P(49)都是false。第二天的晚上，人人都已经知道P(50)是真的了。
这三天的过程象极了数学归纳法的三个必不可少的步骤，真是神妙。
> 那么我就不明白了，那么对于无论多少只狗(设数量N)，到了第三天晚上，所有狗都
会被杀掉。
> 因为，对于总共有N只狗的情况下，只有P(N)=true；
> 那么我们把这个问题延伸一下：
> 甲村庄有10只狗，乙村庄有50只狗，丙村庄有100只狗……一天，县里来人了，说每
个村里都有狗病了，必须被杀掉。…… 每个人都开始使用数学归纳法……
> 第三天晚上，甲村庄传来10声枪响，乙村庄传来50声枪响，丙村庄传来100声枪
响……
> <建议：能不能不要用狗来假设，很血腥呀……>啊，你很聪明，你的延伸理论上是对的。（为什么我没有想过这一点？）
之所以用狗做例子可能是微软出题目的人和我一样不喜欢宠物。
多年以后再一个风平浪静的日子里，一封来自大西洋对岸的电子邮件让我认识到了正确的答案。
这是在Becky的启发下。
你的说法是对的。是三只。的确三四年前的看法还是有点点幼稚了。我试说如下。假如只有一个病狗，当天就会有人射杀因为肯定有病狗，而他的主人肯定看到49只健康的狗，第一天没有枪声可以肯定病狗的数目大于1。假如有两只病狗，它们的主人一定可以看到一支病狗，主人所要决定的仅仅是自家的狗是否生病。如果自己的狗是健康的，那么总共就只有一支病狗，根据上面的结论已经否定了一只，所以第二天的时候，两只病狗的主人应该都可以推断出自己的狗是病狗，并开枪，而第二天没有枪声，说明狗的数目超过2。也就是说两只狗，需要一天的沉寂来判断。同理两天的寂静否定了两只病狗，第三天枪响了，说明是三只病狗，因为这时候能推力出结果的人一定是看到了两只病狗，在否定两只以后，自然就知道自己的狗也是生病的。
13. 也是黄勇提供的puzzle:
说有一个人出差回来（乘飞机），飞机比计划提前一个小时到机场，来接他回家的车 子还没到，于是他就开始往回家路上走去，在途中碰到了来接他的汽车，他上车，车 子把他送回家，到家时他发现比原计划到家提早了２０分钟，而汽车是按计划准时出 发到机场去接他的。问这个人走了多少时间？
(假定：车子匀速行驶，车子准时接机，即车子本来要按航班到达时刻到机场。黄勇认为要加一个条件是车子是从家里开出的，我认为不需要，只要人车相遇的地点是去机场的必经之路就行，而人往家走肯定是知道这是必经之路，否则怎么相遇呢？）
据说是小学生的数学应用题，很惭愧，我本来马上解答了，却又开始怀疑，结果，又给出了错误的答案。
比预计早20分钟到家，就是说车子：1。比正常接机时间早了若干分钟。因为，人车相遇意味着，车子还没到机场，也就是比计划时间早出发。2。比正常车程来得少。因为，半路相遇车子自然少走了路。
这两个因素，加在一起结果是提前了20分钟，因为车子是匀速的，所以，而且车子正常情况一开到机场立刻掉头，所以，提前的时间和少走的里程是等效的，即因素1和2是等值的。因此，提前的时间是20/2=10分钟。也就是说，这个人走了60-10=50分钟。
14。也是黄勇提供的puzzle:
一个小猴子边上有100根香蕉，它要走过50米才能到家，每次它最多搬50根香蕉，
（多了就被压死了），它每走1米就要吃掉一根，请问它最多能把多少根香蕉搬
到家里。
提示：他可以把香蕉放下往返的走，但是必须保证它每走一米都能有香蕉吃。
也可以走到n米时，放下一些香蕉，拿着n根香蕉走回去重新搬50根。
首先，明白小猴实际上如果只搬50根香蕉只能走回家，路上会劝吃光。所以，第一次他要把香蕉放在路中间以便第二次搬回
家。那么，小猴只有一次回家的机会，她在路上放多少，就是它能搬回去的数目，因为，她没多走一步，就要多吃掉一根，
问题就转化为，第一次带50根香蕉放多少，放在什么地方。
假定小猴走n米，则来回吃掉的香蕉数目为2n,能够在n米处放下50-2n根香蕉。显然，n《=25，是否走的越远越好呢？不，目的
是多搬橡胶回家，多走路，吃掉的就越多；但是放在太近也不行，因为，小猴下次出发只能带50根香蕉，放得太近，小猴搬
不了。我们可以看出，实际上放香蕉的地方，小猴来回加上最后一次走，一共走过3次，就是说他一定会吃掉3n根香蕉，如果
放的香蕉数是50的1/3的话，小猴路上吃掉的香蕉正好可以得到最大的补充，这个数就是它能搬回家的数。
所以，第一次，小猴带50根香蕉走到17米处，放下16根，带着17根走回，再带着50根出发，走到17米处，正好吃掉17根可以拿
起先前放的16根接着走，所以就搬了16根回家。你做对了吗？
你参加一项抽奖大赛，有三个门，其中只有一个门后是大奖。你选择了一个之后，主持人会这样做：打开没有大奖的一扇门，（当然主持人知道哪一个们是由奖品的了。）给你看，然后问你是否要改变你的选择。你怎么做？
（提示：如果你学过统计学，或概率论就会明白这是后验概率。）
解答：你要改变你的选择。
答案是违反直觉的。分析如下：
对于你最初的选择无非有两种结果，正确1/3，错误2/3。
1。你原来就选对了，这个时候，你换了，你选错了，你成功的概率是1/3 x 0 =0;
2。你原来的选择是错的，这个时候，你换了，你选对了，你成功的概率是2/3 x 1 =2/3
两项相加，这个时候你换了，你总的成功概率是2/3。
很难理解吗？我们把这个问题一般化。假如有n个门，只有一个是对的。假如你作出选择后，主持人仍然给你看一个错误的门问你要不要改变，你怎么办？
实际上你有大约三种大的策略：
A. 不换。这说明你坚持原来的选择，你原来的选择概率是1/n。你还是1/n的成功率。
B. 换。但是，为什么要把我第一次的选择排除在外呢？我想把剩下的(n-1)个都重新选择一遍。这个时候，你成功的概
率是 1/(n-1)。
C. 换。主持人的提示相当于一种后验概率的提示，我要排除我第一次的选择，在剩下的n-2力作选择。
分两种情况：
a)我第一次选错了，这个可能性是(n-1)/n ，我现在换的话，我成功的可能性是1/(n-2)，我总的成功几率是两项相乘。
b)我第一次选对了，这个可能性是1/n,现在我换的话，我成功的可能性是0。
所以，a+b是我的总的成功率是(n-1)/(n x (n-2))
我们现在来看看A和B的区别：同分母后，
P(B) = n(n-2)/nx(n-1)x(n-2)
P(C) = (n-1)x(n-1)/nx(n-1)x(n-2)
P(C) - P(B) 的分子是 1。所以就是说，C策略比B策略多了1/n(n-1)(n-2)的机会。当n=3时候，它是1/6这就很大了。
你还是不信吗？把n=2看看是什么结果？为什么？
16。还是离散数学里的概率问题，结果总是出乎我的意料和直觉估计。
饭店的衣帽间里管寄存帽子的雇员忘记把客户的号码和帽子放在一起，结果，客户来取帽子时候，他就随机抓一顶，问能够正确给客户帽子的个数。假如客户的人数是n,当然，你如果知道算法，这个条件是多余的。（假设客户都很粗心，谁也不管帽子的正确与否。）
解答：1个。
因为，每个来取帽子的客户给对帽子的可能性都是1/n（这一点下面证明。），我们可以把问题转化为，n个随机变量（random variable)X(1),X(2)...X(n)分别表示第k个客户拿对了帽子，X(k) = 1,拿错了帽子，X(k) = 0，则总共拿对帽子的客户个数是这n个随机变量与其拿对帽子的概率乘积之和，也就是每个随机变量数学期望的和，就是总的拿对帽子的客户个数的数学期望。那么，n个随机变量的取值为1的概率是1/n，总和就是n个（1/n x 1)之和，就是1了。
下面我们来证明P{X(k)=1} = 1/n
对第k个客户来说，如果他的帽子被前面k-1个客户中的某一个拿走的话，他永远无法拿到正确的帽子，所以，我们只考虑他的帽子在剩下的n-(k-1)里的情况，这个概率是 n-k+1/n。因为，帽子是随机分配在他来之前的部分和剩下的部分。
这里面拿对的几率是1/n-k+1,运用乘法定律，他能拿到他的帽子的概率是 (n-k+1/n)x(1/n-k+1) = 1/n
这个答案很出乎我的直觉，这居然和客户的人数无关。对于所有的顾客来说假如人人都不去纠正这个家伙的错误的话，总的就是只有一个人能够拿到他自己的帽子。
这个问题的等价问题是你在一大堆的磁带里找你喜爱的拿一盘磁带，或者从书架上照某一本书，每次你发现不对的话，你又把它放回去，再次随即选取，要找多少次你才能找到呢？第n次，这是个令人吃惊的结果。设想一下吧，计算机在一组未排序的数组里（假定数组大小为10000)每次随机查找某一个元素，理论上要找10000次。可是，假如数组经过了排序，用最简单的二分法，则只要最多14次。
集合A有m个元素，集合B有n个元素，那么有多少种不同的onto function f: A-->B?
提示：1. 总共的function是：n^m(就是n的m次方)。
2. 总共的one-to-one function是：当m>n时为0，当m<=n时为: n(n-1)(n-2)...(n-m+1)。
提醒：1. function的定义是：对于A中每一个元素，在B中有且仅有一个元素与之对应。
2. one-to-one的定义是：这个function里B的每一个元素b在A里仅有一个元素与之对应。即：
[(x,b) and (y,b) in f] ==> x = y
3. onto的定义是：B的每一个元素都在function里。
答案：不是我想出来的，是看到离散里的解答。
首先，m<n，答案是0，因为不可能有on-to德function。
如果m>=n，答案是
n^m - C(n, 1) (n-1)^m + C(n, 2) (n-2)^m -....+ [(-1)^(n-1)] C(n,n-1) 1^ m
{注意：C(n, k) = n!/(n-k)!/k! 是组合数。}
这是从inclusion-exclusion原理来的：我们的range有n个元素，让我们假定
N(Pk) = {range中第k个元素不在function。n=>k>0}
那么所有的onto function 的数目就是总的function的数目减去N(P1UP2UP3...Pn),明白吗？我们要求得是所有的元素都
在，那么自然就是用总的数目减去所有都不在的情况。{注意，这里面实际上包括了一个元素不在，两个元素不在，。。。直到
n个元素都不在。}
但是，当我们计算k个元素不在的时候会重复计算，这时候就要用到inclusion-exclusion原理，定理的证明就略过了。
这个问题的实质是，当我们无法对一个集合进行partition得到所有disjoint subset时候怎样去计算集合的size,比如类似的
问题，我们知道一群工程师里面会一种技能的人有k1个，会两种技能的有k2个，。。。会n种技能的人有kn个，而每个人最多就是
n种技能，最少一种技能，那么工程师的人数是多少？答案就是k1-k2+k3-...+(-1)^n x kn
（提示：所谓公平就是人人都满意，对两个强盗来说就是分配方案提出者不能同时是优先分配者。例如，甲强盗提方案，乙强
盗优先选择。）
答案：应该不止一种分法。
最初的想法：
首先，我们运用递归的思想来解决。将三个强盗分为两组，方案提出方1人和方案优先实施方2人，即一个强盗提出赃物分成三份
的分配方案，然后交由另外两个强盗自行挑选其中两份，然后两个强盗先将两份赃物合并再按照“谁提方案谁后拿”的原则分配
他们挑选的那一份。
将三个强盗分为两组，方案提出方2人和方案优先实施方1人，即两个强盗提出赃物分成三份的分配方案，然后交由另外一个强盗
自行挑选其中一份，然后两个强盗先将所剩的两份赃物合并再按照“谁提方案谁后拿”的原则分配他们各自的那一份。
这两个方案实际上是一样的，只不过分配的顺序有些不同。第一种情况强盗分组有C(3,1)=3种组合方法；第二种有C(3,2)=3种
分组方法，所以，共有6种可能的情况。
推而广之，假如有n个强盗，究竟有多少种公平的分配情况可能发生？
很复杂啊！想不清楚。
和长征讨论后认为以上提法不太对：
关键的前提就是赃物往往不是可以准确量化的，或者说每个强盗的量化标准不统一才出现这种分赃不均的问题。所以，让两个强
盗商量分配方案是不一定可行的，只有一个人自己才能做决定如何进行分配。所以，长征才提示说只有两个强盗才能满意地分
赃。
基于此，我的答案是这样的：假设三个强盗分别是A,B,C，随机抽取一个强盗做方案提出者，不妨假设为A。让A提出一个三等分
的方案来让B,C选择，这里会有两种情况：
1。B,C的选择重合。即B,C心目中认定的最大的两份一致，（即便他们对两份中哪一个最大有不同看法也无妨，因为，我们
已经成功地把A的那一份解决了，B,C可以将他们认定的两份合并，然后再采取“谁提方案谁后拿”的原则重新分配他们各自
的那一份。）这样问题就解决了，皆大欢喜。
2。B,C的选择部分重合。即B,C心目中认定的最大的两份只有一个一致，（一定且只有一份是重合的，因为，从三份里面选两
个。）那么，对于B,C意见一致的那一份，可以拿出来让B,C按照“谁提方案谁后拿”的原则再等分之。对于意见不一致的
两份，让他们分别与A重新进行细分，同样遵循“谁提方案谁后拿”的原则再等分之。
这样每个强盗都是满意的，因为，我们始终遵循“谁提方案谁后拿”的原则，每个人的利益与意见都得到了尊重。A是方案的制定
者，他的意见完全在方案中体现，分多分少她早就能预见到；B,C虽然没有权利制定方案，但是，他们是方案的选择者，而且，B
和C的不同意见也完美的解决了。连强盗都懂得理性地，民主地解决问题，我深深地为台湾日本所谓的议员们在议会打架的行为感
到可耻，因为，他们确实从智力上，道德上远远地落后于强盗。
对于利益分配的不均始终是困扰人类的一个问题，从原始社会以来，每次的革命与暴动都只是一次利益的再分配的过程，几乎每
次都是血和火的洗礼，人们为了自己的意见得到尊重不惜以消灭不同意见者的肉体，精神为手段。难道我们不能找出类似的公平
方法来解决吗？
19。100个球，其中黑色70个，红色30个，问当我们随机抽取并不放回，第50次拿到黑球的可能性是多大？
答案：请用数学归纳法证明。
我们假设第50次拿到黑球的概率还是0.7,现在证明如下：
证明：设B(i)={为第i次抽取黑球的概率} R(i)={第i次抽取红球的概率}
显然地， B(i)+R(i) = 1 并且 B(1) =0.7; R(1）= 0.3；
Basis: When i=2, B(2) = B(1)*(69/99) + R(1)*(70/99) = B(1)*(69/99) + (1-B(1))*(70/99)
= (70-B(1))/99 = (100*70-70)/99/100 = 70/100
Assume: for some k>=2, B(k)=0.7, obviously 如果这时候有n个球，一定有n*0.7黑球，n*0.3个红球。
Then: B(k+1) = B(k)*(n*0.7 - 1)/(n-1) + R(k)*(n*0.7)/(n-1)
= B(k)*(n*0.7 - 1)/(n-1) + (1-B(k))*(n*0.7)/(n-1)
= (n*0.7-B(k))/(n-1) = 0.7*(n-1)/(n-1) = 0.7
Q.E.D.
李文杰的方法很巧妙：把100个球随机排成一列代表每次抽取的顺序，则第50个球放黑球的方法有70种，其余的球的排列方法是
99的阶乘：99!,总的100个球的排列是100！，所以，第50次抽取黑球的概率是：
70*99！/100！ = 0.7
20。这是老张的问题：给你两根部一样的绳子，都恰好能燃烧1个小时，问怎样精确找出一段15分钟的时间长度？（当然指给你
火柴或者打火机。）
答案：这个问题比以前我的一根绳子的问题稍稍的复杂一点点。
既然我们知道怎样找出一半的时间的方法，自然就可以再找出一半。
1。第一步，一根绳子两头一起点着，另一根绳子一头点着。
2。第二步，当两头一起燃烧的绳子烧尽的时候，我们的第二根绳子就燃烧到了半小时的长度了，也就是说剩下的绳子的燃烧时
间是半个小时，这时候，点燃绳子的另一端，从这时候到绳子燃尽正好是15分钟。
21。第一道题：在房里有三盏灯，房外有三个开关，在房外看不见房内的情况，你只能进门一次，你用什么方法来区分那个开关控制那一盏灯？
答案：这个问题我以前是看到答案的，估计叫我自己去想是想不出来的。
如果你是学计算机的话，你应该很快明白三个开关好像三个布尔值，除掉全开（111），全关（000）之外只有两种情况：1个开（100），两个开（110），你无法用这两个情况判断三盏灯泡的情况。注意这里100，001，010是无法区分的。一句话，这个题目用正规的办法是无解的。
你只能另找办法，也就是额外的信息，比如，你在屋子外打开两盏灯，过了一会儿，关掉一盏灯，然后，进屋子看看两盏没有亮的灯泡那一盏灯泡是热的。
22。第三道题：一个经理有三个女儿，三个女儿的年龄加起来等于13，三个女儿的年龄乘起来等于经理自己的年龄，有一个下属已知道经理的年龄，但仍不能确定经理三个女儿的年龄，这时经理说只有一个女儿的头发是黑的，然后这个下属就知道了经理三个女儿的年龄。请问三个女儿的年龄分别是多少？为什么？
答案：我不是很确认我的答案，不过应该是对的吧？
这里关键就是说，经理的年龄可以有两种以上的组合方式，也就是说，经理的年龄有很多因子，这样才有可能组合多个。那么就尝试6，9这类的多因子的数字，很快你可以有这样的结果：2x2x9=36; 1x6x6=36;这里2+2+9=1+6+6=13，所以，雇员不清楚是哪一个组合。我对于黑头发的翻译只能是说女儿一岁二岁的时候还没有头发，所以，2,2,9是唯一的选择。
23。若干人排队领苹果，已知第一个人领的苹果数为一，从第二个人开始每个人领的苹果数是前面一个人领的苹果的2倍再加3，请问第n个人领了多少。
答案：这个是一个非常简单的迪归公式求同项的小题目，其实他的难度不太适合放在这个范畴里面，但考虑到题目提供着Albert愿意上传Diablo2给我下载，因此特别允许这个题目post在这里。
24。Hats On A Death Row
You are one of 20 prisoners on death row with the execution date set for
tomorrow. Your king is a ruthless man who likes to toy with his people's
miseries. He comes to your cell today and tells you:
“I’m gonna give you prisoners a chance to go free tomorrow. You will all stand
in a row (queue) before the executioner and we will put a hat on your head,
either a red or a black one. Of course you will not be able to see the color of
your own hat; you will only be able to see the prisoners in front of you with
their hats on; you will not be allowed to look back or communicate together in
any way (talking, touching.....).
The prisoner in the back will be able to see the 19 prisoners in front of him.
The one in front of him will be able to see 18…
Starting with the last person in the row, the one who can see everybody in front
of him, he will be asked a simple question: WHAT IS THE COLOR OF YOUR HAT?
He will be only allowed to answer “BLACK” or “RED”. If he says anything else you
will ALL be executed immediately.
If he guesses the right color of the hat on his head he is set free, otherwise
he is put to death. And we move on to the one in front of him and ask him the
same question and so on…
Well, good luck tomorrow, HA HA HA HA HA HA!”
Now since you all can communicate freely during the night, can you find a way to
guarantee the freedom of some prisoners tomorrow? How many?
首先，我想最直觉的回答至少是一半，就是每个偶数囚犯牺牲自己说出自己前面的人的颜色，自己只好碰运气，这是我一开始的想法。
