你想出来了吗
- 给一个瞎子52张扑克牌,并告诉他里面恰好有10张牌是正面朝上的。要求这个瞎子把牌分成两堆,使得每堆牌里正面朝上的牌的张数一样多。瞎子应该怎么做?
- 如何用一枚硬币等概率地产生一个1到3之间的随机整数?如果这枚硬币是不公正的呢?
如果是不公正的硬币,注意到出现“正反”和“反正”的概率一样,因此令“正反反正”、“反正正反”、“正反正反”分别为1、2、3,其余情况重来。另一种更妙的办法是,投掷三次硬币,“正反反”为1,“反正反”为2,“反反正”为3,其余情况重来。
- 30枚面值不全相同的硬币摆成一排,甲、乙两个人轮流选择这排硬币的其中一端,并取走最外边的那枚硬币。如果你先取硬币,能保证得到的钱不会比对手少吗?
- 一个环形轨道上有n个加油站,所有加油站的油量总和正好够车跑一圈。证明,总能找到其中一个加油站,使得初始时油箱为空的汽车从这里出发,能够顺利环行一圈回到起点。
另一种证明方法:先让汽车油箱里装好足够多的油,随便从哪个加油站出发试跑一圈。车每到一个加油站时,记录此时油箱里剩下的油量,然后把那个加油站的油全部装上。试跑完一圈后,检查刚才路上到哪个加油站时剩的油量最少,那么空着油箱从那里出发显然一定能跑完全程。
- 初始时,两个口袋里各有一个球。把后面的n-2个球依次放入口袋,放进哪个口袋其概率与各口袋已有的球数成正比。这样下来,球数较少的那个口袋平均期望有多少个球?
我们换一个角度来看题目描述的过程:假想用一根绳子把两个球拴在一起,把这根绳子标号为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)。
- 考虑一个n*n的棋盘,把有公共边的两个格子叫做相邻的格子。初始时,有些格子里有病毒。每一秒钟后,只要一个格子至少有两个相邻格子染上了病毒,那么他自己也会被感染。为了让所有的格子都被感染,初始时最少需要有几个带病毒的格子?给出一种方案并证明最优性。
- 在一个m*n的棋盘上,有k个格子里放有棋子。是否总能对所有棋子进行红蓝二染色,使得每行每列的红色棋子和蓝色棋子最多差一个?
- 任意给一个88的01矩阵,你每次只能选一个33或者4*4的子矩阵并把里面的元素全部取反。是否总有办法把矩阵里的所有数全部变为1?
- 五个洞排成一排,其中一个洞里藏有一只狐狸。每个夜晚,狐狸都会跳到一个相邻的洞里;每个白天,你都只允许检查其中一个洞。怎样才能保证狐狸最终会被抓住?
方案不是唯一的,下面这些方案都是可行的:
2, 3, 4, 4, 3, 2
4, 3, 2, 2, 3, 4
4, 3, 2, 4, 3, 2
- 一个经典老题是说,把一个333的立方体切成27个单位立方体,若每一刀切完后都允许重新摆放各个小块的位置,最少可以用几刀?答案仍然是6刀,因为 正中间那个单位立方体的6个面都是后来才切出来的,因此怎么也需要6刀。考虑这个问题:若把一个nnn的立方体切成一个个单位立方体,最少需要几刀?
推荐阅读
- 你到家了吗
- 画画吗()
- 拍照一年啦,如果你想了解我,那就请先看看这篇文章
- 你有婚内虐待行为吗()
- 红糖补血()
- 难道你仅会钻规则的漏洞吗()
- 2019-1-14
- 父母越不讲道理,孩子反而越优秀!说的是你吗()
- C语言字符函数中的isalnum()和iscntrl()你都知道吗
- C语言中的时间函数clock()和time()你都了解吗