2012江苏附加题

aishuxue

设集合 $P_n=\{1,2, \cdots, n\}, n \in \mathbf{N}^*$．记 $f(n)$ 为同时满足下列条件的集合 $A$ 的个数：
（1）$A \subseteq P_n$ ；（2）若 $x \in A$ ，则 $2 x \notin A$ ；（3）若 $x \in$ $\complement_{P_n} A$ ，则 $2 x \notin \complement_{P_n} A$ ．

• 求 $f(4)$ ；
• 求 $f(n)$ 的解析式（用 $n$ 表示）．

kuing

将答案细化，大概就是这种意思：
如果 $2x\leqslant n$，则条件（3）可以化为：若 $x\notin A$，则 $2x\in A$。
因此，当 $2x\leqslant n$ 时，$x$ 与 $2x$ 有且只有一个属于 $A$。
如果 $x$ 为偶数，则同理也有 $x/2$ 与 $x$ 有且只有一个属于 $A$，如此类推，直至 $x/2^k$ 为奇数，记此奇数为 $p$。
如果 $4x\leqslant n$，则同理也有 $2x$ 与 $4x$ 有且只有一个属于 $A$，如此类推，直至最大的 $2^kx$（即再翻倍就超过 $n$），记此 $2^kx$ 为 $q$。
也就是说，如果 $p$ 一旦被确定了属于 $A$ 与否，那么数列 $\{p, 2p, \ldots, x/4, x/2, x, 2x, 4x, \ldots, q\}$ 里的所有数是否属于 $A$ 也都被确定下来了，所以 $A$ 的情况就完全取决于对这些奇数 $p$ 的取舍。

aishuxue

非常好的解释，谢谢kuing！