每日一题[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$．