2.答案：如果是公正的硬币，则投掷两次，“正反”为1，“反正”为2，“正正”为3，“反反”重来。
如果是不公正的硬币，注意到出现“正反”和“反正”的概率一样，因此令“正反反正”、“反正正反”、“正反正反”分别为1、2、3，其余情况重来。另一种更妙的办法是，投掷三次硬币，“正反反”为1，“反正反”为2，“反反正”为3，其余情况重来。

3.答案：先取者可以让自己总是取奇数位置上的硬币或者总是取偶数位置上的硬币。数一数是奇数位置上的面值总和多还是偶数位置上的面值总和多，然后总是取这些位置上的硬币就可以了。

4.答案：总存在一个加油站，仅用它的油就足够跑到下一个加油站（否则所有加油站的油量加起来将不够全程）。把下一个加油站的所有油都提前搬到这个加油站来，并把油已被搬走的加油站无视掉。在剩下的加油站中继续寻找油量足以到达下个加油站的地方，不断合并加油站，直到只剩一个加油站为止。显然从这里出发就能顺利跑完全程。
另一种证明方法：先让汽车油箱里装好足够多的油，随便从哪个加油站出发试跑一圈。车每到一个加油站时，记录此时油箱里剩下的油量，然后把那个加油站的油全部装上。试跑完一圈后，检查刚才路上到哪个加油站时剩的油量最少，那么空着油箱从那里出发显然一定能跑完全程。

5.答案：先考虑一个看似无关的问题——怎样产生一个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个格子也是必需的。当一个新的格子被感染后，全体被感染的格子所组成的图形的周长将减少0个、2个或4个单位（具体减少了多少要看它周围被感染的格子有多少个）。又因为当所有格子都被感染后，图形的周长为4n，因此初始时至少要有n个被感染的格子。

7.答案：可以。建一个二分图G(X,Y)，其中X有m个顶点代表了棋盘的m个行，Y有n个顶点代表了棋盘的n个列。第i行第j列有棋子就在X(i)和Y(j)之间连一条边。先找出图G里的所有环（由于是二分图，环的长度一定是偶数），把环里的边红蓝交替染色。剩下的没染色的图一定是一些树。对每棵树递归地进行操作：去掉一个叶子节点和对应边，把剩下的树进行合法的红蓝二染色，再把刚才去掉的顶点和边加回去，给这个边适当的颜色以满足要求。

8.答案：不能。大矩阵中有36个3*3的小矩阵和25个4*4的小矩阵，因此总共有61种可能的操作。显然，给定一个操作序列，这些操作的先后顺序是无关紧要的；另外，在一个操作序列中使用两种或两种以上相同的操作也是无用的。因此，实质不同的操作序列只有2^61种。但8*8的01矩阵一共有2^64种，因此不是每种情况都有办法达到目的。

9.答案：按照2, 3, 4, 2, 3, 4的顺序检查狐狸洞可以保证抓住狐狸。为了说明这个方案是可行的，用集合F表示狐狸可能出现的位置，初始时F = {1, 2, 3, 4, 5}。如果它不在2号洞，则第二天狐狸已经跑到了F = {2, 3, 4, 5}。如果此时它不在3号洞，则第三天狐狸一定跑到了F = {1, 3, 4, 5}。如果此时它不在4号洞，则再过一晚后F = {2, 4}。如果此时它不在2号洞，则再过一天F = {3, 5}。如果此时它不在3号洞，再过一天它就一定跑到4号洞了。
方案不是唯一的，下面这些方案都是可行的：
2, 3, 4, 4, 3, 2
4, 3, 2, 2, 3, 4
4, 3, 2, 4, 3, 2

10.答案：事实上，从一个更强的命题出发反而能使问题变得更简单。对于一个a*b*c的长方体，我们需要f(a)+f(b)+f(c)刀，其中f(x)=log(x)/log(2)。只需要注意到，在整个过程中的任何一步，切完当前最大的块所需要的刀数也就等于整个过程还需要的刀数，因为其它小块需要的刀数都不会超过最大块所需刀数，它们都可以与最大块一道并行处理。这表明，我们的最优决策即是让当前的最大块尽可能的小，也就是说要把当前的最大块尽可能相等地切成两半。利用数学归纳法，我们可以很快得到本段开头的结论。

11.答案：先行者在桌子中心放置一枚硬币，以后的硬币总是放在与后行者刚才放的地方相对称的位置。这样，只要后行者能放，先行者一定也有地方放。先行者必胜。

12.答案：先将整篇文章的所有字符逆序（从两头起不断交换位置相对称的字符）；然后用同样的办法将每个单词内部的字符逆序。这样，整篇文章的单词顺序颠倒了，但单词本身又被转回来了。

13.答案：把字符串切成长为m和n-m的两半。将这两个部分分别逆序，再对整个字符串逆序。

14.答案：注意到平分矩形面积的线都经过矩形的中心。过大矩形和空心矩形各自的中心画一条线，这条线显然把两个矩形都分成了一半，它们的差当然也是相等的。

