# 2015 USAMO Problems/Problem 3

## Problem

Let , where . Each of the subsets of is to be colored red or blue. (The subset itself is assigned a color and not its individual elements.) For any set , we then write for the number of subsets of T that are blue.

Determine the number of colorings that satisfy the following condition: for any subsets and of ,

### Solution

Define function: if the set T is colored blue, and if is colored red. Define the .

The empty set is denoted as , denotes intersection, and denotes union. Let are one-element subsets.

Let denote m choose k.

(Case I) . Then for distinct m and k, , meaning only if and are both blue is their union blue. Namely

Similarly, for distinct , , . This procedure of determination continues to . Therefore, if , then . All colorings thus determined by the free colors chosen for subsets of one single elements satisfy the condition. There are colorings in this case.

(Case II.) .

(Case II.1) . Then either (II.1.1) there exist two nonintersecting subsets A and B, , but f, a contradiction, or (II.1.2) all subsets has , which is easily confirmed to satisfy the condition . There is one coloring in this case.

(Case II.2) Core = a subset of 1 element. WLOG, . Then , and subsets containing element 1 may be colored Blue. , namely . Now S_1 functions as the in case I, with elements to combine into a base of two-element sets, and all the other subsets are determined. There are colorings for each choice of core. However, there are nC1 = n such cores. Hence altogether there are colorings in this case.

(Case II.3) Core = a subset of 2 elements. WLOG, let . Only subsets containing the core may be colored blue. With the same reasoning as in the preceding case, there are colorings.

(Case II.n+1) Core = S. Then , with all other subsets , there is

Combining all the cases, we have colorings.