2015 USAMO 第 3 题

Let $S = \{1, 2, ..., n\}$, where $n \ge 1$. Each of the $2^n$ subsets of $S$ is to be colored red or blue. (The subset itself is assigned a color and not its individual elements.) For any set $T \subseteq S$, we then write $f(T)$ for the number of subsets of T that are blue.

Determine the number of colorings that satisfy the following condition: for any subsets $T_1$ and $T_2$ of $S$,

$$

f(T_1)f(T_2) = f(T_1 \cup T_2)f(T_1 \cap T_2).

$$

令 $S = \{1, 2, ..., n\}$，其中 $n \ge 1$。 $S$ 的每个 $2^n$ 子集都将被涂成红色或蓝色。 (子集本身被分配了颜色，而不是它的各个元素。)对于任何集合 $T \subseteq S$，我们将 T 的蓝色子集的数量写为 $f(T)$。

确定满足以下条件的着色数：对于$S$的任意子集$T_1$和$T_2$，

$$f(T_1)f(T_2) = f(T_1 \cup T_2)f(T_1 \cap T_2)。$$