Q:

Subset coloring, additive structure.

Let $S = \{1, 2, \dots, 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.
Prove that the number of colorings that satisfy the following condition is $1 + 3^n$: 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).$$

A:

Call a subset $T$ of $S$ "bluish" if $f(T) \ne 0$.  In a coloring that satisfies the condition, if $A$ and $B$ are both bluish, then $A \cap B$ is also bluish, since $f(A) f(B) = f(A \cup B) f(A \cap B) \ne 0$.  Therefore if there are any bluish sets at all, there is a unique minimal bluish set $$M = \bigcap_{T\textrm{ bluish}}T.$$
If $M \nsubseteq T$, $T$ is not bluish and is therefore red.  $f(M)=1$, since $M$'s only blue subset is $M$ itself.  The choice of $M$ and the color of the sets $M \cup \{k\}$ for each $k \in S \setminus M$ determine the entire coloring:
(*) Given $T \subseteq S$, $T$ is blue iff $M \subseteq T$ and $M \cup \{k\}$ is blue for every $k \in T \setminus M$.
(**) Given $T \supseteq M$, $f(T) = 2^s$, where $s$ is the number of $k \in T \setminus M$ such that $M \cup \{k\}$ is blue.
The two statements (*) and (**) are proved together by induction on the number of elements in $T$.  The statements are obvious for $|T|=|M|$ and $|T|=|M|+1$.  If both statements are true of $T$ with $M \subseteq T \subseteq S$ and $k \notin T$, then we must have
$$f(T) f(M \cup \{k\}) = f(T \cup \{k\}) f(M)$$
If $M \cup \{k\}$ is red, then $f(M \cup \{k\})=1$ and $f(T) = f(T \cup \{k\}) = 2^s$, so $T \cup \{k\}$ is red.
If $M \cup \{k\}$ is blue, then $f(M \cup \{k\})=2$ and $2 f(T) = f(T \cup \{k\}) = 2^{s+1}$, which can only happen if $T \cup \{k\}$ is blue.
So the total number of colorings is
$$ N = 1 + \sum_{i=0}^n (\mbox{choices for $M$ with $|M|=i$})(\mbox{choices for colors of $M \cup \{k\}$})$$
where the one extra coloring is the all-red coloring where $M$ does not exist.
$$ N = 1 + \sum_{i=0}^n \binom{n}{i} 2^{n-i} = 1 + (1+2)^n = 1 + 3^n$$

