培玉 · 一试
2012 年山西预赛 · 第 8 题
F3填空题经典的计数模型
集合 是集合 的 20 元子集，且 中的任两个元素之差为 12 的倍数，则这种子集 的个数是。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
思路
所有元素必须属于模12的同一个剩余类，按类大小选20个。
解答
任意两个元素之差为12的倍数，当且仅当所有元素同余。因 ，模12有8个剩余类含168个元素，4个剩余类含167个元素。因此所求为 。
复核
任意20元子集至少含一个元素，所属剩余类唯一，十二类之间不重计；各类均足够选20个。
方法总结
两两差的整除条件可化为全体元素属于同一剩余类。
为什么评为 F3（会透露解法方向）
作者独立评为F3：所有元素必须属于模12的同一个剩余类，按类大小选20个。 关键转换后仍需核对定义域、边界或计数不重不漏。
用到的方法（会透露解法方向）
核心工具：剩余类、幂周期与局部排除、把对象唯一编码后分类计数
已记下，谢谢！