绿皮书刷题记录_02
条评论这是绿皮书刷题记录系列的第 2 篇。
Trailing Zeros
How many trailing zeros are there in 100! (factorial of 100)?
首先，1 到 100 已经存在 11 个 0。
其次，$2\times5=10$，因此所有尾数为 2 和 5 的组合可以组成一个 0，因此又有 10 个 0。
再次，由于 $4\times25=100$，因此所有 25 的倍数可以再多组成一个 0，即 25、50、75。注意虽然 $4\times100=400$，但是相比 100 本来就有的两个 0，没有带来新的 0。因此又有 3 个 0。
还有没有更多的？有，但那是 $8\times128=1000$，而100以内没有 125 的倍数，因此到此为止。
0 的数量：$11+10+3=24$。
Wise Men
A sultan has captured 50 wise men. He has a glass currently standing bottom down. Every minute he calls one of the wise men who can choose either to turn it over (set it upside down or bottom down) or to do nothing. The wise men will be called randomly, possibly for an infinite number of times. When someone called to the sultan correctly states that all wise men have already been called to the sultan at least once, everyone goes free. But if his statement is wrong, the sultan puts everyone to death. The wise men are allowed to communicate only once before they get imprisoned into separate rooms (one per room). Design a strategy that lets the wise men go free.
这道题的关键在于，要选出一个特定的“spokesman”，由这个人来判断是否所有人都已经被叫到过了。
既然已经选出了这么一个人，那么剩下的人要保证：
- 每次被叫出来，必须传递“自己被叫出来了”这一信息；
- 如果被叫出来时上一个人的信息还没有被“spokesman”接收到，那么不可以破坏这一信息；
- 如果已经传递过一次信息了，那么接下来不能再次传递这一信息；
- 对于“spokesman”，如果接收到了信息，要通知下一个未传递信息的人传递信息。
那么解法就比较明确了：
- 对于“spokesman”，每次被叫出来都查看杯口是否朝下，朝下则说明有一个人传递过了信息。回去时，要保证杯口朝上；
- 对于其他人，如果未传递过信息且杯口朝上，则翻转杯子（传递信息）；如果已经传递过信息或者杯口朝下，则什么也不做。
那么当“spokesman”数到第 49 次杯口朝下，则可以判断所有人都至少被叫出来过一次了。
Missing Integers
Suppose we have 98 distinct integers from 1 to 100. What is a good way to find out the two missing integers (within [1, 100])?
利用两个连续整数数列求和性质：
$$
\displaylines{\sum_{n=1}^{N} n=\frac{N(N+1)}{2}={N^2\over2}+{N\over2}\\
\sum_{n=1}^{N} n^{2}=\frac{N(N+1)(2 N+1)}{6}=\frac{N^{3}}{3}+\frac{N^{2}}{2}+\frac{N}{6}}
$$
假设丢失的两个数为 $x$ 和 $y$，其他数为 $z_1,\dots,z_{98}$，那么我们可以列出两个关于 $x$ 和 $y$ 的式子：
$$
\begin{aligned}
&\sum_{n=1}^{100} n=x+y+\sum_{i=1}^{98} z_{i}\\ \Rightarrow & x+y=\frac{100 \times 101}{2}-\sum_{i=1}^{98} z_{i}
\end{aligned}
$$
$$
\begin{aligned}
&\sum_{n=1}^{100} n^{2}=x^{2}+y^{2}+\sum_{i=1}^{98} z_{i}^{2}\\ \Rightarrow & x^{2}+y^{2}=\frac{100^{3}}{3}+\frac{100^{2}}{2}+\frac{100}{6}-\sum_{i=1}^{98} z_{i}^{2}
\end{aligned}
$$
从而联立方程求解。
Prisoner Problem
One hundred prisoners are given the chance to be set free tomorrow. They are all told that each will be given a red or blue hat to wear. Each prisoner can see everyone else’s hat but not his own. The hat colors are assigned randomly and once the hats are placed on top of each prisoner’s head they cannot communicate with one another in any form, or else they are immediately executed. The prisoners will be called out in random order and the prisoner called out will guess the color of his hat. Each prisoner declares the color of his hat so that everyone else can hear it. If a prisoner guesses correctly the color of his hat, he is set free immediately, otherwise he is executed.
They are given the night to come up with a strategy among themselves to save as many prisoners as possible. What is the best strategy they can adopt and how many prisoners can they guarantee to save?
The two-color case is easy, isn’t it? What if there are 3 possible hat colors: red, blue, and white? What is the best strategy they can adopt and how many prisoners can they guarantee to save?
这道题被划分在“Modular Arithmetic”这一节里，但在我眼里依然是一个信息编码的问题。假设有 $n$ 种不同颜色的帽子由于每个人都知道其他人帽子是什么颜色，而自己帽子只有 $n$ 种可能，恰好第一个出去的人又能传递 $n$ 种信息，因此理论上是足以让剩下所有人知晓自己帽子颜色的。
题目的解法是，给各种颜色编码为 $0,1,\dots,n$，然后第一个人将剩下的人帽子颜色编码相加成为 $x$，如果 $x%n=0$ 就报第一种颜色，以此类推。而剩下的人根据其所报出的颜色，就知道他们帽子颜色编码总和对 $n$ 的模是多少，每个不同的模都对应一种他们帽子的颜色。举例而言，如果一个人是第 2 种颜色，那么他将剩下的帽子编码加起来的和对 $x$ 取模就会得到 $n-1$，那么他自然知道自己帽子颜色的编码是 1，也就意味着他帽子属于第二种颜色。
Division
Given an arbitrary integer, come up with a rule to decide whether it is divisible by 9 and prove it.
首先，令
$$
a=10^na_n+10^{n-1}a_{n-1}+\cdots+a_0
$$
又令 $x=a_n+a_{n-1}+\cdots+a_0$，则
$$
a-x=a_n(10^n-1)+a_{n-1}(10^{n-1}-1)+\cdots+a_1(10-1)
$$
注意，这里结果中的每一项都可被 9 整除，因此 $a-x$ 也可被 9 整除。
那么，如果 $x$ 可被 9 整除，也就能推出 $a$ 能被 9 整除。
类似地，下面讨论一个数能否被 11 整除的判断方法。
令
$$
y= (-1)^{n} a_{n}+(-1)^{n-1} a_{n-1}+\cdots+a_{0}
$$
则
$$
a-y=a_n\left(10^n-(-1)^n\right)+a_{n-1}\left(10^{n-1}-(-1)^{n-1}\right)+\cdots+a_1(10+1)
$$
注意，当 $n$ 为奇数时，我们有
$$
\left(10^n-(-1)^n\right)=10^n+1=(10+1)(10^n-10^{n-1}+\cdots+1)
$$
因而此时 $\left(10^n-(-1)^n\right)$ 可以被 11 整除。
而当 $n$ 为偶数时，我们有
$$
\left(10^n-(-1)^n\right)=99(10^{n-1}+10^{n-2}+\cdots+1)
$$
因而此时 $\left(10^n-(-1)^n\right)$ 同样可以被 11 整除。
根据以上两个条件，我们可以证明 $a-y$ 可以被 11 整除。从而，如果 $y$ 可以被 11 整除则证明 $a$ 可以被 11 整除。
Chameleon Colors
A remote island has three types of chameleons with the following population: 13 red chameleons, 15 green chameleons and 17 blue chameleons. Each time two chameleons with different colors meet, they would change their color to the third color. For example, if a green chameleon meets a red chameleon, they both change their color to blue. Is it ever possible for all chameleons to become the same color? Why or why not?
这道题最简便的思路如下。
如果最后一个状态是只剩下一种颜色，那么倒数第二个状态必然是，某两个颜色都只剩下一个变色龙。那么在这个过程中，必然存在至少一个状态，使得某两种颜色的变色龙数量相等。
现在我们注意到，在变化过程中，两两颜色相对数量要么保持不变，要么相对数量变化为 3。那么 13、15 和 17 三个数字，两两不可能变化到相等的状态。因此不可能最后仅剩下一个颜色。
Rainbow Hats
Seven prisoners are given the chance to be set free tomorrow. An executioner will put a hat on each prisoner’s head. Each hat can be one of the seven colors of the rainbow and the hat colors are assigned completely at the executioner’s discretion. Every prisoner can see the hat colors of the other six prisoners, but not his own. They cannot communicate with others in any form, or else they are immediately executed. Then each prisoner writes down his guess of his own hat color. If at least one prisoner correctly guesses the color of his hat, they all will be set free immediately; otherwise they will be executed.
They are given the night to come up with a strategy. Is there a strategy that they can guarantee that they will be set free?
这道题的的思路仍然用到取模运算。将帽子颜色编码为 $0,1,\dots6$，那么约定好，从第 1 个人到第 7 个人，其猜测的自己的帽子颜色所对应的编码，和其他颜色编码加起来，对 7 取模的结果分别为 $0,1,\dots6$。
举例而言，如果第 1 个人看到其他人的颜色编码总和对 7 取模结果为 5，那么他就猜自己是第 3 种颜色；如果看到这个结果的是第 2 个人，那么他猜自己是第 4 种颜色，以此类推。
以这种方式，很巧妙地，虽然每个人猜的颜色都不一样，但是由于取模覆盖了所有结果，因此刚好覆盖了所有可能性。
