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

Revision as of 11:35, 10 August 2020

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 $\varnothing$ , $\cap$ denotes intersection, and $\cup$ denotes union. Let $S_n=\{n\}$ are one-element subsets.

Let $m_{c_k}=\dbinom{m}{k} = \frac{m!}{k!(m-k)!}$ denote m choose k.

(Case I) $f(\varnothing)=1$ . Then for distinct m and k, $f(S_m \cup S_k)=f(S_m)f(S_k)$ , meaning only if $S_m$ and $S_k$ are both blue is their union blue. Namely $C(S_m \cup S_k)=C(S_m)C(S_k).$

Similarly, for distinct $m,n,k$ , $f(S_m \cup S_k \cup Sn)=f(S_m \cup S_k)f(S_n)$ , $C(S_m \cup S_k \cup S_n)=C(S_m)C(S_k)C(S_n)$ . This procedure of determination continues to $S$ . Therefore, if $T=\{a_1,a_2, \cdots a_k\}$ , then $C(T)=C(S_{a_1})C(S_{a_2}) \cdots C(S_{a_k})$ . 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) $\text{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$ , a contradiction, or (II.1.2) all subsets has $C(T)=0$ , which is easily confirmed to satisfy the condition $f(T_1)f(T_2)=f(T_1 \cap T_2)f(T_1 \cup T_2)$ . There is one coloring in this case.

(Case II.2) Core = a subset of 1 element. WLOG, $C(S_1)=1$ . Then $f(S_1)=1$ , and subsets containing element 1 may be colored Blue. $f(S_1 \cup S_m)f(S_1\cup S_n)=f(S_1 \cup S_m \cup S_n)$ , namely $C(S_1 \cup S_m \cup S_n)=C(S_m \cup S_1)C(S_n \cup S_1)$ . Now S_1 functions as the $\varnothing$ in case I, with $n-1$ elements to combine into a base of $n-1$ two-element sets, and all the other subsets are determined. There are $2^{n-1}$ colorings for each choice of core. However, there are nC1 = n such cores. Hence altogether there are $n2^{n-1}$ colorings in this case.

(Case II.3) Core = a subset of 2 elements. WLOG, let $C(S_1 \cup S_2)=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.

$\dots$

(Case II.n+1) Core = S. Then $C(S)=1$ , with all other subsets $C(T)=0$ , there is $1=\dbinom{n}{n}2^0$

Combining all the cases, we have $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}$ colorings.

@@ Line 1: / Line 1: @@
-WOLG, let the circle be the unit circle centered at the origin, A=(1,0) P=(1-a,b), Q=(1-a,-b), where (1-a)^2+b^2=1. Let angle <XAB=A, which is an acute angle, tanA=t, then X=(1-a,at).
+==Problem==
+Let <math>S = \{1, 2, ..., n\}</math>, where <math>n \ge 1</math>. Each of the <math>2^n</math> subsets of <math>S</math> is to be colored red or blue. (The subset itself is assigned a color and not its individual elements.) For any set <math>T \subseteq S</math>, we then write <math>f(T)</math> for the number of subsets of T that are blue.
-Angle <BOS=2A, S=(-cos2A,sin2A).
+Determine the number of colorings that satisfy the following condition: for any subsets <math>T_1</math> and <math>T_2</math> of <math>S</math>, <cmath>f(T_1)f(T_2) = f(T_1 \cup T_2)f(T_1 \cap T_2).</cmath>
-Let M=(u,v), then T=(2u+cos2A, 2v-sin2A)
-The condition TX perpendicular to AX yields (2v-sin2A-at)/(2u+cos2A+a-1)=cotA.     (E1)
+===Solution===
-Use identities (cosA)^2=1/(1+t^2),  cos2A=2(cosA)^2-1= 2/(1+t^2) -1, sin2A=2sinAcosA=2t^2/(1+t^2), we obtain 2vt-at^2=2u+a.   (E1')
+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{ where } C(T)=1</math>.
-The condition that T is on the circle yields (2u+cos2A)^2+ (2v-sin2A)^2=1, namely vsin2A-ucos2A=u^2+v^2.   (E2)
+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.
-M is the mid-point on the hypotenuse of triangle STX, hence MS=MX, yielding (u+cos2A)^2+(v-sin2A)^2=(u+a-1)^2+(v-at)^2.   (E3)
+Let <math>m_{c_k}=\dbinom{m}{k} = \frac{m!}{k!(m-k)!}</math> denote m choose k.
-Expand (E3), using (E2) to replace 2(vsin2A-ucos2A) with 2(u^2+v^2), and using (E1') to replace a(-2vt+at^2) with -a(2u+a), and we obtain
-u^2-u-a+v^2=0, namely (u-1/2)^2+v^2=a+1/4, which is a circle centered at (1/2,0) with radius r=sqrt(a+1/4).
+(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 <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.)  <math>f(\varnothing)=0</math>.
+(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. 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, 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>
+(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.

Page

Toolbox

Search

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

Revision as of 11:35, 10 August 2020

Problem

Solution