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
,
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 colorings.