第三十章 ：数竞训练！（第二更求追读月票）

【考虑序列ak=11...1{k个1}其中 k=1，2，…，n+1，这 n+1个数模n的余数只可能取0，1…，n?1。】

【由鸽巢原理，存在两个不同的下標 i<j使得a i≡a j(mod n).】

【计算差aj-a i=....】

看著稿纸上的算式，韩川思索著。

如果一个数要同时是n的倍数，並且所有数字都是0或1，那么它可以写成若干个10的冪次之和的形式。

但这里的问题转化为：能否在10的冪次中找到若干个数，它们的和恰好被n整除。

“10的冪次模n的余数...”

这个短语在他脑子里一闪，像一根火柴划亮了一片黑暗让他幡然醒悟了过来。

拾笔，落笔。

一行行的算式快速地在稿纸上写下。

“如果考虑数列10^1， 10^2， 10^3……一直到10^(n+1)，这n+1个数分別模n取余数。”

“而模n的余数只有n种可能——0到n-1。n+1个数放进n个盒子里，根据鸽巢原理，至少有两个数的余数相同。”

“將 n+1个全1数模 n的余数作为物体，余数的可能取值（0，1，…，n?1）作为抽屉，再对其进行整除性处理，就可以了。”

很快，答案就计算了出来。

由於 gcd(n，10)=1，n与 10 ^i互质，因此nir。而 r的每一位都是 1，故 r即为所求的 n的倍数！

“搞定！”

笔锋落下，韩川咧嘴笑了笑。

这题还真是有迷惑性，核心难度在於构造一个辅助数列。

如果用一般的构造倍数法来解题，他就算是解上一个晚上也算不出来。

但如果先构造辅助数列，再將『存在性』问题转化为『重复余数』问题，就很容易证明了！

解决了第一题，韩川迅速看向第二题。

【证明：对任意正整数 n，总存在一个 n的倍数，其十进位表示中每一位数字都是奇数（即只包含 1， 3， 5， 7， 9中的数字）。】

这道题与“仅由 0和 1组成”的结论类似，但限制为全奇数数字。

韩川尝试用鸽巢原理解答了一下，但很快就遇到了困难。

因为两个形如 111…1的数之差会產生末尾的 0，而 0是偶数。

很显然，相比第一题，这道题目的难度上升了不止一星半点。

他隱隱约约感觉到，第二题的思路跟第一题应该有某种对称性。

如果说第一题用的是10的冪次，第二题可能需要用到某种变形。

思索著，他在心里把这个命题拆开、重组、从不同的角度去尝试。

然后....然后他就卡住了。

看著稿纸上乱七八糟的算式，韩川有些头疼地揉了揉太阳穴。

他感觉做出来了一半，能感觉到答案就在前面不远的地方，但中间隔著一层薄雾，他看不清路。

就在这时，他带过来放在桌角的数学教材微微亮了一下，一行字跡浮现了出来。

是葛军的，笔锋锐利如刀。

“你可真是个狗脑子，都想到了10的冪次可以构造全0的数，为什么就不会转弯！”

“蠢！”

很显然看著韩川被第二题卡住这么久，课本中的书灵葛大爷开始耐不住了，浮现出一行字跡『教育』他。

.....