称集合 $S$ 是“非乘积的”，如果不存在 $a\text{,}b\text{,}c\in S$（$a\text{,}b\text{,}c$ 可以相同）使得 $ab\text{=}c$ 。例如，空集和 $\left\{ 16\text{,}20 \right\}$ 都是“非乘积的”，$\left\{ 4\text{,}16 \right\}\text{,}\left\{ 2\text{,}8\text{,}16 \right\}$ 不是“非乘积的”。求集合 $\left\{ 1\text{,}2\text{,}3\text{,}4\text{,}5\text{,}6\text{,}7\text{,}8\text{,}9\text{,}10 \right\}$“非乘积的”子集的个数。
【难度】
【出处】
2017年第35届美国数学邀请赛Ⅰ（AIMEⅠ）
【标注】
【答案】
252
【解析】
我们根据子集的最小元素进行分类讨论。设 $S$ 为一个“非乘积”的子集。
1．如果 $S$ 的最小元素为 $\text{2}$：考虑集合 $\left\{\text{3},\text{6},\text{9} \right\}$，则该集合的子集中有 $5$ 个可以是 $S$ 的子集，分别为 $\left\{ \text{3}\right\}\left\{ \text{6} \right\}\left\{ \text{9} \right\}\left\{\text{6},\text{9} \right\}\varnothing $ 。考虑集合 $\left\{ \text{5},\text{10} \right\}$，则 $\left\{\text{5} \right\}\left\{ \text{10} \right\}\varnothing $ 这三个子集可以是 $S$ 的子集。因为 $\text{2}*\text{2=4}$，所以 $S$ 不含 $4$ 。考虑集合
2．如果 $S$ 的最小元素为 $3$：$S$ 的惟一限制是不含 $9$ 。于是此类情况共有 ${{2}^{6}}\text{=}64$ 个
3．如果 $S$ 的最小元素大于 $3$：$S$ 可为 $\left\{4\text{,}5\text{,}6\text{,}7\text{,}8\text{,}9\text{,}10 \right\}$ 的任一子集，包含空集。于是此类情况共有 ${{2}^{7}}\text{=}128$ 个
综上，一共有 $60+64+128\text{=}252$ 个
1．如果 $S$ 的最小元素为 $\text{2}$：考虑集合 $\left\{\text{3},\text{6},\text{9} \right\}$，则该集合的子集中有 $5$ 个可以是 $S$ 的子集，分别为 $\left\{ \text{3}\right\}\left\{ \text{6} \right\}\left\{ \text{9} \right\}\left\{\text{6},\text{9} \right\}\varnothing $ 。考虑集合 $\left\{ \text{5},\text{10} \right\}$，则 $\left\{\text{5} \right\}\left\{ \text{10} \right\}\varnothing $ 这三个子集可以是 $S$ 的子集。因为 $\text{2}*\text{2=4}$，所以 $S$ 不含 $4$ 。考虑集合
2．如果 $S$ 的最小元素为 $3$：$S$ 的惟一限制是不含 $9$ 。于是此类情况共有 ${{2}^{6}}\text{=}64$ 个
3．如果 $S$ 的最小元素大于 $3$：$S$ 可为 $\left\{4\text{,}5\text{,}6\text{,}7\text{,}8\text{,}9\text{,}10 \right\}$ 的任一子集，包含空集。于是此类情况共有 ${{2}^{7}}\text{=}128$ 个
综上，一共有 $60+64+128\text{=}252$ 个
答案
解析
备注
