锻炼脑力(精).doc

上一篇下一篇共 45 篇分享 10 道精彩的智力问题(转) 2010 年 08 月 13 日 00:08:47 1、给一个瞎子 52 张扑克牌,并告诉他里面恰好有 1 0张牌是正面朝上的。要求这个瞎子把牌分成两堆, 使得每堆牌里正面朝上的牌的张数一样多。瞎子应该怎么做? 答案:把扑克牌分成两堆,一堆 10 张,一堆 42 张。然后,把小的那一堆里的所有牌全部翻过来。大 D:很神奇。 2、如何用一枚硬币等概率地产生一个 1到3之间的随机整数?如果这枚硬币是不公正的呢? 答案:如果是公正的硬币,则投掷两次,“正反”为1, “反正”为2,“正正”为3,“反反”重来。如果是不公正的硬币,注意到出现“正反”和“反正”的概率一样,因此令“正反反正”、“反正正反”、“正反正反”分别为 1 、2 、3 ,其余情况重来。另一种更妙的办法是,投掷三次硬币, “正反反”为1 ,“反正反”为2 , “反反正”为3 ,其余情况重来。大D :看了答案才知道题目是什么意思。 3 、 30 枚面值不全相同的硬币摆成一排,甲、乙两个人轮流选择这排硬币的其中一端,并取走最外边的那枚硬币。如果你先取硬币,能保证得到的钱不会比对手少吗? 答案:先取者可以让自己总是取奇数位置上的硬币或者总是取偶数位置上的硬币。数一数是奇数位置上的面值总和多还是偶数位置上的面值总和多,然后总是取这些位置上的硬币就可以了。大D :这个简单。 4 、一个环形轨道上有 n 个加油站,所有加油站的油量总和正好够车跑一圈。证明,总能找到其中一个加油站,使得初始时油箱为空的汽车从这里出发,能够顺利环行一圈回到起点。答案:总存在一个加油站,仅用它的油就足够跑到下一个加油站(否则所有加油站的油量加起来将不够全程)。把下一个加油站的所有油都提前搬到这个加油站来,并把油已被搬走的加油站无视掉。在剩下的加油站中继续寻找油量足以到达下个加油站的地方,不断合并加油站,直到只剩一个加油站为止。显然从这里出发就能顺利跑完全程。另一种证明方法:先让汽车油箱里装好足够多的油, 随便从哪个加油站出发试跑一圈。车每到一个加油站时,记录此时油箱里剩下的油量,然后把那个加油站的油全部装上。试跑完一圈后,检查刚才路上到哪个加油站时剩的油量最少,那么空着油箱从那里出发显然一定能跑完全程。 5 、初始时,两个口袋里各有一个球。把后面的 n-2 个球依次放入口袋,放进哪个口袋其概率与各口袋已有的球数成正比。这样下来,球数较少的那个口袋平均期望有多少个球? 答案:先考虑一个看似无关的问题——怎样产生一个1 到n 的随机排列。首先,在纸上写下数字 1 ;然后, 把2 写在 1 的左边或者右边;然后,把3 写在最左边, 最右边,或者插进 1 和2 之间……总之,把数字 i 等概率地放进由前面 i-1 个数产生的(包括最左端和最右端在内的)共 i 个空位中的一个。这样生成的显然是一个完全随机的排列。我们换一个角度来看题目描述的过程:假想用一根绳子把两个球拴在一起,把这根绳子标号为 1 。接下来, 把其中一个小球分裂成两个小球,这两个小球用标号为2 的绳子相连。总之,把“放进第 i 个球”的操作想象成把其中一个球分裂成两个用标有 i-1 的绳子相连的小球。联想我们前面的讨论,这些绳子的标号事实上是一个随机的全排列,也就是说最开始绳子 1 的位置最后等可能地出现在每个地方。也就是说,它两边的小球个数(1,n- 1) 、(2,n-2) 、(3,n-3) 、……、(n-1,1) 这 n-1 种情况等可能地发生。因此,小袋子里的球数大约为 n/4 个。准确地说,当 n 为奇数时,小袋子里的球数为(n+1)/4 ;当 n 为偶数时,小袋子里的球数为 n^2/(4n-4) 。大D :概率题…… 6 、考虑一个 n*n 的棋盘,把有公共边的两个格子叫做相邻的格子。初始时,有些格子里有病毒。每一秒钟后,只要一个格子至少有两个相邻格子染上了病毒, 那么他自己也会被感染。为了让所有的格子都被感染, 初始时最少需要有几个带病毒的格子?给出一种方案并证明最优性。答案:至少要 n 个,比如一条对角线上的 n 个格子。 n 个格子也是必需的。当一个新的格子被感染后,全体被感染的格子所组成的图形的周长将减少 0 个、 2 个或 4 个单位(具体减少了多少要看它周围被感染的格子有多少个)。又因为当所有格子都被感染后,图形的周长为 4n ,因此初始时至少要有 n 个被感染的格子。 7 、在一个 m*n 的棋盘上,有 k 个格子里放有棋子。是否总能对所有棋子进行红蓝二染色,使得每行每列的红色棋子和蓝色棋子最多差一个? 答案:可以。建一个二分图 G(X,Y) ,其中 X 有m 个顶点代表了棋盘的 m 个行,Y 有n 个顶点代表了棋盘的 n 个列。第i 行第 j 列有棋子就在 X(i