【2017年整理】十道难题.docVIP

10道智力题你会做几道？(2010-1-26 15:12:04) 上一篇 首页 下一篇 1. 给一个瞎子52张扑克牌，并告诉他里面恰好有10张牌是正面朝上的。要求这个瞎 子把牌分成两堆，使得每堆牌里正面朝上的牌的张数一样多。瞎子应该怎么做？ 答案：把扑克牌分成两堆，一堆10张，一堆42张。然后，把小的那一堆里的所有牌 全部翻过来。 2. 如何用一枚硬币等概率地产生一个1到3之间的随机整数？如果这枚硬币是不公 正的呢？ 答案：如果是公正的硬币，则投掷两次，“正反”为1，“反正”为2，“正正”为3 ，“反反”重来。 如果是不公正的硬币，注意到出现“正反”和“反正”的概率一样，因此令“正反 反正”、“反正正反”、“正反正反”分别为1、2、3，其余情况重来。另一种更妙 的办法是，投掷三次硬币，“正反反”为1，“反正反”为2，“反反正”为 3，其余情况重来。 3. 30枚面值不全相同的硬币摆成一排，甲、乙两个人轮流选择这排硬币的其中一端 ，并取走最外边的那枚硬币。如果你先取硬币，能保证得到的钱不会比对手少吗？ 答案：先取者可以让自己总是取奇数位置上的硬币或者总是取偶数位置上的硬币。 数一数是奇数位置上的面值总和多还是偶数位置上的面值总和多，然后总是取这些 位置上的硬币就可以了。 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)。 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列有棋子就在