每日一题[2108]组合计数

设集合 $A=\{1,2,3,\cdots,2045\}$,如果 $A$ 的子集 $S$ 的任何一个元素都不是另一个元素的三倍,就称集合 $S$ 是三倍自由的.三倍自由集合 $S$ 中元素个数最多的集合个数为 $n$,且 $n$ 可以表示为 $p^aq^b$ 的形式,其中 $p,q$ 为质数,$a,b$ 为正整数.若 $N=p^2+q^2+a^2+b^2$,则 $N$ 的末三位数是_______.

答案    $202$.

解析    将集合分划为\[\begin{array}{c|ccccccc}\hline \text{组号}&1&2&3&4&5&6&7\\ \hline 1&1&3&9&27&81&243&729 \\ \hline 2&2&6&18&52&162&486&1458\\ \hline 3&4&12&36&108&324&972&\\ \hline 4&5&15&45&135&405&1215& \\ \hline \cdots&\cdots&&&&&&\\ \hline \end{array}\] 每一组都是先写出之前没有出现过的最小的数,然后不断乘以 $3$,直到超出集合 $A$ 的范围为止,则每组的开头的数为所有不被 $3$ 整除的数\[1,2,4,5,7,8,\cdots,\]其中组中含有的元素个数(长度)与对应组数的关系为\[\begin{array}{c|ccccccc} \hline \text{长度}&7&6&5&4&3&2&1\\ \hline \text{首项}&1,2&4,5,7,8&10\sim 25&26\sim 75&76\sim 227&229\sim 680&682\sim 2045 \\ \hline \text{组数}&2&4&11&33&102&302&910 \\ \hline\end{array}\]在每组个数中最多可以隔项取一个,如长度为 $7$ 的数组\[\boxed{1},3,\boxed{9},27,\boxed{81},243,\boxed{729},\]最多取 $4$ 个.这样可以得到一个包含元素个数为\[4\cdot 2+3\cdot (4+11)+2\cdot (33+102)+1\cdot (302+910)=1535\]的三倍自由集合.容易构造抽屉证明 $1535$ 是三倍自由集合 $S$ 中元素个数的最大值.下面求 $n$,长度为奇数的组取法固定,长度为 $6$ 的组有 $4$ 种不同的取法,长度为 $4$ 的组有 $3$ 种不同的取法,长度为 $2$ 的组有 $2$ 种不同的取法,因此\[n=4^4\cdot 3^{33}\cdot 2^{302}=2^{310}\cdot 3^{33},\]从而\[N=2^2+302^2+3^2+37^2=97202,\]其末三位数字为 $202$.

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

发表评论