数列的构造与论证

一列正整数$a_1,a_2,\cdots,a_n,\cdots$满足每个数都能整除之后的数,即$a_n\mid a_{n+1}$,则它们模$30$的余数最多可能有多少种不同的取值?


正确答案是$21$.

分析与解 将集合$\{1,2,\cdots,30\}$划分为元素质因数分解后不包含$2,3,5$的组成集合$A_0$;包含$2$但不包含$3,5$的组成集合$A_2$;包含$3$但不包含$2,5$的组成集合$A_3$;包含$5$但不包含$2,3$的组成集合$A_5$;包含$2,3$但不包含$5$的组成集合$A_{2,3}$;包含$3,5$但不包含$2$的组成集合$A_{3,5}$;包含$2,5$但不包含$3$的组成集合$A_{2,5}$;包含$2,3,5$的组成集合$A_{2,3,5}$,如下表.\[\begin{matrix}
name &type & set & card \\ \hline
A_0&x & 1,7,11,13,17,19,23,29 & 8 \\
A_2&2^k\cdot x & 2,4,8,14,16,22,26,28 & 8\\
A_3&3^k\cdot x & 3,9,21,27 & 4\\
A_5&5^k\cdot x & 5,25 & 2\\
A_{2,3}&2^{k_1}\cdot 3^{k_2}\cdot x & 6,12,18,24 &4\\
A_{3,5}&3^{k_1}\cdot 5^{k_2}\cdot x & 15 & 1\\
A_{2,5}&2^{k_1}\cdot 5^{k_2}\cdot x & 10,20 & 2\\
A_{2,3,5}&2\cdot 3\cdot 5 & 30 & 1\\ \hline
\end{matrix}\]容易知道,如果余数数列出现了$A_2$中的数,就不可能再出现$A_0$中的数;类似的,如果余数数列中出现了$A_{2,3}$中的数,就不可能出现$A_2,A_3$中的数.因此最多取值数为\[{\rm Card}(A_0)+{\rm Card}(A_2)+{\rm Card}(A_{2,3})+{\rm Card}(A_{2,3,5})=8+8+4+1=21.\]具体的构造可行性可以利用裴蜀定理证明.

 可以构造$a_n=\displaystyle \prod_{i=1}^nx_i$,其中$i=1,2,\cdots,$.而其中\[x_n:1,7,7,7,11,7,7,7,2,7,7,7,11,7,7,7,3,7,7,7,5,\cdots\]对应的余数数列为\[\underbrace{1,7,19,13,23,11,17,29}_{A_0},\underbrace{28,16,22,4,14,8,26,2}_{A_2},\underbrace{6,12,24,18}_{A_{2,3}},0,\cdots\]

此条目发表在解题展示分类目录,贴了标签。将固定链接加入收藏夹。

发表评论