Before I post a solution, I'll comment something about an initial impression: The outputs of $f$ are integers between $0$ and $2^n$, and have an additive structure. The condition in the problem is of the form $ab = cd$. This was huge motivation for me to actually do the problem during lunch, because it suggests that the possible values of $f$ ought to be very limited -- otherwise, it seems like would have to do nontrivial number theory! For example, it would be kind of surprising if $f(T) = 7$ was possible, since from that you can get statements about divisibility on the other side of the equation. I think that's the biggest give-away this problem is not as terrifying as it looks. In fact, if combo was my best subject and geo my worst (which is the opposite of true for me), I definitely would have tried #3 before #2.

Alright, solution: For an $n$-coloring $\mathcal C$ (by which we mean a coloring of the subsets of $\{1,\dots,n\}$), define the support of $\mathcal C$ as \[ \operatorname{supp}(\mathcal C) = \left\{ T \mid f(T) \neq 0 \right\}. \]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(T_1) f(T_2) \neq 0$ then necessarily both $f(T_1 \cap T_2)$ and $f(T_1 \cup T_2) \ne 0$ are nonzero; and the support is obviously upwards closed. Thus, the support must take the form \[ \operatorname{supp}(\mathcal C) = [X,S] \overset{\text{def}}{=} \left\{ T \mid X \subseteq T \subseteq S \right\} \]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,\dots,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. Proof. To see there is at least one coloring, color only the subsets of $B$ blue. In that case \[ f(T) = 2^{\left\lvert T \cap B \right\rvert} \]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 $\left\lvert T \right\rvert$; hence there is at most one way to complete a coloring of the singletons, which completes the proof. $\blacksquare$ 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-\left\lvert X \right\rvert)$-coloring with full support. For $\left\lvert X \right\rvert = k$, there are $\binom nk$ possible choices of $X \subseteq S$. Adding back in the trivial coloring, the final answer is \[ 1 + \sum_{k=0}^n \binom nk 2^k = \boxed{1 + 3^n}. \]

Is it wise to post the problems so early? Considering it's not even 2pm in Hawaii yet? Perhaps we should wait a bit longer. I'm surprised they didn't lock the forums today.

What do you mean? All testing is done.

gauss202 wrote: Is it wise to post the problems so early? Considering it's not even 2pm in Hawaii yet? Perhaps we should wait a bit longer. I'm surprised they didn't lock the forums today. devenware gave an OK in another thread; otherwise I would have waited until 5:30PM ET as in past years. Note that the contest is given at the same time everywhere in the world.

I see. I still might advocate for everyone waiting a bit longer just to be sure everyone is done, but if AoPS says okay, then so be it. Carry on then.

it is taken at the same time all over the world.

I managed to figure out the answer $1+3^n$ with small values of $n$, but my "proof" was almost completely off (basically bs). Perhaps 1 point?

