主题:给山区的小朋友出几条智力题
- 发表于2010-01-27
答案:如果是公正的硬币,则投掷两次,“正反”为1,“反正”为2,“正正”为3,“反反”重来。
如果是不公正的硬币,注意到出现“正反”和“反正”的概率一样,因此令“正反反正”、“反正正反”、“正反正反”分别为1、2、3,其余情况重来。另一种更妙的办法是,投掷三次硬币,“正反反”为1,“反正反”为2,“反反正”为3,其余情况重来。
- 发表于2010-01-27
6. 考虑一个n*n的棋盘,把有公共边的两个格子叫做相邻的格子。初始时,有些格子里有病毒。每一秒钟后,只要一个格子至少有两个相邻格子染上了病毒,那么他自己也会被感染。为了让所有的格子都被感染,初始时最少需要有几个带病毒的格子?给出一种方案并证明最优性。
答案:至少要n个,比如一条对角线上的n个格子。n个格子也是必需的。当一个新的格子被感染后,全体被感染的格子所组成的图形的周长将减少0个、2个或4个单位(具体减少了多少要看它周围被感染的格子有多少个)。又因为当所有格子都被感染后,图形的周长为4n,因此初始时至少要有n个被感染的格子。
- 发表于2010-01-27
7. 在一个m*n的棋盘上,有k个格子里放有棋子。是否总能对所有棋子进行红蓝二染色,使得每行每列的红色棋子和蓝色棋子最多差一个?
答案:可以。建一个二分图G(X,Y),其中X有m个顶点代表了棋盘的m个行,Y有n个顶点代表了棋盘的n个列。第i行第j列有棋子就在X(i)和Y(j)之间连一条边。先找出图G里的所有环(由于是二分图,环的长度一定是偶数),把环里的边红蓝交替染色。剩下的没染色的图一定是一些树。对每棵树递归地进行操作:去掉一个叶子节点和对应边,把剩下的树进行合法的红蓝二染色,再把刚才去掉的顶点和边加回去,给这个边适当的颜色以满足要求。
- 发表于2010-01-27
8. 任意给一个8*8的01矩阵,你每次只能选一个3*3或者4*4的子矩阵并把里面的元素全部取反。是否总有办法把矩阵里的所有数全部变为1?
答案:不能。大矩阵中有36个3*3的小矩阵和25个4*4的小矩阵,因此总共有61种可能的操作。显然,给定一个操作序列,这些操作的先后顺序是无关紧要的;另外,在一个操作序列中使用两种或两种以上相同的操作也是无用的。因此,实质不同的操作序列只有2^61种。但8*8的01矩阵一共有2^64种,因此不是每种情况都有办法达到目的。
- 发表于2010-02-10
答案:把扑克牌分成两堆,一堆10张,一堆42张。然后,把小的那一堆里的所有牌全部翻过来。