Which Way Did the Bicycle Go 趣题选(下)

 

23. 一些硬币互不重叠地放在桌上。四色定理告诉我们,若要对硬币进行染色,使得挨在一起的硬币颜色不同的话,最多只需要四种颜色就可以了。存在至少需要四种颜色的构造吗?

 

答案:存在。如图,若只允许三种颜色的话, A 的颜色必须与所有阴影硬币颜色相同, B 的颜色也必须与所有阴影硬币颜色相同, A 、 B 将会同色。

  


 
 

24. 将火柴棍视为边,其端点视为顶点,可以把用火柴棍拼成的图形看作一个平面图。试着用火柴棍拼一个所有顶点的度均为 3 的平面图。

 

答案:如图。

  

 
 

25. 圆周上有 2n 个等分点,每两点之间连一条边,构成一个完全图 K_2n 。是否存在一个 Hamilton 回路,使得图中经过的边互不平行?

 

答案:不存在这样的回路。把 2n 个顶点从 1 到 2n 顺次编号,并定义一条边的方向值为两端点的编号之和。显然,两条边平行当且仅当它们的方向值模 2n 同余。假设有一条 Hamilton 回路使得途中任意两边都不平行,则这些边的方向值只可能恰好为 1, 2, …, 2n (mod 2n),它们的和为 1 + 2 + … + 2n = 2n^2 + n ≡ n (mod 2n) 。另外,由于这是一条 Hamilton 回路,因此整条路所经过的边的方向值之和为 2 * (1 + 2 + … + 2n) = 4n^2 + 2n ≡ 0 (mod 2n) ,矛盾。

 
 

26. 证明:对任意正整数 n ,从 1 到 10^n 中的总数字个数等于从 1 到 10^(n+1) 中数字 0 出现的次数。

 

答案:对于 1 到 10^n 中每个数,列出所有在中间插入一个 0 后可以得到的数,构成一个新的数列:

    10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 100, 101, 110, 102, 120, …

由于对于一个 k 位数来说,在中间插入一个 0 有 k 种方法,因此数列的总项数就等于 1 到 10^n 中的总数字个数。下面我们只需说明,数列的总项数也等于 1 到 10^(n+1) 中数字 0 出现的次数。这是因为数列中的所有数显然都不超过 10^(n+1) ,并且显然一个数有几个 0 ,它就在该数列中出现了几次。

 
 

27. 经过一个公共点的 n 个平面(但任意三个平面不过同一直线)把空间分为了多少块?

 

答案:以这个公共点为球心做一个球面,我们要求的即是球面被切分出来的区域数。在这个球面上利用 Euler 公式 V – E + F = 2 ,我们能很快求出 F 的值。由于每对大圆有两个交点,因此 V = 2 * C(n, 2) ;由于每个顶点的度都为 4 ,因此 E = 4V/2 = 2V。于是 F = E – V + 2 = 2V – V + 2 = V + 2 = n^2 – n + 2。
利用 Euler 公式还可以瞬间秒杀下面这个经典问题: n 个圆最多可以把平面分成多少块?由于每两个圆之间都有两个交点,因此顶点数 V = n(n – 1) ;由于每个圆被切成了 2(n – 1) 条弧,因此 E = 2n(n – 1) 。于是, F = E – V + 2 = 2n(n – 1) – n(n – 1) + 2 = n^2 – n + 2 。
注意到,上述两个问题答案是一样的。其实,这并不是巧合。把前一个问题中的球面从北极点投影到与南极点相切的平面上,你就会发现这两个问题其实是一回事。

 
 

28. 证明:当 m 、 n 互质时, m×n 的棋盘的对角线恰好穿过 m + n – 1 个格子。

  

 

答案:由于 m 、 n 互质,显然对角线不会穿过交叉点。而从左下角到右上角必须要经过 m – 1 条竖直线和 n – 1 条水平线,因此对角线与棋盘必然有 m + n – 2 个交点,即它穿过了 m + n – 1 个格子。该结论可扩展为:对任意正整数 m 、 n , m×n 的棋盘的对角线恰好穿过 m + n – gcd(m, n) 个格子。

 
 

29. 在空间中放置 8 个点,使得对于任意三个点,它们之间的三条线段中至少有两条一样长。换句话说,这 8 个点确定的所有三角形(包括退化成线的三角形)都是等腰三角形。

 