15.答案：N x M – 1次显然足够了。这个数目也是必需的，因为每掰一次后当前巧克力的块数只能增加一，把巧克力分成N x M块当然需要至少掰N x M – 1次。

16.答案1（关于数字位数线性）：for(n=0; b; b >>= 1) if (b & 1) n++;
答案2（关于”1″的个数线性）：for(n=0; b; n++) b &= b-1;

17.答案：计算数组中的所有数的和，再计算出从1到N-1的所有数的和，两者之差即为重复的那个数。计算数组中的所有数的和，再计算出从1到N+1的所有数的和，两者之差即为缺少的那个数。

18.答案：(b & (b-1)) == 0

19.答案：“北极点”是一个传统的答案，其实这个问题还有其它的答案。事实上，满足要求的点有无穷多个。所有距离南极点1 + 1/(2π)英里的地方都是满足要求的，向南走一英里后到达距离南极点1/(2π)的地方，向东走一英里后正好绕行纬度圈一周，再向北走原路返回到起点。事实上，这仍然不是满足要求的全部点。距离南极点1 + 1/(2kπ)的地方都是可以的，其中k可以是任意一个正整数。

20.答案：A把药放进箱子，用自己的锁把箱子锁上。B拿到箱子后，再在箱子上加一把自己的锁。箱子运回A后，A取下自己的锁。箱子再运到B手中时，B取下自己的锁，获得药物。

21.答案：握手次数只可能是从0到2N-2这2N-1个数。除去男主人外，一共有2N-1个人，因此每个数恰好出现了一次。其中有一个人(0)没有握手，有一个人(2N-2)和所有其它的夫妇都握了手。这两个人肯定是一对夫妻，否则后者将和前者握手（从而前者的握手次数不再是0）。除去这对夫妻外，有一个人(1)只与(2N-2)握过手，有一个人(2N-3)和除了(0)以外的其它夫妇都握了手。这两个人肯定是一对夫妻，否则后者将和前者握手（从而前者的握手次数不再是1）。以此类推，直到握过N-2次手的人和握过N次手的人配成一对。此时，除了男主人及其配偶以外，其余所有人都已经配对。根据排除法，最后剩下来的那个握手次数为N-1的人就是女主人了。

22.答案：两个机器人同时开始以单位速度右移，直到一个机器人走到另外一个机器人的起点处。然后，该机器人以双倍速度追赶对方。程序如下。

while(!at_other_robots_start) {
move_right 1
}
while(true) {
move_right 2
}

23.答案：选择第一种游戏，并写下“我既不会得到10美元，也不会得到10000000美元”。

24.答案：在下面把2,3连在一起，把4到6全连在一起，把7到10全连在一起，等等，这样你就把电线分成了6个“等价类”，大小分别为1, 2, 3, 4, 5, 6。然后到楼顶，测出哪根线和其它所有电线都不相连，哪些线和另外一根相连，哪些线和另外两根相连，等等，从而确定出字母A..U各属于哪个等价类。现在，把每个等价类中的第一个字母连在一起，形成一个大小为6的新等价类；再把后5个等价类中的第二个字母连在一起，形成一个大小为5的新等价类；以此类推。回到楼下，把新的等价类区别出来。这样，你就知道了每个数字对应了哪一个原等价类的第几个字母，从而解决问题。

25.答案：把手上的三片药各自切成两半，分成两堆摆放。再取出一粒药片A，也把它切成两半，然后在每一堆里加上半片的A。现在，每一堆药片恰好包含两个半片的A和两个半片的B。一天服用其中一堆即可。

26.答案：给处理器从1到n标号。用符号a->b表示向标号为a的处理器询问处理器b是不是好的。首先问1->2，如果1说不是，就把他们俩都去掉（去掉了一个好的和一个坏的，则剩下的处理器中好的仍然过半），然后从3->4开始继续发问。如果1说2是好的，就继续问2->3，3->4，……直到某一次j说j+1是坏的，把j和j+1去掉，然后问j-1 -> j+2；或者从j+2 -> j+3开始发问，如果前面已经没有j-1了（之前已经被去掉过了）。注意到你始终维护着这样一个“链”，前面的每一个处理器都说后面那个是好的。这条链里的所有处理器要么都是好的，要么都是坏的。当这条链越来越长，剩下的处理器越来越少时，总有一个时候这条链超过了剩下的处理器的一半，此时可以肯定这条链里的所有处理器都是好的。或者，越来越多的处理器都被去掉了，链的长度依旧为0，而最后只剩下一个或两个处理器没被问过，那他们一定就是好的了。另外注意到，第一个处理器的好坏从来没被问过，仔细想想你会发现最后一个处理器的好坏也不可能被问到（一旦链长超过剩余处理器的一半，或者最后没被去掉的就只剩这一个了时，你就不问了），因此询问次数不会超过n-2。

27.答案：你可以把两个相机放在圆盘上相近的两点，然后观察哪个点先变色。事实上，只需要一个相机就够了。控制相机绕圆盘中心顺时针移动，观察颜色多久变一次；然后让相机以相同的速度逆时针绕着圆盘中心移动，再次观察变色的频率。可以断定，变色频率较慢的那一次，相机的转动方向是和圆盘相同的。