Let $S=\{1,2, \ldots, n\}$, where $n \geq 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\left(T_{1}\right) f\left(T_{2}\right)=f\left(T_{1} \cup T_{2}\right) f\left(T_{1} \cap T_{2}\right) $$
For an $n$-coloring $\mathcal{C}$ (by which we mean a coloring of the subsets of $\{1, \ldots, n\}$), define the support of $\mathcal{C}$ as 
$$ \operatorname{supp}(\mathcal{C})=\{T \mid f(T) \neq 0\} $$
Call a coloring nontrivial if $\operatorname{supp}(\mathcal{C}) \neq \varnothing$ (equivalently, the coloring is not all red). In that case, notice that 
- the support is closed under unions and intersections: since if $f\left(T_{1}\right) f\left(T_{2}\right) \neq 0$ then necessarily both $f\left(T_{1} \cap T_{2}\right)$ and $f\left(T_{1} \cup T_{2}\right)$ are nonzero; and 
- the support is obviously upwards closed. 
Thus, the support must take the form 
$$ \operatorname{supp}(\mathcal{C})=[X, S] \stackrel{\text { def }}{=}\{T \mid X \subseteq T \subseteq S\} $$
for some set $X$ (for example by letting $X$ be the minimal (by size) element of the support). Say $\mathcal{C}$ has full support if $X=\varnothing$ (equivalently, $\varnothing$ is blue). 

## Lemma 
For a given $n$ and $B \subseteq\{1, \ldots, n\}$, there is exactly one $n$-coloring with full support in which the singletons colored blue are exactly those in $B$. Therefore there are exactly $2^{n}$ $n$-colorings with full support. 

$$ f(T)=2^{|T \cap B|} $$
which satisfies the condition by Inclusion-Exclusion. To see this extension is unique, note that $f(\{b\})$ is determined for each $b$ and we can then determine $f(T)$ inductively on $|T|$; hence there is at most one way to complete a coloring of the singletons, which completes the proof. 

For a general nontrivial $n$-coloring $\mathcal{C}$, note that if $\operatorname{supp}(\mathcal{C})=[X, S]$, then we can think of it as an $(n-|X|)$-coloring with full support. For $|X|=k$, there are $\binom{n}{k}$ possible choices of $X \subseteq S$. Adding back in the trivial coloring, the final answer is 
$$ 1+\sum_{k=0}^{n}\binom{n}{k} 2^{k}=1+3^{n} $$ 
Remark. To be more explicit, the possible nontrivial colorings are exactly described by specifying two sets $X$ and $Y$ with $X \subseteq Y$, and coloring blue only the sets $T$ with $X \subseteq T \subseteq Y$. In particular, one deduces that in a working coloring, $f(T)$ is always either zero or a power of two. If one manages to notice this while working on the problem, it is quite helpful for motivating the solution, as it leads one to suspect that the working colorings have good structure.