Difference between revisions of "2015 USAMO Problems/Problem 3"
Thomasihkim (talk | contribs) m (→Solution) |
Pwusinaisgod (talk | contribs) m (→Solution) |
||
| Line 20: | Line 20: | ||
f(S1+Sm)f(S1+Sn)=f(S1+Sm+Sn), namely C(S1+Sm+Sn)=C(Sm+S1)C(Sn+S1). Now S1 functions as the Nil 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) legit colorings for each choice of core. BUt there are nC1 (i.e. n choose 1) =n such cores. Hence altogether there are n2^(n-1) colorings in this case. | f(S1+Sm)f(S1+Sn)=f(S1+Sm+Sn), namely C(S1+Sm+Sn)=C(Sm+S1)C(Sn+S1). Now S1 functions as the Nil 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) legit colorings for each choice of core. BUt there are nC1 (i.e. n choose 1) =n such cores. Hence altogether there are n2^(n-1) colorings in this case. | ||
| − | (Case II.3) Core = a subset of 2 elements. | + | (Case II.3) Core = a subset of 2 elements. WLOG, C(S1+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. |
... (Case II.n+1) Core =S. Then C(S)=1, with all other subsets C(T)=0, there is 1=(nCn)2^0 | ... (Case II.n+1) Core =S. Then C(S)=1, with all other subsets C(T)=0, there is 1=(nCn)2^0 | ||
Combining all the cases, 1+[1+(nC1)2^(n-1)+(nC2)2^(n-2)+...+(nCn)2^0]=1+3^n is the total number of colorings satisfying the given condition. | Combining all the cases, 1+[1+(nC1)2^(n-1)+(nC2)2^(n-2)+...+(nCn)2^0]=1+3^n is the total number of colorings satisfying the given condition. | ||
Revision as of 18:32, 13 March 2016
Solution
Define function: 
if the set T is colored blue, and 
if 
is colored red.
Define the 
.
The empty set is denoted as Nil. ^ denotes intersection; + 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 = m!/(k!(m-k)!)
(Case I) f(Nil)=1. Then for distinct m and k, f(Sm+Sk)=f(Sm)f(Sk), meaning only if Sm and Sk are both blue is their union blue. Namely C(Sm+Sk)=C(Sm)C(Sk).
Similarly, for distinct m,n,k, f(Sm+Sk+Sn)=f(Sm+Sk)f(Sn), C(Sm+Sk+Sn)=C(Sm)C(Sk)C(Sn). This procedure of determination continues to S. Therefore, if T={a1,a2,...ak}, then C(T)=C(Sa1)C(Sa2)...C(Sak). All colorings thus determined by the free colors chosen for subsets of one single elements satisfy the condition. There are 2^n legit colorings in this case.
(Case II.) f(Nil)=0.
(Case II.1) Core=Nil. 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^T2)f(T1+T2). There is one legitimate coloring in this case.
(Case II.2) Core= a subset of 1 element. WOLG, C(S1)=1. Then f(S1)=1, and subsets containing element 1 may be colored Blue.
f(S1+Sm)f(S1+Sn)=f(S1+Sm+Sn), namely C(S1+Sm+Sn)=C(Sm+S1)C(Sn+S1). Now S1 functions as the Nil 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) legit colorings for each choice of core. BUt there are nC1 (i.e. n choose 1) =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+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.
... (Case II.n+1) Core =S. Then C(S)=1, with all other subsets C(T)=0, there is 1=(nCn)2^0
Combining all the cases, 1+[1+(nC1)2^(n-1)+(nC2)2^(n-2)+...+(nCn)2^0]=1+3^n is the total number of colorings satisfying the given condition.
