Difference between revisions of "2015 USAMO Problems/Problem 3"
(→Solution) |
Shridhar278 (talk | contribs) m (→Solution) |
||
(25 intermediate revisions by 4 users not shown) | |||
Line 6: | Line 6: | ||
===Solution=== | ===Solution=== | ||
Define function: <math>C(T)=1</math> if the set T is colored blue, and <math>C(T)=0</math> if <math>T</math> is colored red. | Define function: <math>C(T)=1</math> if the set T is colored blue, and <math>C(T)=0</math> if <math>T</math> is colored red. | ||
− | Define the <math>\text{Core} =\text{intersection of all} T \text{ | + | Define the <math>\text{Core} =\text{intersection of all } T \text{ where } C(T)=1</math>. |
− | The empty set is denoted as | + | The empty set is denoted as <math>\varnothing</math>, <math>\cap</math> denotes intersection, and <math>\cup</math> denotes union. Let <math>S_n=\{n\}</math> are one-element subsets. |
− | |||
− | Let | + | Let <math>m_{c_k}=\dbinom{m}{k} = \frac{m!}{k!(m-k)!}</math> denote m choose k. |
− | (Case I) <math>f(\ | + | (Case I) <math>f(\varnothing)=1</math>. Then for distinct m and k, <math>f(S_m \cup S_k)=f(S_m)f(S_k)</math>, meaning only if <math>S_m</math> and <math>S_k</math> are both blue is their union blue. Namely <math>C(S_m \cup S_k)=C(S_m)C(S_k).</math> |
− | Similarly, for distinct m,n,k, f( | + | Similarly, for distinct <math>m,n,k</math>, <math>f(S_m \cup S_k \cup Sn)=f(S_m \cup S_k)f(S_n)</math>, <math>C(S_m \cup S_k \cup S_n)=C(S_m)C(S_k)C(S_n)</math>. This procedure of determination continues to <math>S</math>. Therefore, if <math>T=\{a_1,a_2, \cdots a_k\}</math>, then <math>C(T)=C(S_{a_1})C(S_{a_2}) \cdots C(S_{a_k})</math>. All colorings thus determined by the free colors chosen for subsets of one single elements satisfy the condition. There are <math>2^n</math> colorings in this case. |
− | (Case II.) f( | + | (Case II.) <math>f(\varnothing)=0</math>. |
− | (Case II.1) Core= | + | (Case II.1) <math>\text{Core}=\varnothing</math>. Then either (II.1.1) there exist two nonintersecting subsets A and B, <math>C(A)=C(B)=1</math>, but f<math>(A)f(B)=0</math>, a contradiction, or (II.1.2) all subsets has <math>C(T)=0</math>, which is easily confirmed to satisfy the condition <math>f(T_1)f(T_2)=f(T_1 \cap T_2)f(T_1 \cup T_2)</math>. There is one coloring in this case. |
− | (Case II.2) Core= a subset of 1 element. | + | (Case II.2) Core = a subset of 1 element. WLOG, <math>C(S_1)=1</math>. Then <math>f(S_1)=1</math>, and subsets containing element 1 may be colored blue. <math>f(S_1 \cup S_m)f(S_1\cup S_n)=f(S_1 \cup S_m \cup S_n)</math>, namely <math>C(S_1 \cup S_m \cup S_n)=C(S_m \cup S_1)C(S_n \cup S_1)</math>. Now S_1 functions as the <math>\varnothing</math> in case I, with <math>n-1</math> elements to combine into a base of <math>n-1</math> two-element sets, and all the other subsets are determined. There are <math>2^{n-1}</math> colorings for each choice of core. However, there are nC1 = n such cores. Hence altogether there are <math>n2^{n-1}</math> colorings in this case. |
− | |||
− | (Case II.3) Core = a subset of 2 elements. WLOG, C( | + | (Case II.3) Core = a subset of 2 elements. WLOG, let <math>C(S_1 \cup S_2)=1</math>. Only subsets containing the core may be colored blue. With the same reasoning as in the preceding case, there are <math>(nC2)2^{n-2}</math> colorings. |
− | + | <math>\dots</math> | |
− | Combining all the cases, <math>1+[ | + | (Case II.n+1) Core = S. Then <math>C(S)=1</math>, with all other subsets <math>C(T)=0</math>, there is <math>1=\dbinom{n}{n}2^0</math> |
+ | |||
+ | Combining all the cases, we have <math>1+\left[2^n+\dbinom{n}{1}2^{n-1}+\dbinom{n}{2}2^{n-2}+ \cdots + \dbinom{n}{n}2^0\right]=\boxed{1+3^n}</math> colorings. sponsored by ALLEN |
Latest revision as of 04:55, 14 April 2023
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. sponsored by ALLEN