答案:在 x-y 平面作一个单位圆,标出它的五等分点。另外三个点放在 (0, 0, 0) 、 (0, 0, -1) 和 (0, 0, 1) 处。

  

 
 

30. 证明:每组对边都相等的四面体中,每个面都是锐角三角形。

  

 

答案:把三角形 △PQR 和 △PSR 想象成是由转轴 PR 连接的两个三角形木板, QS 是一条橡皮筋。旋转 △PSR 使得 △PSR 和 △PQR 位于同一平面,橡皮筋 QS 将被拉长到 d 。此时,整个图形变成了一个平行四边形。由于对角线 d > c ,因此 ∠PQR < 90° 。同理可知,四面体中的每个角都小于 90° 。

  

 
 

31. 对于空间中的点集 E ,把所有点对确定的直线所构成的点集记作 L(E) 。如果 V 是一个正四面体的四个顶点,那么 L(V) 就是该四面体的六条边所在的直线所组成的点集。请问: L(L(V)) 是否包含了空间中所有点?

 

答案:不是。如图,设想一个由正方体六个面的对角线构成的正四面体。下面我们说明, P 点不在 L(L(V)) 中。首先,在四面体中相邻的边上取点,确定出来的直线始终在四面体的面上,不会过 P 点;在对边上取点构成的连线也不会过 P ,比方说同时过红色线段和蓝色线段的直线一定不会过 P ,因为过 P 且与红色线段相交的线都在正方体的顶面上。

  

可以证明,不在 L(L(V)) 中的点只有正方体中不在四面体上的那四个顶点。

 
 

32. 一幢大楼的底层有 1001 根电线,这些电线一直延伸到大楼楼顶。你需要确定底层的 1001 个线头和楼顶的 1001 个线头的对应关系。你有一个电池,一个灯泡,和许多很短的电线。如何只上下楼一次就确定电线线头的对应关系?

 

答案:对于奇数根电线的情况,都可以采用下面这种做法。在楼下把线头两个两个相接,余下单独一个线头什么都不接。把这个单出来的线头标号为 #1 。到楼顶找出和谁接都不构成回路的导线,它就是 #1 。在剩下的导线中测出能构成回路的导线对,并标号为 (#2, #3) , (#4, #5) ,…… 。接下来,把 #1 和 #2 相接, #3 和 #4 相接,依此类推,让 #1001 单着。到楼下拆掉原有的连接,然后从 #1 开始顺藤摸瓜确定所有对应关系:和 #1 能构成回路的导线就是 #2 ,原来和 #2 配对的就是 #3 ,和 #3 能构成回路的就是 #4 ,依此类推。

 
 

33. 桌子上有 15 张大小形状任意的纸,它们完全覆盖了整个桌面。这些纸可能有重叠,也可能伸出桌面。证明:总能从中拿走其中 5 张纸,使得剩下的纸仍然覆盖了至少 2/3 的桌面。

 

答案:假设纸在放到桌面上之前,桌面上刷满了红色颜料。把纸覆盖上去后,某一些纸(的全部或某些部分)染上了颜色。由于整个桌面被完全覆盖,因此所有纸上的所有红色区域面积总和恰好等于桌面面积。如果我们拿掉颜料最少的五张纸,则拿走的颜料面积显然不会超过 1/3 ,也就是说纸上的红色面积之和还有至少 2/3 ,即还有至少 2/3 的桌面是被覆盖了的。

 
 

34. 即使钟的时针和分针一样长,大多数时候也能读出正确的时间来。例如,两针一个指向 12 一个指向 6 ,那么前者只能是分针,后者只能是时针。但有时候,时针和分针的位置互换后,所指的时间仍然有意义,我们就说这时的指针位置有歧义。从 0:00 到 12:00 这 12 个小时中,指针位置会产生歧义的时刻有多少个?

 

答案: 132 个。假设有 A 、 B 两个钟叠放在一起, A 以正常的速度运转, B 以 12 倍的速度运转。因此, B 的时针将永远与 A 的分针重合。每当 B 的分针与 A 的时针重合时, A 此时所指的时刻就是有歧义的。而 B 的分针比 A 的时针快 144 倍,因此 A 的时针转了一圈后, B 的分针转了 144 圈,因此 B 的分针与 A 的时针重合了 143 次。但是,这其中有 11 次是同一个钟的时针和分针本身就重合的,不会导致歧义,因此真正会导致歧义的有 143 – 11 = 132 个时刻。

 
 