Just wondering, if you leave out the $\binom{n}{k}$ in the summation but prove everything else (also write the 1 in the summation but don't have it added in the final answer - so I ended up with $1 + \sum_{k=0}{n}2^k = 2^{k+1}$ oops), how many points would be deducted? Also v_Enhance I believe you have a typo in your sum - the $2^n$ should be $2^k$. Nice concise solution though!

Sketch of my solution (it was 11 pages oops): We claim that every coloring is either trivial or some interval $[R_1,R_2]$. It isn't hard to show that the conditions are satisfied if this is the case. Otherwise, let $R_1$ be the minimal blue set-if there's another minimal blue set we get a contradiction, so all blue sets are supersets of $R_1$. Now we can WLOG assume that $R_1$ is the empty set. Let $A$ be the set of singletons which are blue, $B$ be the set which are not. We take $R_2=A$; to prove that the blue ones are the ones we claim are blue, we just use induction on the size of sets, adding in either something in $A$ or something in $B$ each time.

Sketch of mine (I may post full solution later): Let $A$ be the smallest blue set. (ignoring the all red case, we'll add one later) Then it's easy to show that all blue sets are supersets of $A$ by contradiction (otherwise, if $T$ were a blue set that is not a superset of $A$, you get $f(T\cap A) > 0$. Now you have: \[\prod_{i \in S \backslash A}f(A \cup \{i\}) = f(S)\] by the given condition, induction, and the fact that $f(A)=1$. So now you use the fact that $f(A \cup \{i\})$ is always either 1 or 2, and let $B=\{i: f(A \cup \{i\}) = 2\}$. You get that $f(B)=2^{|B|}$ using a similar idea to the large product above. It follows pretty quickly that the set of blue sets is the set of all $T$ such that $A \subseteq T \subseteq A \cup B$. It is easy to show that this always works, so the answer is just the number of ways to pick disjoint $A$ and $B$, which is $3^n$. So you add back in the one for the all red case to get $\boxed{3^n+1}$

I got till the point that T is a superset of A. But then I messed up due to a mis-proof (I showed that all solutions must be of the kind A, AUB, AUBUC... where A, B, C... are disjoint) Also I handled the cases when the null set is blue and all the subsets are red separately (and correctly). Can I expect a 1-2 one this one?

v_Enhance wrote: gauss202 wrote: Is it wise to post the problems so early? Considering it's not even 2pm in Hawaii yet? Perhaps we should wait a bit longer. I'm surprised they didn't lock the forums today. devenware gave an OK in another thread; otherwise I would have waited until 5:30PM ET as in past years. Note that the contest is given at the same time everywhere in the world. When I think about that, it'll be extremely painful for someone living in, say, China, for they have to not sleep and do the problems if they want to participate. Fortunately it's USAMO, so not many people will be outside of US.

If $\varnothing$ is blue then we have $f(T_1)f(T_2) = f(T_1 \cup T_2)$. If $T_1$ is a single element subset and is red, then $f(T_2) = f(T_1 \cup T_2)$. This means that any subset containing that element $T_1$ is red. Otherwise, if $T_1$ is blue, then $f(T_2) \cdot 2 = f(T_1 \cup T_2)$ and so that means every subset of $T_2$ + $T_1$. So we can build the coloring of all subsets based on the elemental colorings. It is pre-determined by the coloring so $2^n$ possibles here. If $\varnothing$ is red then that means for any two disjoint sets $f(T_1)f(T_2) = 0$. This means that for any two disjoint subsets, at least one of them is red. We again look at elemental subsets. Suppose we have an element $v$ that was blue. Then consider any set $S$ that doesn't contain $v$. This tells us that $f(S) = 0$ which means every single subset not containing $v$ is red. In fact, if we have a set that is blue, then any set not containing that set must be red. Suppose we have a blue set $B$ where $|B|$ is minimal. We know that Any set disjoint with $B$ is red. Every subset of $B$ is red by minimality. Suppose there is a set $R$ such that $B \cap R \neq \varnothing$, and $B$ is not a subset of $R$. Then that means $f(B \cap R) = 0$ and so that implies that all subsets of $R$ are red. We can treat supersets of $B$ like $B$ is the null set in the case where the null set is blue. This gives us $$ 2^n + 1 + \sum_{k = 1}^n \binom{n}{k} 2^{n-k} = 3^n+1$$

fclvbfm934 wrote: If $\varnothing$ is blue then we have $f(T_1)f(T_2) = f(T_1 \cup T_2)$. If $T_1$ is a single element subset and is red, then $f(T_2) = f(T_1 \cup T_2)$. This means that any subset containing that element $T_1$ is red. Otherwise, if $T_1$ is blue, then $f(T_2) \cdot 2 = f(T_1 \cup T_2)$ and so that means every subset of $T_2$ + $T_1$. So we can build the coloring of all subsets based on the elemental colorings. It is pre-determined by the coloring so $2^n$ possibles here. If $\varnothing$ is red then that means for any two disjoint sets $f(T_1)f(T_2) = 0$. This means that for any two disjoint subsets, at least one of them is red. We again look at elemental subsets. Suppose we have an element $v$ that was blue. Then consider any set $S$ that doesn't contain $v$. This tells us that $f(S) = 0$ which means every single subset not containing $v$ is red. In fact, if we have a set that is blue, then any set not containing that set must be red. Suppose we have a blue set $B$ where $|B|$ is minimal. We know that Any set disjoint with $B$ is red. Every subset of $B$ is red by minimality. Suppose there is a set $R$ such that $B \cap R \neq \varnothing$, and $B$ is not a subset of $R$. Then that means $f(B \cap R) = 0$ and so that implies that all subsets of $R$ are red. Any subset that is a superset of $B$ can be anything we want. This gives us $$ 2^n + 1 + \sum_{k = 1}^n \binom{n}{k} 2^{n-k} = 3^n+1$$ I did almost this but due to mis-proof showed that all blue sets have to be supersets of smaller blue sets (in the second last step). Any idea how much I can expect?

raxu wrote: v_Enhance wrote: gauss202 wrote: Is it wise to post the problems so early? Considering it's not even 2pm in Hawaii yet? Perhaps we should wait a bit longer. I'm surprised they didn't lock the forums today. devenware gave an OK in another thread; otherwise I would have waited until 5:30PM ET as in past years. Note that the contest is given at the same time everywhere in the world. When I think about that, it'll be extremely painful for someone living in, say, China, for they have to not sleep and do the problems if they want to participate. Fortunately it's USAMO, so not many people will be outside of US. You don't need to tell me that, I was in Taiwan during the USAMO last year 12:30AM-5AM... those were a fun two nights.

@v_Enhance You mean mornings

You can consult Evan's USAMO contest analysis at http://www.mit.edu/~evanchen/olympiad.html or actually http://www.mit.edu/~evanchen/handouts/USAMO2014/USAMO2014.pdf (but the first link has other stuff too).

Has nobody mentioned the typo "colered" in the OP? Good catch! Fixed -- v_E

I hate this problem. The answer is $3^n+1$, obtained by caseworking on the smallest (rigid!) blue set. First, note that there is 1 way for there to be no blue sets. Then, if the empty subset is blue, we show that in this case there are $2^n$ ways. Indeed, based on the singleton sets, by taking disjoint sets into the equation we can uniquely determine $f(T_1/cup T_2)=f(T_1)f(T_2)$. Now, if $f(\emptyset)=0$, note that out of all singleton sets, there is at most 1 set that is blue, because otherwise you could take two disjoint singleton blue sets and their intersection makes RHS 0 but LHS nonzero. Case 1: 1 singleton subset is blue; let this subset/element be $A$. Then all subsets B without A must be red, since $f(B)f(A)=f(B\cup A)f(\emptyset)=0$. Now, we look at the rest of the subsets with A: we can ignore the element A (since all $f$s in the equation have A irregardless); this reduces into the case where $f(\emptyset)=1$, whence there are $n2^{n-1}$, where the n is from n options for singleton. Case 2: All singleton subsets are red. This has the same characteristics as the empty set being red, since all 1-element subsets of this type are red; so we are reduced to the same casework as in 1, but with $\binom n2$ ways to form 2-element subsets, and $2^{n-2}$ ways to color the rest. Continuing analogously, our answer is then $n2^{n-1}+\binom n2 2^{n-2}+\dots+\binom nn 2^0=(2+1)^n=3^n$ ways, added with no blue sets makes our claimed answer. $\blacksquare$

We will show that the answer is $3^n+1.$ We claim that, aside from the all-red coloring, there is a bijection between the number of valid colorings and the number of ways to choose one subset $X$ and color the subsets $Y$ satisfying $X \subseteq Y$ and $|Y|=|X|+1$ in any way. To do this, first let $X$ be the blue subset with the least number of elements. Suppose there exists a blue subset $X'$ with $X \nsubseteq X'.$ Then, clearly $f(X)f(X') \ge 1,$ but $|X \cap X'|<|X|,$ so $f(X \cup X')f(X \cap X')=0,$ contradiction. Therefore all blue subsets must contain $X.$ Next, we state the following lemma: If $a_1,a_2,\dots,a_k$ are integers satisfying $1 \le a_i \le n$ and $a_i \notin X$ for each $1 \le i \le k,$ then we have $f(X \cup \{a_1,a_2,\dots,a_k\})=2^K,$ where $K$ is the number of subsets $X \cup \{a_i\}$ that are blue. Proof: We have \[f(X \cup \{a_1,a_2,\dots,a_k\})f(X)^{k-1}=f(X \cup \{a_1,a_2,\dots,a_{k-1}\})f(X \cup \{a_k\})f(X)^{k-2}=\dots=f(X \cup \{a_1\})f(X \cup \{a_2\}) \cdots f(X \cup \{a_k\}),\]and $f(X)=1,$ and we can see that $f(X \cup \{a_i\})=2$ if $X \cup \{a_i\}$ is blue, and it is $1$ otherwise, proving the lemma. Thus, from this lemma, it is not hard to see that by arbitrarily coloring the subsets $Y$ described above, we will get at most one valid coloring of all subsets. We can also easily show that our coloring will indeed be valid as follows. Suppose we have two subsets $T_1,T_2.$ If at most one of $T_1,T_2$ is a superset of $X,$ then we get $f(T_1)f(T_2)=f(T_1 \cup T_2)f(T_1 \cap T_2)=0.$ Now suppose that $T_1=X \cup S_1$ and $T_2=X \cup S_2$ with $X$ disjoint to both $S_1,S_2.$ Denote by $g(S)$ the number of subsets $X \cup \{a\}$ that are blue, across all $a \in S.$ Notice that any element $a$ appears the same number of times across $S$ and $S'$ combined as it does across $S \cup S'$ and $S \cap S'$ combined, where $S,S'$ are any sets. Thus, we have \[f(T_1)f(T_2)=2^{g(S_1)+g(S_2)}=2^{g(S_1 \cup S_2)+g(S_1 \cap S_2)}=f(T_1 \cup T_2)f(T_1 \cap T_2),\]so our coloring will be valid. Therefore, our claim is proved. To finish, note that we can choose a subset $X$ of $\{1,2,\dots,n\}$ with size $n-k$ in $\binom{n}{k}$ ways, and we can color the $k$ subsets $Y$ in $2^k$ ways. Then we have $\sum_{k=0}^n 2^k \binom{n}{k}=(2+1)^n=3^n,$ and adding in the all-red coloring gives $3^n+1,$ as desired.

Assume that there exists a blue subset of $S$. Denote $P = \{p_1,p_2,\ldots p_k\}$ to be the a set of minimal length such that $P$ is blue (and therefore $f(P) > 0$). Clearly, $f(P) = 1$, or else a set with fewer elements will also be blue. Also know that given any set $T$ such that $P \not\in T$, we have that $f(P)f(T) = f(P \cup T)f(P \cap T) = 0$ since $|P \cup T| < |P| \Rightarrow$. Thus, we only need to consider the sets $T$ such that $P \in T$. Lemma. Denote $N = S \setminus P$. Fixing all the values of $f(P \cup \{n\})$ for all $n \in N$ will fix the values of all $f(T)$ for any $P \in T \in S$. Proof. Consider any $P \in T \in S$, such that $T \setminus P = X = \{x_1,x_2,\ldots,x_t\}$, where $t \geq 2$ (since we have defined all sets where $t = 1$). Then, notice that $$\prod\limits_{i=1}^{t} f(X \cup \{x_i\}) = f(X \cup \{x_1,x_2\}) \prod\limits_{i=3}^{t} f(X \cup \{x_i\}) = \ldots = f(X \cup \{x_1,x_2,\ldots,x_t\}) = f(T). $$ It is also easy to show that the fixing of all values of $f(S \cup \{n\})$ creates a valid solution (by casework on if $P \in T_1$ and if $P \in T_2$). Also note that $f(P \cup \{n\})$ can either be $1$ or $2$ since the only sets that could be blue are $P$ and $P \cup \{n\}$, and we know that $P$ is blue. Thus, for this set $P$ such that $|P| = k$, we have $2^{|N|} = 2^{|S|-k} = 2^{n-k}$ solutions. Finally, we just need to sum over all values of $P$, and then add $1$ in the case that there are no blue subset of $S$, so we wish to find $$1+\sum\limits_{P \in S} 2^{n-|P|} = 1+\sum\limits_{i=1}^{n} \binom{n}{i} 2^{n-i} = 1+3^n.$$

Case 1: $\emptyset$ is blue. Suppose we colour the singleton sets randomly. Claim: If we color the remaining sets such that a set is blue iff each of its elements' singleton sets is blue, this works, and is in fact the only coloring that works for that coloring of singleton sets. Proof: First we show that this works. (This is actually just straightforward computational checking.) Suppose we have two sets $T_1=\{x_1,x_2,\ldots,y_1,y_2,\ldots \}$ and $T_2=\{z_1,z_2,\ldots,y_1,y_2,\ldots \}$, with the $y$'s being common elements. Let $X,Y,Z$ be the number of blue $x$'s, $y$'s and $z$'s respectively. Then $f(T_1)f(T_2)=2^{X+Y}\cdot2^{Z+Y}=2^{X+Y+Z}\cdot2^Y=f(T_1 \cup T_2)f(T_1 \cap T_2)$. Now we prove that this has to be the case. We do strong induction on the size of the set. Suppose we have proven till size $m$. Suppose FTSOC some set $T$ of size $m+1$ is blue, but some elements' singletons $\{k_1\},\{k_2\} \ldots$ are red. Now split the set into $T_1=\{k_1,k_2,\ldots\}$ and $T_2$ (let it be of size $l$) which contains the remaining elements. Then $f(T_1)f(T_2)=f(T_2)=2^l$, because the only blue set of $f(T_1)$ is $\phi$, by inductive hypothesis (since none of its singleton elements are blue). However $f(T_1 \cup T_2)f(T_1 \cap T_2)=f(T)f(\emptyset)=f(T)=2^l+1$, since $T$ is also blue. Therefore we have a contradiction. The other direction also has a similar proof. So the number of colorings with $\emptyset$ blue is the number of ways to randomly colour the singletons, which is $2^n$. Case 2: $\emptyset$ is red. Let $m$ be the smallest subset size such that some subset $T_1$ of size $m$ is blue. Claim: $T_1$ is the only blue subset of size $m$. Proof: Assume FTSOC there is some other blue subset $T_2$ of size $m$. Then $(T_1\cup T_2)$ is red, since its size is $<m$. Therefore $f(T_1 \cup T_2)f(T_1 \cap T_2)$ is 0, but $f(T_1)f(T_2)$ is non-zero, contradiction. Note that in fact, all sets $T_2$ which do not contain $T_1$ must be red, because the product $f(T_1)f(T_2)$ needs to be zero since $f(T_1 \cap T_2)=0$, since it has size $<m$. Consider the sets of size $m+1$ of which $T_1$ is a subset. Call these sets 'sparkling'. Colour them randomly. Then colour the remaining sets as follows: A set is blue iff all its subsets containing $T_1$ are blue. I claim that this works, and that this is the only working coloring for this coloring of the sparkling sets. The proof for this is again by size contradictions. (Outline of proof: If some set is not behaving properly, then take two subsets such that their union is the badly behaved set, and their intersection is $T_1$. You will get contradictions. Checking that this works is again simple computation.) So to find the number of ways if $\emptyset$ is red, we color everything up till size $m-1$ red, then colour one set of size $m$ blue (and the others red), then randomly colour sets of size $m+1$, which contain the set of size $m$ that we picked. All other sets are colored according to the conditions and constraints stated earlier. The number of ways for this (for a particular $m$) is $n \choose m$$\cdot 2^{n-m}$. (Since there are $n-m$ sparkling sets.) We sum this across all $m$ (from 1 to $n$), and also add 1 for the case where all subsets are red (this obviously works since all products are 0). We also need to add $2^n$ (from the other case) to get the total sum. Now our total sum is $2^n+1+\Sigma_{m=1}^{n}$$n \choose m$$\cdot 2^{n-m} = 1+\Sigma_{m=0}^{n}$$n \choose m$$\cdot 2^{n-m}$. Note that this is $1+$ the number of ways to put $n$ objects into $3$ boxes, so the answer is $\boxed{1+3^n}$.

We claim that the answer is $\boxed{3^n+1}$ We have two cases. Case 1: $f(\emptyset) = 1$ We claim that all $f(T)$ are defined by the sets with size $1$. This is because we can inductively discover the sets of size $n$. For example choose subsets $T_1$ and $T_2$ such that $T_1 \cup T_2 = T$ and $T_1 \cap T_2 = \emptyset$ to discover that $f(T) = f(T_1) \cdot f(T_2)$. We can thus see that the answer for this case is $2^n$. Case 2: $f(\emptyset) = 1$ Let $x$ be the size of the smallest set such that $f(T) = 1$. Obviously we would have this equal to $1$. We claim that we cannot have two of the sets with size $x$ be blue. This is because if $f(T_1) = f(T_2) = 1$ as $x$ element sets then $f(T_1)\cdot f(T_2) = 0$ (because their intersection has size at most $x-1$). Now we consider that the size of $x$ can be anything in $[0, n]$ (or just not exist so we must add $1$). Notice this also includes case $1$. Thus our answer is \[1 + \sum_{k = 0}^{k = n} \binom{n}{k} 2^{n-k} = 3^n +1\]since this is just the binomial expansion of $(1+2)^n$. $\blacksquare$ quite nice, but extremely rigid

For any two subsets $A\subseteq B$ we color subsets $T$ blue iff $A\subseteq T\subseteq B$. Proof of Sufficiency: Call an element ``good'' if it is in $B$ but not in $A$. Let $T_1,T_2\in S$ and suppose that there are $a$ good elements in $T_1$ but not $T_2$. Define $b$ similarly. Then, suppose there are $x$ good elements in both $T_1$ and $T_2$. If either of $T_1$ or $T_2$ does not contain $A$, both sides of the assertion are zero so assume otherwise. Then, \[f(T_1)f(T_2)=2^{a+x}\cdot 2^{b+x}=2^{a+b+x}\cdot 2^{x}=f(T_1\cup T_2)f(T_1\cap T_2),\]as desired. Proof of Necessity: Let $S'$ be the set of blue subsets. Let $A$ be the subset in $S'$ with minimal size. Then, for $T\in S'$ we have \[1\le f(A)f(T)=f(A\cap T)f(A\cup T).\]If $A\nsubseteq T$ then $|A\cap T|<|A|$ and there exists a subset of $A\cap T$ that is blue as $f(A\cap T)>0$, which is a contradiction. Hence, $A\subseteq T$. Let $B$ be the subset in $S'$ with maximal size. Consider $T\in S'$. Suppose $f(B\setminus T)=b$, $f(T\setminus B)=t,$ $f(T\cap B)=x$. Then, \[(b+x)(t+x)=f(B)f(T)=f(B\cup T)f(B\cap T)=(b+t+x)x\]which gives $bt=0$ which means all blue subsets of $B$ are contained in $T$ or vice versa. Note $|T|\le |B|$ so if $B\subseteq T$ then $B=T$ ie $T\subseteq B$. Otherwise, $T\subseteq B$. Hence, all blue subsets $T$ satisfy $A\subseteq T\subseteq B$ for some $A\subseteq B$. If we have all red subsets, there is one coloring. If there is at least one blue subset, there are $3^n$ ways to choose $A$ and $B$ so our answer is $\boxed{3^n+1}$.

Answer: $3^n + 1$. We begin with the following claim: Claim: If $\emptyset$ is blue, then there are exactly $2^n$ possible colorings. Proof. Note that $f(\{x\})f(\{y\}) = f(\{\emptyset\})f(\{x, y\}) = f(\{x, y\})$, so $f(\{x, y\})$ is uniquely determined by $f(\{x\}),f(\{y\})$. Inducting it, we see that $f(\{a_1, a_2, \dots, a_k\})$ is uniquely determined by $f(\{a_1\}), f(\{a_2\}), \dots, f(\{a_n\})$. Therefore, $f(T_1)f(T_2) = f(T_1 \cap T_2)f(T_1 \cup T_2)$ holds. Conversely, if we put colors of $f(\{1\}), f(\{2\}), \dots, f(\{n\})$ arbitrarily, we get a coloring that satisfies the problem condition. Thus, the number of coloring is $2^n$. $\blacksquare$ If there isn't any blue subset, then there are exactly 1 such coloring, so we may assume there exists a blue set. Let $S$ be the minimal blue set, i.e $|S|$ is minimal and let $T$ be an arbitrary set such that $f(T) > 0$. If $S \not\subseteq T$, then $0 \neq f(S)f(T) = f(S \cap T)f(S \cup T)$, so $0 \neq f(S \cap T)$. Therefore, there exists a blue subset $H$ of $S \cap T$, so $|H| \le |S \cap T| < |S|$, contradicting the fact that $|S|$ is minimal. Hence, whenever $f(T) > 0$, $S \subseteq T$. Let $T_1, T_2$ be subsets of $\{1, 2, \dots,n\}$ that don't include $S$. Then note that $f(T_1)f(T_2) = 0 = f(T_1 \cap T_2) = f(T_1 \cap T_2)f(T_1 \cup T_2)$ and $f(T_1)f(T_2 \cup S) = 0 = f(T_1 \cap (T_2 \cup S))f(T_1 \cup (T_2 \cup S))$, so we only need to work on the subsets that are including $S$. Let $T_1, T_2 \subseteq \{1, 2, \dots, n\}\backslash S$. Then note that we only have to count the number of coloring that satisfies $f(T_1 \cup S)f(T_2 \cup S) = f(S \cup T_1 \cup T_2)f(S \cup (T_1 \cap T_2))$. If we erase $S$ from these subsets, then the problem reduces down to the case that original set is $\{1, 2, \dots, n\}\backslash S$ and $\emptyset$ is blue. Thus by claim, the number of such coloring is $2^{n - |S|}$. Hence the final answer is $1 + \sum_{k=0}^{n} 2^{n-k}\binom{n}{k} = 3^n + 1$, as needed. $\blacksquare$ Remark: At first, I worked on the cases $n = 1, 2, 3$ and realised the claim, but it took embarrasingly long time to prove, because I chose wrong approach to prove. I tried to prove the claim by using induction on $n$, which seems pretty tempting for me, but I couldn't prove it by induction. Then I somehow considered singleton sets and that was the time I proved the claim. Then somehow, I magically did the rest of the problems in 10 minutes, just considering the minimal set.

First we do the case where $\emptyset$ is blue. Note that all subsets are determined by what color the sets with only one element are. For example, if $1$ is blue and $2$ is red, then ${1,2}$ is red. Note that a subset is blue if and only if all the elements are blue. Thus, there are $2^n$ colorings for when the $\emptyset$ is blue, corresponding to what color each of the $n$ single element sets are. \newline Now, the case where the empty set is red. Obviously the all red case works. Now consider the blue set with the least elements. Let the smallest blue set have $t$ elements.There can obviously be no more blue sets with $t$ elements as $1 \cdot 1 \neq 0,$ or any sets that don't contain the smallest blue subset. Now, consider all subsets that have the smallest blue set as a subset. Then note that we can consider this as simply an $\emptyset$ is blue case where there are $n-t$ elements. Thus, our final answer is $$\sum_{t=0}{n}\binom{n}{t} 2^{n-t}+1=\boxed{3^n+1}$$.

We count $1$ for when all subsets are red. Now let $k$ be the minimal cardinality of a blue subset. Case 1: $k = 0$. Then the empty set is blue. For brevity call an element $x \in T$ blue if $\{ x \}$ is blue. Note that for any disjoint $A$ and $B$, we have $f(A \cup B) = f(A) f(B) \implies f(T) = \prod_{x \in T} f(\{x \})$ which is simply $2$ to the power of the number of blue elements in $T$. Call this result $(1)$. Claim 1: Any nonempty set $T \subseteq S$ is blue if and only if all of its elements are blue. Proof. We induct, the $|T| = 1$ case is self-evident. Assuming it is true up to $|T|$, consider an arbitrary $|U| = |T| + 1$. Suppose $U$ has $b$ blue elements. If $b = |U|$, by the inductive hypothesis all $2^b - 1$ proper subsets are blue. But $(1)$ implies there are $2^b$ in total, so $U$ is blue itself. On the other hand, if $U$ has at least one red element, it has $2^b$ proper subsets that are blue. So $(1)$ shows that $U$ is red. The above claim implies that the whole coloring is uniquely determined by one of $2^n$ colorings of the sets $\{1 \}, \{2 \}, \dots \{ n \}$, all can be verified to work for sufficiency. Case 2: $1 \le k \le n$. WLOG $\{1, 2, \dots, k \}$ is the smallest blue set. Then all of its proper subsets are red. Now since for disjoint $A$ and $B$, the product $f(A) f(B) = 0$, all subsets of $\{k + 1, k + 2, \dots, n \}$ are all red. Now consider all sets $(P \cup Q) \subseteq S$ where $P \subset \{1, 2, \dots, k \}$ and $Q \subseteq \{k + 1, k + 2, \dots, n \}$. Then \[ 0 = f(P) (\{1, 2, \dots, k \} \cup Q)= f(P \cup Q) f(\{1, 2, \dots, k \}) = f(P \cup Q) \implies P \cup Q \text{ is red.} \]The only sets left to assign a color are those of the form $\{1, 2, \dots, k \} \cup Q$. Let $\{1, 2, \dots, k \} = V$. This situation is virtually the same as Case 1, where instead of $\varnothing$, it is $V$, and instead of assigning colors to $\{1 \}, \{2 \}, \dots, \{n \}$ we are doing this on $V \cup \{k + 1 \}, V \cup \{k + 2 \}, \dots, V \cup \{ n \}$. There are $2^{n - k}$ ways to choose these colors. Now showing the constructions work is easily verifiable. Collectively the second case yields $\sum_{k = 1}^n \binom{n}{k} 2^{n - k}$. We have exhausted all cases, our final answer is therefore \[1 + 2^n + \sum_{k = 1}^n \binom{n}{k} 2^{n - k} = \boxed{3^n + 1}. \]

what the

New highest MOHS solve! We split this into cases. Call an element blue if the one element set consisting of that set is blue. If $\O$ is blue, then $f(\O) = 1$ and then for disjoint sets $T_1, T_2$ we have $f(T_1 \cup T_2) = f(T_1) f(T_2)$. Then I claim that coloring the one element sets $\{1 \}, \{ 2, \}, \dots \{ n \}$ uniquely determines the rest of the colorings, giving $2^n$ cases. If $T = \{ x_1, x_2, \dots x_n \}$ then $f(T) = \prod_i f(x_i)$. But $f(x_i)$ is $2$ iff $\{ x_i \}$ is blue. Therefore $$f(T) = 2^{\text{number of blue elements}}$$which is obviously determined by the one element subsets. Claim: $T$ is blue iff all of its elements are blue. Proof: We proceed using strong induction on the size of $T$. The single element case is obvious. Now if we have that $f(T) = 2^x$ for some integer $x$, we know we have exactly $x$ blue elements. If $x$ is the size of $T$, then $T$ is obviously blue. But if $x < |T|$, then we know by our inductive hypothesis that any subset of those $x$ elements is blue as well, giving us $2^x$ blue subsets. Therefore, $T$ cannot be blue because if it was then $f(T) \geq 2^x + 1$, contradiction.$ \blacksquare$ Therefore, if $\O$ is blue then we have $2^n$ cases. If $\O$ is red, then $f(\O) = 0$. Therefore, out of any two disjoint subsets one of them must have no blue subsets. Therefore, there must be exactly one blue element or no blue element. If there is exactly one blue element, WLOG $\{ 1 \}$. Then clearly $f(\text{all subsets with no 1}) = 0$. The key step here is that instead of the previous case with the single element subsets forming a basis, we have the double element subsets with $1$. Particularly, $\{1, 2 \}, \{ 1, 3 \}, \dots \{ 1, n \}$ determine all of the subsets that contain a $1$. To see why, notice that $f(\{ 1, x_1, x_2, \dots x_n\}) = \prod_i f(\{ 1, x_i\}) = 2^{\text{number of blue two element sets with one}}$. Then using the exact same induction as the previous case we note that $T$ is blue iff $f(T) = 2^{|T|-1}$, thus determining all subsets. This gives $n \cdot 2^{n-1}$, where the $n$ is from the WLOG earlier.

smallest blue subset, giving one trivial solution. Our answer is then $$1 + 2^n + \sum_{k=1}^n \binom{n}{k} \cdot 2^{n-k} = \boxed{3^n+1}$$by the binomial theorem.

Suppose that $\emptyset$ is blue. The key observation is that the number of colorings is fixed based on any coloring the sets $\{1\}, \ldots, \{n\}$, as we have $f(T) = 2^{\#(T)}$ for all $T \subseteq S$, where $\#(T)$ represents the number of elements in $S$ whose set is colored blue. Thus we have $2^n$ colorings in this case. We have one coloring if all elements are red. Otherwise, suppose $M$ is the blue set of minimal cardinality $|M| = k$. First notice that $M$ is be unique and only supersets of $M$ can also be colored blue by letting $T_1$ be $M$ and $T_2$ be any a set which violates these conditions. We have $\textstyle \binom nk$ ways to select $M$ with given cardinality, and now we're essentially left with coloring the subsets of $\{1,2,\ldots,n-k\}$ with $\emptyset$ blue, which we determined to have $2^{n-k}$ choices. Summing over $0 \leq k \leq n$ gives \[1 + \binom n0 \cdot 2^n + \ldots + \binom nn \cdot 2^0 = \boxed{3^n+1}. \quad \blacksquare\]

Let $S = \left\{ 1,2,\dots,n \right\}$, 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). \] The answer is $3^n + 1$. We split into cases on the empty set $\varnothing$. Case 1: $\varnothing$ is blue. Then, for disjoint $T_1$, $T_2 \subseteq S$, $f(T_1)f(T_2) = f(T_1 \cup T_2)$. We claim that each coloring is fixed by the $1$-element sets, and a set is blue iff all of its elements are. Hence, there are $2^n$ colorings in this case. The proof is by strong induction. Suppose that each $j$-element set is blue iff all of its elements are for each $1 \leq j \leq k$. We will show that the $k+1$-element sets satisfy this property too. Begin by freely choosing the $1$-element subsets, which establishes the trivial base case $k = 1$. Then, for each set of size $k+1$, partition it into two disjoint sets of size $k$ and $1$. WLOG, let's take $\{1, 2, \dots, k+1\} = \{1, 2, \dots, k\} \cup \{k+1\}$. We have \[ f(\{1, 2, \dots, k\})f(\{k+1\}) = f(\{1, 2, \dots, k+1\}). \] If $\{k+1\}$ is red, $f(\{1, 2, \dots, k\}) = f(\{1, 2, \dots, k+1\})$. But $\{1, 2, \dots, k\} \subset \{1, 2, \dots, k+1\}$, so this forces $\{1, 2, \dots, k+1\}$ to be red. If $\{k+1\}$ is blue, $2f(\{1, 2, \dots, k\}) = f(\{1, 2, \dots, k+1\})$. By the inductive hypothesis, each proper subset $T \subset \{1, 2, \dots, k\}$ is blue iff $T \cup \{k+1\}$ is. Along with $f(\{1, 2, \dots, k+1\}) = 2f(\{1, 2, \dots, k\})$, this implies $\{1, 2, \dots, k\}$ is blue iff $\{1, 2, \dots, k+1\}$ is. In turn, $\{1, 2, \dots, k+1\}$ is blue iff. all of its elements are by the hypothesis. This completes the inductive step. Now we verify all $2^n$ colorings work. Take a set $T = \{e_1, e_2, \dots, e_m\}$. By repeatedly applying $f(T_1)f(T_2) = f(T_1 \cup T_2)$, $f(T) = f(e_1)f(e_2)\dots f(e_m)$. Suppose it has $b$ blue elements; then $b$ of those terms are $2$ and the other $m-b$ are $1$. So $f(T) = 2^b$. Consequently, if $A$ has $x$ blue elements and $B$ has $y$ blue elements with $z$ elements of overlap (i.e. $A \cap B$ has $z$ blue elements, $A \cup B$ has $x + y - z$ blue elements), we get $2^x2^y = 2^z2^{x+y-z}$, which holds. Case 2: $\varnothing$ is red. Let $B$ be the blue set of minimal size. We claim it is unique. Indeed, if $B_1$ and $B_2$ are blue sets of minimal size $k$, then $f(B_1)f(B_2) \neq 0$. But $B_1 \cap B_2$ has size less than $k$, so all of its subsets (including itself) are red. Thus $f(B_1 \cap B_2) = 0$, contradiction. So there is a unique minimal blue set $B$ of size $k$. Additionally, we claim all sets $C$ with $B \subsetneq C$ are red. $f(B)f(C) = f(B \cap C)f(B \cup C) = 0$, since $|B \cap C| < |B|$. But $f(B) \neq 0$, so $f(C) = 0$. Thus, everything is fixed except the supersets of $B$. Observe the bijection between coloring the supersets of $B$ which are subsets of $S$ and coloring the subsets of $S \setminus B$. Formally, let $g(P) = f(B \cup P)$ for each subset $P$ of $S \setminus B$. Then, since $(B \cup P_1) \cup (B \cup P_2) = B \cup (P_1 \cup P_2)$ and $(B \cup P_1) \cap (B \cup P_2) = B \cup (P_1 \cap P_2)$, $g(P_1)g(P_2) = g(P_1 \cup P_2)g(P_1 \cap P_2).$ Also, $g(\varnothing) = f(B) = 1$. So this is equivalent to coloring the subsets of $S \setminus B$ according to the same restriction, with the empty set being blue: exactly the same as Case 1! Thus, since $|S \setminus B| = n-k$, there are $2^{n-k}$ such colorings. We quickly verify they all work: take sets $A_1$, $A_2 \subseteq S$. If one of $A_1$, $A_2$ is not a superset of $B$, $f(A_1)f(A_2) = 0$. Then $A_1 \cap A_2$ is also not a superset of $B$, so $f(A_1 \cap A_2) = 0$. If both $A_1$, $A_2$ are supersets of $B$, the condition holds by the bijection. Now each coloring in Case 2 can be determined by fixing $0 < k \leq n$, choosing $B$ to be one of the $\binom{n}{k} k$-element sets, and adding $2^{n-k}$ to the count. Note also that the all-red set trivially works, so this adds $1$. The count is \[\sum_{i = 1}^n 2^{n-i}\binom{n}{i} + 1 \]\[= \sum_{i = 1}^n 2^{n-i}\binom{n}{n-i} + 1 \]\[= \sum_{i = 0}^{n-1} 2^{i}\binom{n}{i} + 1 \]\[= 3^n - 2^n + 1. \] Combined with Case 1, this yields $3^n + 1$ total colorings.

We claim there are $3^n+1$ ways. For convenience, we will denote sets with uppercase letters and elements of $\{1,2,\dots ,n\}$ with lowercase ones. CASE 1: Assume $f(\emptyset)=0$, then $f(A)f(B)=f(A\cap B)$ for disjoint sets $A,B$. We claim $f(\{a_1,a_2,\dots a_k\})=2^l$, where $l$ is the number of elements $a_i$ such that $f(\{a_i\})=2$. It is clearly true for $k=1$, so suppose it is true for $a_1, a_2, \dots a_k$ and now $2^lf(\{a_{k+1}\})=f(\{a_1, a_2, \dots a_k\})f(\{a_{k+1}\})=f(\{a_1, a_2, \dots a_k, a_{k+1}\})$, so we're done by induction. Furthermore, for non-disjoint sequences $a_i, b_i$, suppose $l_1$ are the amount of elements that satisfy $f(x)=2$ and are shared between both sequences and $l_2, l_3$ are the ones which only appear in one of the sequences. Check that: $2^{2l_1+l_2+l_3}=f(\{a_1,a_2, \dots a_k\})f(\{b_1,b_2, \dots b_t\})=f(\{a_1,a_2, \dots a_k\} \cup \{b_1,b_2, \dots b_t\})f(\{a_1,a_2, \dots a_k\} \cap \{b_1,b_2, \dots b_t\}) = 2^{l_1+l_2}2^{l_1+l_3}=2^{2l_1+l_2+l_3}$. Consequently, after choosing $f(\{x\})$ for all $x$, the remaining of the sequence is forced, hence there're $2^n$ ways to do it. CASE 2: Let $f(\emptyset)=0$. First, we claim that there exists at most one element that satisfies $f(\{x\})=1$, since, if there were two, $1=f(\{x\})f(\{y\})=f(\{x,y\})f(\emptyset)=0$. Suppose that element $x$ does exist, then we prove by induction that $f(\{x,a_1,a_2, \dots a_k\})=\prod_{i=1}^kf(\{x,a_i\})$ with base case $f(\{x,a\})f(\{x,b\})=f(\{x,a,b\})$ clear. Suppose it is true for $f(\{x,a_1,a_2, \dots a_k\})=\prod_{i=1}^kf(\{x,a_i\})$ and now $f(\{x,a_1,a_2, \dots ,a_k,a_{k+1}\})=f(\{x,a_1,a_2, \dots ,a_k\})f(\{x,a_{k+1}\})=\prod_{i=1}^{k+1}f(\{x,a_i\})$. Also, if $x\not \in A$, then $f(A)=0$, for $f(A)f(\{x\})=f(A\cup \{x\})f(A\cap \{x\})=0$. Just check that this works for all sets by considering $B,C$ and $x\in A$ disjoint and so $\prod_{a\in A}f(x,a)^2\prod_{b\in B}f(x,b)\prod_{c\in C}f(x,c)=\prod_{i\in A or B}f(1,a)\prod_{j\in AorC}f(x,a)=f(A\cup B)f(A\cup C)=f(A\cup B\cup C)f(A)=\prod_{k\in AorBorC}f(x,k)\prod_{h\in A}f(x,h)=\prod_{a\in A}f(x,a)^2\prod_{b\in B}f(x,b)\prod_{c\in C}f(x,c)$ (if $x\not \in A$, then both terms will be 0). To sum up, we can choose an element $x$ to be the one that $f(\{x\})=1$, and we choose whether $\{x,y\}$ was blue or red for all $y$, remaining, so there're $n2^{n-1}$ ways to colour. CASE 3: Consider if there is no element such that $f(\{x\})=1$ and $f(\emptyset)=0$. Then we choose $A$ to be the set that satisfies $f(A)>0$ with minimal cardinality, then clearly $f(A)=1$. We'll call an element $y$ \textit{good} if $f(A\cup\{y\})2$ and \textit{bad} otherwise. We now prove by induction that $f(A\cup B)=2^k$ ($A,B$ disjoint), where $k$ is the amount of good elements with base case clear. Suppose $B$ only contains \textit{good} elements and $y$ be one, then $f(A\cup B)=2^{\mid B\mid}$ and so $f(A\cup B\cup \{y\})=f(A\cup B)f(A\cup \{y\})=2^{\mid B\mid +1}$, so all subsets containing only \textit{good} elements and $A$ will be blue. However, whenever there're no more \textit{good} elements, include \textit{bad} $x$ and so $f(A\cup C\cup \{x\})=f(A\cup C)f(A\cup \{x\})=f(A\cup C)$, so all sets containing $A, x$ are red. Finally, just check that if a certain subset $S$ doesn't include $A$, then all $f(S)=0$, which can be easily proved when supposing there exists one with minimal cardinality and so $f(S)F(A)=f(A\cup S)f(A\cap S)=0$, for $A\cap S$ has less cardinality than $S$. We can check this configuration always works by considering sets $S_1, S_2$ that contain $A$ (if not clearly 0=0), where $S_1=A\cup B\cup C_1\cup D_1$, $S_2=A\cup B\cup C_2\cup D_2$, where $B,C_i$ are the sets of shared and individual \textit{good} elements and $D_i$ are the remaining ones, hence $2^{\mid B\mid +\mid C_1\mid+\mid C_2\mid}2^{\mid B \mid}=f(S_1\cup S_2)f(S_1\cap S_2)=f(S_1)f(S_2)=2^{\mid B\mid+\mid C_1\mid}2^{\mid B\mid+\mid C_2\mid}$, so it always works. Therefore, we just have to choose the minimal blue set (if it exists, so we must add one in case every set is red) and decide whether $f(A\cup \{x\}=\{1,2\}$, therefore, there're $\sum_{i=2}^n\binom{n}{i}2^{n-i}+1=\sum_{i=0}^n\binom{n}{i}2^{n-i}+1-n2^{n-1}-2^n=3^n-2^n-n2^{n-1}+1$. Consequently, there're $2^n+n2^{n-1}+3^n-2^n-n2^{n-1}+1=3^n+1$.