阅读提示:
如果是移动端阅读,可能会发生公式截断的问题,需要将设备横屏变为宽屏模式才能正常阅读.毕竟数学内容不同于纯文字.
另外,网站采用mathjax渲染latex代码,qq或者微信内置浏览器第一次打开可能会只显示源码不作处理.需要退出后再次打开才能正确渲染,其他浏览器应无问题.
对于每个正整数 $k, a_k$ 是最 大的且不能被 3 整除的 $k$ 的约数. 定义数列 $\left\{S_n\right\}$ 为 $S_n=a_1+a_2+\cdots+a_n$ (例如, $S_6=1+2+$ $1+4+5+2)$. 证明: $S_n$ 被 3 整除当且仅当 $n$ 的三进制表示中, 1 的个数可以被 3 整除.
参考答案的做法比较复杂,我们这里用递推的方式书写.
首先,如果做本题之前做过另外一个小题,对本题会有所帮助:
设$a_n$是$n$的最大奇因子,求$S_{2^n}$.
核心想法是考虑到$a_{2n}=a_n,a_{2n-1}=2n-1$,故 \begin{gather} S_{2^n}=a_1+a_2+\dots+a_{2^n}\\ =(a_1+a_3+\dots+a_{2^n-1})+(a_2+a_4+\dots+a_{2^n})\\ =(1+3+\dots+(2^n-1))+(a_1+a_2+\dots+a_{2^{n-1}})\\ =(1+3+\dots+(2^n-1))+S_{2^{n-1}} \end{gather} 再由这个递推式求出$S_{2^n}$
本题的定义和上题非常类似,我们可以得到 \[ a_{3m+1}=3m+1,a_{3m+2}=3m+2,a_{3m}=a_m,\forall m \in \mn \]
于是 \begin{align} S_{3m}&=a_1+a_2+\dots+a_{3m}\\ &=1+2+4+5+\dots+(3m-2)+(3m-1)+(a_3+a_6+a_9+\dots+a_{3m})\\ &=3+9+\dots+(6m-3)+S_m \\ &\equiv S_m \pmod 3 \end{align}
这样就得到了$S_{3m}$和$S_m$的关系式.而题目中描述的三进制表达式也就自然而然出现了: \[ S_{3m+1}\equiv 3m+1+S_{3m} \equiv S_m+1 \pmod 3 \] \[ S_{3m+2}\equiv (3m+1)+(3m+2)+S_{3m} \equiv S_m \pmod 3 \]
概括而言,就是引理: \[ S_{3m+b} \equiv \delta(b)+S_m \pmod 3,b=0,1,2 \] 其中$\delta(1)=1,\delta(0)=\delta(2)=0$
设$n$的三进制表达为$\sum_{j=0}^k b_j \cdot 3^j,b_j \in \{0,1,2\},\forall j =0,1,2,\dots,k$,且$b_k \ne 0$
那么我们就有 \[ n=b_0+3(b_1+b_2 \cdot 3+\dots+b_k \cdot 3^{k-1}) \]
对$k$归纳: \[ S(\sum_{j=0}^k b_j \cdot 3^j) \equiv \sum_{j=0}^k \delta(b_j) \pmod 3 \] 当$k=0$容易验证成立
假设对$k-1$成立,则$S(b_1+b_2 \cdot 3+\dots+b_k \cdot 3^{k-1}) \equiv \sum_{j=1}^k \delta(b_j) \pmod 3$
考虑 \[ \sum_{j=0}^k b_j \cdot 3^j=b_0+3(b_1+b_2 \cdot 3+\dots+b_k \cdot 3^{k-1}) \]
使用上面的引理可得
\begin{align} S(\sum_{j=0}^k b_j \cdot 3^j) &\equiv \delta(b_0)+S(b_1+b_2 \cdot 3+\dots+b_k \cdot 3^{k-1}) \\ &\equiv \delta(b_0)+\sum_{j=1}^k \delta(b_j) \\ &\equiv \sum_{j=0}^k \delta(b_j) \pmod 3 \end{align}
则对$k+1$也成立