35. Alice 和 Bob 玩猜数游戏。 Alice 背着 Bob 写下 n 个正整数 x1, x2, …, xn 。然后 Bob 选择 n 个正整数 a1, a2, …, an 告诉 Alice , Alice 说出 a1·x1 + a2·x2 + … + an·xn 的值。接下来, Bob 又选择另外 n 个正整数 b1, b2, …, bn ,并获知 Σbi·xi 的值。如此下去,直到 Bob 能够推出 Alice 写下的 n 个数。 Bob 需要多少次询问就可以保证猜出所有 n 个数?

 

答案:两次。先选择 a1 = a2 = … = an = 1 ,从而获知 n 个数之和 S 。注意到,由于 Alice 写下的数都是正整数,因此对所有 i 都有 xi ≤ S 。然后,选择 b1 = 1, b2 = S+1, b3 = (S+1)^2, …, bn = (S+1)^(n-1),然后 Alice 将告诉他一个数

    N = x1 + x2·(S+1) + x3·(S+1)^2 + … + xn·(S+1)^(n-1)

接下来, Bob 只需要把 N 写成 S+1 进制,每个数位上的数就依次是 Alice 的那 n 个数了。

下面我们证明,两次询问已经是最优的了,只问一次是猜不出来的。假设 Bob 第一次询问得到的结果是 a1 + a2 + … + an + a1·a2 ,则他没法知道 Alice 的 n 个数是 a2+1, 1, 1, …, 1 ,还是 1, a1+1, 1, 1, …, 1 。

 
 

36. 桌上有两个盒子,一个盒子里有 51 枚硬币,一个盒子里有 101 枚硬币。 Alice 和 Bob 轮流把其中一个盒子的硬币倒掉,再把另一个盒子里的硬币分装在两个盒子中。最后谁不能继续操作了,谁就输了。如果 Alice 先走,谁有必胜策略?

 

答案: Bob 必胜。 Alice 走后,两个盒子里的硬币数必然是一奇一偶。 Bob 倒掉有奇数枚硬币的盒子,把剩下的硬币分成 1 加另一个奇数。这样 Bob 面前总有一个盒子里有偶数枚硬币,因此他始终有走的。

 
 

37. 如果一个平面向量满足 y ≥ 0 ,我们就说这个向量是朝上的。两个朝上的单位向量,其向量和可能很小很小。证明:奇数个朝上的单位向量,向量和的长度不可能小于 1 。

 

答案:假设 n 个向量分别为 V1, V2, …, Vn 。注意到, V1 + V2 + … + Vn = V1 + (V2 + … + Vn) ,而两个向量的夹角变大将使得和向量变小,因此把 V1 变成 (1, 0) 或 (-1, 0) 中的某一个,那么这 n 个向量的和将会变得更小。反复利用该引理可知,这 n 个向量都是水平向量时,向量和最小。而奇数个单位水平向量的最小值为 1 。

 
 

38. 假设 n 次多项式 p(x) 满足,对于所有 x ,都有 p(x) ≥ 0 。证明,对于所有 x ,都有 p(x) + p'(x) + p”(x) + … + p^(n)(x) ≥ 0

 

答案:由于对于所有 x 都有 p(x) ≥ 0 ,因此 p(x) 的次数 n 一定是偶数,且最高次项系数大于 0 。令 q(x) = p(x) + p'(x) + p”(x) + … + p^(n)(x) ,显然 q(x) 的次数和最高次项系数跟 p(x) 一样,因此 q(x) 存在一个最小值,比方说 q(x0) 。我们只需要说明 q(x0) ≥ 0 即可。
由于 q(x0) 是最小值,因此 q'(x0) = 0 。而 q'(x) = p'(x) + p”(x) + … + p^(n)(x) = q(x) – p(x) ,因此 q(x0) – p(x0) = 0 ,即 q(x0) = p(x0) ≥ 0 。

 
 

39. 是否有可能在平面上画不可数个不相交的 8 ?

  

 

答案:不可能。对于任意一个 8 字形,在两个洞里各取一个有理点 P 、 Q (由于平面上的有理点是稠密的,这是总能办到的),则称这个 8 字形圈住了有理点对 (P, Q) 。注意到由于 8 字形不能相交,因此两个 8 字形不可能圈住同一对有理点。由于平面上的有理点对是可数的,因此 8 字形的数量也是可数的。

18 条评论

回复给 orbea jersey 取消回复