2015 USAMO Problems/Problem 3

Problem

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).$

Solution

Define function: $C(T)=1$ if the set T is colored blue, and $C(T)=0$ if $T$ is colored red. Define the $\text{Core} =\text{intersection of all } T \text{ where } C(T)=1$ .

The empty set is denoted as $\varnothing$ , $\cap$ denotes intersection, and $\cup$ denotes union. T1<T2 means T1 is a subset of T2 but not =T2. Let $Sn={n}$ are one-element subsets.

Let mCk denote m choose k = $\frac{m!}{k!(m-k)!}$

(Case I) $f(\null)=1$ . Then for distinct m and k, $f(S_m \cup S_k)=f(S_m)f(S_k)$ , meaning only if $S_m$ and $S_k$ are both blue is their union blue. Namely $C(S_m \cup S_k)=C(S_m)C(S_k).$

Similarly, for distinct m,n,k, f(S_m \cup S_k \cup Sn)=f(S_m \cup S_k)f(S_n), C(S_m \cup S_k \cup S_n)=C(S_m)C(S_k)C(S_n). This procedure of determination continues to S. Therefore, if $T=\{a_1,a_2, \cdots a_k\}$ , then $C(T)=C(S_{a1})C(S_{a2}) \cdots C(S_{ak})$ . All colorings thus determined by the free colors chosen for subsets of one single elements satisfy the condition. There are $2^n$ colorings in this case.

(Case II.) $f(\varnothing)=0$ .

(Case II.1) $\text{Core}=\varnothing$ . Then either (II.1.1) there exist two nonintersecting subsets A and B, $C(A)=C(B)=1$ , but f $(A)f(B)=0$ which is a contradiction, or (II.1.2) all subsets has $C(T)=0$ , which is easily confirmed to satisfy the condition $f(T1)f(T2)=f(T1 \cap T2)f(T1 \cup T2)$ . There is one coloring in this case.

(Case II.2) Core = a subset of 1 element. WLOG, C(S1)=1. Then $f(S1)=1$ , and subsets containing element 1 may be colored Blue. $f(S1 \cup Sm)f(S1\cup Sn)=f(S1 \cup Sm \cup Sn)$ , namely $C(S1 \cup Sm \cup Sn)=C(Sm \cup S1)C(Sn \cup S1)$ . Now S1 functions as the $\varnothing$ in case I, with n-1 elements to combine into a base of n-1 2-element sets, and all the other subsets are determined. There are $2^(n-1)$ colorings for each choice of core. But there are nC1 = n such cores. Hence altogether there are $n2^{n-1}$ colorings in this case.

(Case II.3) Core = a subset of 2 elements. WLOG, $C(S1 \cup S2)=1$ . Only subsets containing the core may be colored Blue. With the same reasoning as in the preceding case, there are $(nC2)2^{n-2}$ colorings.

$\dots$

(Case II.n+1) Core = S. Then C(S)=1, with all other subsets $C(T)=0$ , there is $1=\dbinom{n}{n}2^0$

Combining all the cases, we have $1+\left[1+\dbinom{n}{1}2^{n-1}+\dbinom{n}{2}2^{n-2}+ \cdots + \dbinom{n}{n}2^0\right]=\boxed{1+3^n}$ colorings.

Page

Toolbox

Search

2015 USAMO Problems/Problem 3

Problem

Solution