Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2015 USAMO Problems/Problem 3"

m (→‎Solution)
m (→‎Solution)
Line 11: Line 11:
 
Let Sn={n} are one-element subsets.
 
Let Sn={n} are one-element subsets.
  
−
Let mCk denote m choose k = m!/(k!(m-k)!)
+
Let mCk denote m choose k = <math>\frac{m!}{k!(m-k)!}</math>
  
  
 
(Case I) <math>f(\null)=1</math>. Then for distinct m and k, <math>f(Sm+Sk)=f(Sm)f(Sk)</math>, meaning only if Sm and Sk are both blue is their union blue. Namely <math>C(Sm+Sk)=C(Sm)C(Sk).</math>
 
(Case I) <math>f(\null)=1</math>. Then for distinct m and k, <math>f(Sm+Sk)=f(Sm)f(Sk)</math>, meaning only if Sm and Sk are both blue is their union blue. Namely <math>C(Sm+Sk)=C(Sm)C(Sk).</math>
  
−
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.  
+
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 colorings in this case.  
  
−
(Case II.)  f(<math>\emptyset</math>)=0.  
+
(Case II.)  f(<math>\varnothing</math>)=0.  
  
−
(Case II.1)  Core=<math>\emptyset</math>. 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.1)  Core=<math>\varnothing</math>. 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.  
 
(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.  
−
  <math>f(S1+Sm)f(S1+Sn)=f(S1+Sm+Sn)</math>, 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.
+
  <math>f(S1+Sm)f(S1+Sn)=f(S1+Sm+Sn)</math>, namely C(S1+Sm+Sn)=C(Sm+S1)C(Sn+S1). Now S1 functions as the <math>\varnothing</math> 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.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.

Revision as of 20:09, 16 January 2017

Problem

Let $S = \{1, 2, ..., n\}$, where $n \ge 1$. Each of the $2^n$ subsets of $S$ is to be colored red or blue. (The subset itself is assigned a color and not its individual elements.) For any set $T \subseteq S$, we then write $f(T)$ for the number of subsets of T that are blue.

Determine the number of colorings that satisfy the following condition: for any subsets $T_1$ and $T_2$ of $S$, \[f(T_1)f(T_2) = f(T_1 \cup T_2)f(T_1 \cap T_2).\]

Solution

Define function: $C(T)=1$ if the set T is colored blue, and $C(T)=0$ if $T$ is colored red. Define the $\text{Core} =\text{intersection of all } T \text{ where } C(T)=1$.

The empty set is denoted as $\emptyset$, ^ 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 = $\frac{m!}{k!(m-k)!}$


(Case I) $f(\null)=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 colorings in this case.

(Case II.) f($\varnothing$)=0.

(Case II.1) Core=$\varnothing$. 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 $\varnothing$ 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+(\dbinom{n}{1})2^{n-1}+(\dbinom{n}{2})2^{n-2}+\cdot \cdot \cdot +(\dbinom{n}{n})2^0]=1+3^n$ is the total number of colorings satisfying the given condition.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_3&oldid=82349"