Difference between revisions of "2015 USAMO Problems/Problem 3"
(→Solution) |
(→Solution) |
||
| Line 9: | Line 9: | ||
The empty set is denoted as <math>\varnothing</math>, <math>\cap</math> denotes intersection, and <math>\cup</math> denotes union. <math>T_1<T_2</math> means <math>T_1</math> is a subset of <math>T_2</math> but is not equal to <math>T2</math>. | The empty set is denoted as <math>\varnothing</math>, <math>\cap</math> denotes intersection, and <math>\cup</math> denotes union. <math>T_1<T_2</math> means <math>T_1</math> is a subset of <math>T_2</math> but is not equal to <math>T2</math>. | ||
| − | Let <math> | + | Let <math>S_n=\{n\}</math> are one-element subsets. |
Let mCk denote m choose k = <math>\frac{m!}{k!(m-k)!}</math> | Let mCk denote m choose k = <math>\frac{m!}{k!(m-k)!}</math> | ||
Revision as of 20:38, 16 January 2017
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 , ![\[f(T_1)f(T_2) = f(T_1 \cup T_2)f(T_1 \cap T_2).\]](http://latex.artofproblemsolving.com/1/e/5/1e5371f0639b2a8ed04d6b74c7401b1d36264652.png)
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. 
means is a subset of but is not equal to 
.
Let 
are one-element subsets.
Let mCk 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 S. 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
which is 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, C(S1)=1. Then 
, and subsets containing element 1 may be colored Blue. 
, namely 
. Now S1 functions as the 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 
colorings for each choice of core. But there are nC1 = n such cores. Hence altogether there are 
colorings in this case.
(Case II.3) Core = a subset of 2 elements. WLOG, 
. 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 C(S)=1, with all other subsets , there is 
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}$](http://latex.artofproblemsolving.com/3/5/3/3533e236d9ac148ffd179d9ba5c44c8bc05f46b2.png)
colorings.
