面试题求助（学数学的同学看过来吧，谢谢）

EE转CS就这么苦逼么。。。。。面试只有4道高中数学题。楼主一个都不会，智商受到很大鄙视。。。
有知道的筒子给楼主点问题的想法吧。。。。
1：掷1个骰子，每次得到的点数相加，到100或超过100就停止，问102停的概率大还是103停的概率大，证明。
2：竞赛图，证明至少存在一点两步之内可以到达其他任何一点。
3：桌子上有数个不规则形状污点，总面积不超过1平方厘米，现有1平方米桌布一块，其上有1平方厘米网格。证明存在一种方法使得桌布可以放置在桌面上，且污点不与网格的十字交叉点重合。
4：100人，第一次分10组，每组至少一人；第二次分11组，每组至少一人。证明至少2个人所在组比原来的小。

跪谢啊。。。。。。。。。。

1）前提是每次掷色子得到的点数是均匀分布
最后一次点数为i，前面已经得到的点数和是S
102的概率位
P1= p（S=96|i=6）*p（i=6）+p（S=97|i=5）*p(i=5)+...+p（S=99|i=3）*p（i=3）

103的概率
P2=p（S=97|i=6）*p(i=6) + p(S=98|i=5)*p(i=5) + ...+p(S=99|i=4)*p(i=4)。
利用p(i=1) = p(i=2) =...=p(i=6)
P1-P2 =p（S=96|i=6）*p（i=6）>0.

2)3)没看懂题

4）
先证明如下结论，如果N个人分成M各组两次，则要么
1）两次中所有人所在的组都和原来一样大
或者2）最少有一人的组比原来的小
2）很好证明，不一样的话，肯定有一个人更大了，那么就有人更小了

有了这个结论，再用构造法证明如下：
我们从第一次分的的10个组构造成11个组，首先从某些组里面选出一些人组成11个组，证明这个时候肯定有两个人的组比原来小，然后对前面的10个组进行按照目标的11个组的前10个重新排组，得到最终的共11个组，再利用事先证明的结论。

刚查了下什么是竞赛图，这题可以用数学归纳法证明
1）三个点的情况很好证明
2）假设n（n>=3）个点的时候结论成立，在n+1个点的时候，
设n个点的时候点X到任何点之间都点都在两步之内，第n+1点Y和X的关系为
a) X->Y，则结论成立
b) Y->X
i）分两种情况，在加入Y之前，X的入度位0，结论很明显成立，
ii）在加入Y之前，X的入读部位0，将其它的n-1个点分为两类A和B，使得所有A中的点都有一条来自X的边，所有B中的点都有一条指向X的边。这里所有B中的点都有一条来自A中点的边。后面根据Y的情况就可以很好证明了。

回复 3# kevy1984

谢谢大神，我爱你！各种膜拜！

回复 2# kevy1984

感觉 1)  的过程可能有问题，S=96,97,98,99不是独立事件，岂能这么相加的。

或者简单点说p(S=N|i=1)和p(S=N|i=2)... p(S=N|i=6)不相等，比如p(S=98|i=1)=0，p(S=98|i=2）显然不是0，
你的上下两式子相减应该不对。

回复 5# ytsr

i和S是独立事件吧？

这不是故意搞人吗？

回复 6# kensan


    显然不独立，S的取值范围是由i 决定的

最后一个可以用反证法    证明   不可能0个组比原来的小  and   不可能只有1个组比原来的小

回复 5# ytsr


    貌似不需要p(S=N|i=2)... p(S=N|i=6)相等吧