题目
将42个正整数（不一定各自不同）写成一行。证明，通过在数字间插入加号、乘号和括号，使得最终的计算结果是100万的倍数。
分析
这个题目要用到鸽巢原理，但不是那么直观。
先分解目标：
\(1000000=2^6\cdot5^6\)
并注意到：
\(42=6\cdot2+6\cdot5\)
于是把42个数按原顺序分成12段连续子串：其中6段长度为2，另外6段长度为5；最后把这12段的结果相乘。这样只要做到
- 每个长度为2的段能变成偶数；
- 每个长度为5的段能变成5的倍数；
那么总乘积就至少含有\(2^6\)和\(5^6\)，从而是1000000的倍数。
长度为2的段很容易：设两个数为\(a,b\)。
- 若\(a,b\)同奇偶，则取\(a+b\)，为偶数；
- 若一奇一偶，则取\(ab\)，为偶数。
所以每个2段都可构造成偶数。
关键是长度为5的段。设该段为\(n_1,\ldots,n_5\)。我们只要找到一个连续子串，其和是5的倍数，就可以把这段写成“该和”乘以“其余项的乘积”，于是整段是5的倍数。
下面用鸽巢原理证明这种子串一定存在。
设前缀和
\(s_i=n_1+\cdots+n_i\quad(i=1,\ldots,5)\)
并记
\(r_i\equiv s_i\pmod5\)
- 若某个\(r_i=0\)，则\(n_1+\cdots+n_i\)就是5的倍数，直接完成；
- 否则\(r_1,\ldots,r_5\)都在集合\(\{1,2,3,4\}\)里。5个数落在4个抽屉中，按鸽巢原理必有\(r_i=r_j(i<j)\)。
于是
\(s_j-s_i=n_{i+1}+\cdots+n_j\)
是5的倍数，得到所需连续子串。
所以每个5段都能构造成5的倍数。
综上，6个2段各贡献一个因子2，6个5段各贡献一个因子5，因此整体表达式是\(2^6\cdot5^6=1000000\)的倍数。
另外，上述“5段”论证可直接推广：任意\(n\)个整数都存在非空连续子串，其和是\(n\)的倍数。
一个实例
下面给一个局部演示，看看规则如何实际操作。
先看一个长度为2的段：\((3,8)\)。两数一奇一偶，因此取乘法，得到\(3\times8=24\)，是偶数。
再看一个长度为5的段：\((2,7,4,6,9)\)。其前缀和为
\(s_1=2,s_2=9,s_3=13,s_4=19,s_5=28\)
模5余数分别是
\(2,4,3,4,3\)
可见\(r_2=r_4=4\)，所以
\($s_4-s_2=19-9=10\)$
也就是中间连续子串\(4+6=10\)是5的倍数。于是这5个数可写成
\($(4+6)\times2\times7\times9\)$
显然是5的倍数。
整道题里把42个数分成6个2段和6个5段后，对每段都按同样方法处理，最后把12段结果相乘，就得到100万的倍数。