IMO

2015

Problem - 49

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).\]