Difference between revisions of "1993 AIME Problems/Problem 8"

Latest revision as of 13:09, 12 January 2024

Problem

Let $S\,$ be a set with six elements. In how many different ways can one select two not necessarily distinct subsets of $S\,$ so that the union of the two subsets is $S\,$ ? The order of selection does not matter; for example, the pair of subsets $\{a, c\},\{b, c, d, e, f\}$ represents the same selection as the pair $\{b, c, d, e, f\},\{a, c\}.$

Solution 1 (Overcounting)

Call the two subsets $m$ and $n.$ For each of the elements in $S,$ we can assign it to either $m,n,$ or both. This gives us $3^6$ possible methods of selection. However, because the order of the subsets does not matter, each possible selection is double counted, except the case where both $m$ and $n$ contain all $6$ elements of $S.$ So our final answer is then $\frac {3^6 - 1}{2} + 1 = \boxed{365}.$

Note: because we can order selections $A$ and $B$ in two ways, but since order does not matter in the problem, we should only count them once, ie we need to divide by two. We first need to subtract one for the count $3^6-1$ because there is one case in which $A$ and $B$ are identical and so while the rest of the “different” cases are counted twice, this one was only counted once so we should subtract one from the total count, divide by two, and add back that distinct one case. Or we could just add one, making all of the problem’s different cases counted twice, and divide it all by two, which is $\frac{3^6+1}{2}=365.$

Solution 2 (Overcounting)

Given one of ${6 \choose k}$ subsets with $k$ elements, the other also has $2^k$ possibilities; this is because it must contain all of the "missing" $n - k$ elements and thus has a choice over the remaining $k.$ We want $\sum_{k = 0}^6 {6 \choose k}2^k = (2 + 1)^6 = 729$ by the Binomial Theorem. But the order of the sets doesn't matter, so we get $\dfrac{729 - 1}{2} + 1 = \boxed{365}.$

Solution 3 (Recursion)

For all nonnegative integers $n,$ let $n$ be the number of elements in $S,$ and $f(n)$ be the number of unordered pairs $\{A,B\}$ of subsets of $S$ for which $A\cup B=S.$ We wish to find $f(6).$

Without the loss of generality, let the elements of $S$ be $1,2,\ldots,n.$ Based on the value of $n,$ we construct the following table: $\begin{array}{c|c|c} & & \\ [-2.5ex] \boldsymbol{n} & \textbf{Unordered Pairs }\boldsymbol{\{A,B\}}\textbf{ of subsets of }\boldsymbol{S}\textbf{ for which }\boldsymbol{A\cup B=S} & \boldsymbol{f(n)} \\ [0.5ex] \hline & & \\ [-2ex] 0 & \{\varnothing,\varnothing\} & 1 \\ 1 & \{\{1\},\{1\}\}, \ \{\{1\},\varnothing\} & 2 \\ 2 & \color{red}\{\{1,2\},\{1,2\}\}\color{black}, \ \color{green}\{\{1,2\},\{1\}\}\color{black}, \ \color{blue}\{\{1,2\},\{2\}\}\color{black}, \ \color{cyan}\{\{1,2\},\varnothing\}\color{black}, \ \color{magenta}\{\{1\},\{2\}\} & 5 \\ 3 & \color{red}\{\{1,2,3\},\{1,2,3\}\}\color{black}, \ \color{red}\{\{1,2,3\},\{1,2\}\}\color{black}, \ \color{green}\{\{1,2,3\},\{1,3\}\}\color{black}, \ \color{green}\{\{1,2,3\},\{1\}\}\color{black}, \ \color{green}\{\{1,2\},\{1,3\}\}\color{black}, & 14 \\ & \color{blue}\{\{1,2,3\},\{2,3\}\}\color{black}, \ \color{blue}\{\{1,2,3\},\{2\}\}\color{black}, \ \color{blue}\{\{1,2\},\{2,3\}\}\color{black}, \ \color{cyan}\{\{1,2,3\},\{3\}\}\color{black}, \ \color{cyan}\{\{1,2,3\},\varnothing\}\color{black}, \ \color{cyan}\{\{1,2\},\{3\}\}\color{black}, & \\ & \color{magenta}\{\{1,3\},\{2,3\}\}\color{black}, \ \color{magenta}\{\{1,3\},\{2\}\}\color{black}, \ \color{magenta}\{\{1\},\{2,3\}\} & \\ \vdots & \vdots & \vdots \end{array}$ Note that for all $n\geq1,$ each unordered pair of the $(n-1)$ -element set contributes three unordered pairs to the $n$ -element set, as the element $n$ can be added to either or both of the subsets. The only exception is that the unordered pair of identical subsets of the $(n-1)$ -element set, namely $\{\{1,2,\ldots,n-1\},\{1,2,\ldots,n-1\}\},$ only contributes two unordered pairs to the $n$ -element set. The table above shows this relationship between the $2$ -element set and the $3$ -element set.

Together, the recursive formula for $f(n)$ is $f(n) = \begin{cases} 1 & \mathrm{if} \ n=0 \\ 3f(n-1)-1 & \mathrm{if} \ n\geq1 \end{cases}.$ Two solutions follow from here:

Solution 3.1 (Recursive Formula)

We evaluate $f(6)$ recursively: $\begin{alignat*}{6} f(0)&=1, \\ f(1)&=3f(0)-1&&=2, \\ f(2)&=3f(1)-1&&=5, \\ f(3)&=3f(2)-1&&=14, \\ f(4)&=3f(3)-1&&=41, \\ f(5)&=3f(4)-1&&=122, \\ f(6)&=3f(5)-1&&=\boxed{365}. \end{alignat*}$ ~MRENTHUSIASM

Solution 3.2 (Explicit Formula)

For all $n\geq1,$ we have $\begin{align*} f(n) &= 3f(n-1)-1 \\ &= 3\left(3f(n-2)-1\right)-1 \\ &= 3^2f(n-2)-3-1 \\ &= 3^2\left(3f(n-3)-1\right)-3-1 \\ &= 3^3f(n-3)-3^2-3-1 \\ & \ \vdots \\ &= 3^nf(0)-3^{n-1}-3^{n-2}-3^{n-3}-\cdots-1 \\ &= 3^n-\left(3^{n-1}+3^{n-2}+3^{n-3}+\cdots+1\right) \\ &= 3^n-\frac{3^n-1}{2} \\ &= \frac{3^n+1}{2} \\ &= \frac{3^n-1}{2}+1, \end{align*}$ which resembles the result in Solutions 1 and 2. The answer is $f(6)=\boxed{365}.$

As $f(0)=1,$ note that $f(n)=\frac{3^n-1}{2}+1$ holds for $n=0$ too. Therefore, this formula is true for all nonnegative integers $n.$

~MRENTHUSIASM

Solution 4 (Casework)

We can perform casework based on the number of overlapping elements. If no elements overlap, there is $\binom60=1$ way to choose the overlapping elements, and $2^{6-0}$ ways to distribute the remaining elements--each element can go in one subset or the other. We must also divide by $2$ because the order of the subsets does not matter. Proceeding similarly for the other cases, our sum is $\dbinom{6}0 \cdot 2^5+\dbinom{6}1 \cdot 2^4+\cdots +\dbinom{6}4 \cdot 2+\dbinom{6}5 \cdot 1+\dbinom{6}6 \cdot 1.$ (Note that we have to be especially careful with the last case, as it does not follow the pattern of the other cases.) Adding these up gives a total of $\boxed{365}.$

~vaporwave

~MrThinker (LaTeX improvements)

Solution 5 (Bash)

If we wanted to, we could use casework, being very careful not to double count cases. Let's first figure out what cases we need to look at. The notation I will be using is $x\rightarrow y,$ which implies that we pick $x$ numbers for the first set which then the second set can have $y$ numbers.

Clearly: $\begin{align*} 0&\rightarrow6 \\ 1&\rightarrow5\mid6 \\ 2&\rightarrow4\mid5\mid6 \\ 3&\rightarrow3\mid4\mid5\mid6 \\ 4&\rightarrow2\mid3\mid4\mid5\mid6 \\ 5&\rightarrow1\mid2\mid3\mid4\mid5\mid6 \\ 6&\rightarrow0\mid1\mid2\mid3\mid4\mid5\mid6 \end{align*}$ However notice that many of the cases are double counted as direction does not matter, e.g. $2\rightarrow4$ is the same as $4\rightarrow2.$ Get rid of those cases so we are just left with: $\begin{align*} 0&\rightarrow6 \\ 1&\rightarrow5\mid6 \\ 2&\rightarrow4\mid5\mid6 \\ 3&\rightarrow3\mid4\mid5\mid6 \\ 4&\rightarrow4\mid5\mid6 \\ 5&\rightarrow5\mid6 \\ 6&\rightarrow6 \end{align*}$ Now we start computing, $0\rightarrow6$ is just $1$ case, $1\rightarrow5\mid6$ is just $\binom{6}{1}\cdot2$ cases, $2\rightarrow4\mid5\mid6$ is just $\binom{6}{2}\cdot2^2$ cases, and $3\rightarrow3\mid4\mid5\mid6$ is just $\binom{6}{3}\cdot2^3$ cases (If you have trouble understanding this, write down the six letters and then try to understand what $x\rightarrow y$ really means.). Now what you can do is continue on this same pattern like Solution 2 does, and then use simple symmetry to figure out the double counted cases. However, the purpose of this solution is to bash out the double counted cases, so we will do exactly that.

One quick thing though. We have a double counted case with the $3\rightarrow3,$ as choosing ABC and DEF is the same thing as choosing DEF and then ABC. There are $\frac{\binom{6}{3}}{2} = 10$ cases of this.

For computing $4\rightarrow4\mid5\mid6,$ we use the same process as before. We have $\binom{6}{4}\cdot(3+4+1)$ (Note, the $3$ comes from $\frac{\binom{4}{2}}{2}$ ), and for $5\rightarrow5\mid6$ we have $\binom{6}{5}\cdot\left(\frac{5}{2}+1\right),$ and then for $6\rightarrow6$ we just have $\binom{6}{6}$ (there is no double counted case since ABCDEF, ABCDEF is only counted once).

Summing case by case, we have $1+12+60+150+120+21+1 = \boxed{365}.$

~Tost (Solution)

~MRENTHUSIASM (Reformatting)

@@ Line 1: / Line 1: @@
 == Problem ==
+Let <math>S\,</math> be a set with six elements. In how many different ways can one select two not necessarily distinct subsets of <math>S\,</math> so that the union of the two subsets is <math>S\,</math>?  The order of selection does not matter; for example, the pair of subsets <math>\{a, c\},\{b, c, d, e, f\}</math> represents the same selection as the pair <math>\{b, c, d, e, f\},\{a, c\}.</math>
-== Solution ==
+== Solution 1 (Overcounting) ==
+Call the two subsets <math>m</math> and <math>n.</math> For each of the elements in <math>S,</math> we can assign it to either <math>m,n,</math> or both. This gives us <math>3^6</math> possible methods of selection. However, because the order of the subsets does not matter, each possible selection is double counted, except the case where both <math>m</math> and <math>n</math> contain all <math>6</math> elements of <math>S.</math> So our final answer is then <math>\frac {3^6 - 1}{2} + 1 = \boxed{365}.</math>
+Note: because we can order selections <math>A</math> and <math>B</math> in two ways, but since order does not matter in the problem, we should only count them once, ie we need to divide by two. We first need to subtract one for the count <math>3^6-1</math> because there is one case in which <math>A</math> and <math>B</math> are identical and so while the rest of the “different” cases are counted twice, this one was only counted once so we should subtract one from the total count, divide by two, and add back that distinct one case. Or we could just add one, making all of the problem’s different cases counted twice, and divide it all by two, which is <math>\frac{3^6+1}{2}=365.</math>
+== Solution 2 (Overcounting) ==
+Given one of <math>{6 \choose k}</math> subsets with <math>k</math> elements, the other also has <math>2^k</math> possibilities; this is because it must contain all of the "missing" <math>n - k</math> elements and thus has a choice over the remaining <math>k.</math> We want <math>\sum_{k = 0}^6 {6 \choose k}2^k = (2 + 1)^6 = 729</math> by the Binomial Theorem. But the order of the sets doesn't matter, so we get <math>\dfrac{729 - 1}{2} + 1 = \boxed{365}.</math>
+== Solution 3 (Recursion) ==
+For all nonnegative integers <math>n,</math> let <math>n</math> be the number of elements in <math>S,</math> and <math>f(n)</math> be the number of unordered pairs <math>\{A,B\}</math> of subsets of <math>S</math> for which <math>A\cup B=S.</math> We wish to find <math>f(6).</math>
+Without the loss of generality, let the elements of <math>S</math> be <math>1,2,\ldots,n.</math> Based on the value of <math>n,</math> we construct the following table:
+<cmath>\begin{array}{c|c|c}
+& & \\ [-2.5ex]
+\boldsymbol{n} & \textbf{Unordered Pairs }\boldsymbol{\{A,B\}}\textbf{ of subsets of }\boldsymbol{S}\textbf{ for which }\boldsymbol{A\cup B=S} & \boldsymbol{f(n)} \\ [0.5ex]
+\hline
+& & \\ [-2ex]
+& \{\varnothing,\varnothing\} & 1 \\
+& \{\{1\},\{1\}\}, \ \{\{1\},\varnothing\} & 2 \\
+& \color{red}\{\{1,2\},\{1,2\}\}\color{black}, \ \color{green}\{\{1,2\},\{1\}\}\color{black}, \ \color{blue}\{\{1,2\},\{2\}\}\color{black}, \ \color{cyan}\{\{1,2\},\varnothing\}\color{black}, \ \color{magenta}\{\{1\},\{2\}\} & 5 \\
+& \color{red}\{\{1,2,3\},\{1,2,3\}\}\color{black}, \ \color{red}\{\{1,2,3\},\{1,2\}\}\color{black}, \ \color{green}\{\{1,2,3\},\{1,3\}\}\color{black}, \ \color{green}\{\{1,2,3\},\{1\}\}\color{black}, \ \color{green}\{\{1,2\},\{1,3\}\}\color{black}, & 14 \\
+& \color{blue}\{\{1,2,3\},\{2,3\}\}\color{black}, \ \color{blue}\{\{1,2,3\},\{2\}\}\color{black}, \ \color{blue}\{\{1,2\},\{2,3\}\}\color{black}, \ \color{cyan}\{\{1,2,3\},\{3\}\}\color{black}, \ \color{cyan}\{\{1,2,3\},\varnothing\}\color{black}, \ \color{cyan}\{\{1,2\},\{3\}\}\color{black}, & \\
+& \color{magenta}\{\{1,3\},\{2,3\}\}\color{black}, \ \color{magenta}\{\{1,3\},\{2\}\}\color{black}, \ \color{magenta}\{\{1\},\{2,3\}\} & \\
+\vdots & \vdots & \vdots
+\end{array}</cmath>
+Note that for all <math>n\geq1,</math> each unordered pair of the <math>(n-1)</math>-element set contributes three unordered pairs to the <math>n</math>-element set, as the element <math>n</math> can be added to either or both of the subsets. The only exception is that the unordered pair of identical subsets of the <math>(n-1)</math>-element set, namely <math>\{\{1,2,\ldots,n-1\},\{1,2,\ldots,n-1\}\},</math> only contributes two unordered pairs to the <math>n</math>-element set. The table above shows this relationship between the <math>2</math>-element set and the <math>3</math>-element set.
+Together, the recursive formula for <math>f(n)</math> is
+<cmath>f(n) = \begin{cases}
+& \mathrm{if} \ n=0 \\
+f(n-1)-1 & \mathrm{if} \ n\geq1
+\end{cases}.</cmath>
+Two solutions follow from here:
+=== Solution 3.1 (Recursive Formula) ===
+We evaluate <math>f(6)</math> recursively:
+<cmath>\begin{alignat*}{6}
+f(0)&=1, \\
+f(1)&=3f(0)-1&&=2, \\
+f(2)&=3f(1)-1&&=5, \\
+f(3)&=3f(2)-1&&=14, \\
+f(4)&=3f(3)-1&&=41, \\
+f(5)&=3f(4)-1&&=122, \\
+f(6)&=3f(5)-1&&=\boxed{365}.
+\end{alignat*}</cmath>
+~MRENTHUSIASM
+=== Solution 3.2 (Explicit Formula) ===
+For all <math>n\geq1,</math> we have
+<cmath>\begin{align*}
+f(n) &= 3f(n-1)-1 \\
+&= 3\left(3f(n-2)-1\right)-1 \\
+&= 3^2f(n-2)-3-1 \\
+&= 3^2\left(3f(n-3)-1\right)-3-1 \\
+&= 3^3f(n-3)-3^2-3-1 \\
+& \ \vdots \\
+&= 3^nf(0)-3^{n-1}-3^{n-2}-3^{n-3}-\cdots-1 \\
+&= 3^n-\left(3^{n-1}+3^{n-2}+3^{n-3}+\cdots+1\right) \\
+&= 3^n-\frac{3^n-1}{2} \\
+&= \frac{3^n+1}{2} \\
+&= \frac{3^n-1}{2}+1,
+\end{align*}</cmath>
+which resembles the result in Solutions 1 and 2. The answer is <math>f(6)=\boxed{365}.</math>
+As <math>f(0)=1,</math> note that <cmath>f(n)=\frac{3^n-1}{2}+1</cmath> holds for <math>n=0</math> too. Therefore, this formula is true for all nonnegative integers <math>n.</math>
+~MRENTHUSIASM
+== Solution 4 (Casework) ==
+We can perform casework based on the number of overlapping elements. If no elements overlap, there is <math>\binom60=1</math> way to choose the overlapping elements, and <math>2^{6-0}</math> ways to distribute the remaining elements--each element can go in one subset or the other. We must also divide by <math>2</math> because the order of the subsets does not matter. Proceeding similarly for the other cases, our sum is <cmath>\dbinom{6}0 \cdot 2^5+\dbinom{6}1 \cdot 2^4+\cdots +\dbinom{6}4 \cdot 2+\dbinom{6}5 \cdot 1+\dbinom{6}6 \cdot 1.</cmath>
+(Note that we have to be especially careful with the last case, as it does not follow the pattern of the other cases.) Adding these up gives a total of <math>\boxed{365}.</math>
+~vaporwave
+~MrThinker (LaTeX improvements)
+==Solution 5 (Bash)==
+If we wanted to, we could use casework, being very careful not to double count cases. Let's first figure out what cases we need to look at. The notation I will be using is <math>x\rightarrow y,</math> which implies that we pick <math>x</math> numbers for the first set which then the second set can have <math>y</math> numbers.
+Clearly:
+<cmath>\begin{align*}
+&\rightarrow6 \\
+&\rightarrow5\mid6 \\
+&\rightarrow4\mid5\mid6 \\
+&\rightarrow3\mid4\mid5\mid6 \\
+&\rightarrow2\mid3\mid4\mid5\mid6 \\
+&\rightarrow1\mid2\mid3\mid4\mid5\mid6 \\
+&\rightarrow0\mid1\mid2\mid3\mid4\mid5\mid6
+\end{align*}</cmath>
+However notice that many of the cases are double counted as direction does not matter, e.g. <math>2\rightarrow4</math> is the same as <math>4\rightarrow2.</math> Get rid of those cases so we are just left with:
+<cmath>\begin{align*}
+&\rightarrow6 \\
+&\rightarrow5\mid6 \\
+&\rightarrow4\mid5\mid6 \\
+&\rightarrow3\mid4\mid5\mid6 \\
+&\rightarrow4\mid5\mid6 \\
+&\rightarrow5\mid6 \\
+&\rightarrow6
+\end{align*}</cmath>
+Now we start computing, <math>0\rightarrow6</math> is just <math>1</math> case, <math>1\rightarrow5\mid6</math> is just <math>\binom{6}{1}\cdot2</math> cases, <math>2\rightarrow4\mid5\mid6</math> is just <math>\binom{6}{2}\cdot2^2</math> cases, and <math>3\rightarrow3\mid4\mid5\mid6</math> is just <math>\binom{6}{3}\cdot2^3</math> cases (If you have trouble understanding this, write down the six letters and then try to understand what <math>x\rightarrow y</math> really means.). Now what you can do is continue on this same pattern like Solution 2 does, and then use simple symmetry to figure out the double counted cases. However, the purpose of this solution is to bash out the double counted cases, so we will do exactly that.
+One quick thing though. We have a double counted case with the <math>3\rightarrow3,</math> as choosing ABC and DEF is the same thing as choosing DEF and then ABC. There are <math>\frac{\binom{6}{3}}{2} = 10</math> cases of this.
+For computing <math>4\rightarrow4\mid5\mid6,</math> we use the same process as before. We have <math>\binom{6}{4}\cdot(3+4+1)</math> (Note, the <math>3</math> comes from <math>\frac{\binom{4}{2}}{2}</math>), and for <math>5\rightarrow5\mid6</math> we have <math>\binom{6}{5}\cdot\left(\frac{5}{2}+1\right),</math> and then for <math>6\rightarrow6</math> we just have <math>\binom{6}{6}</math> (there is no double counted case since ABCDEF, ABCDEF is only counted once).
+Summing case by case, we have <math>1+12+60+150+120+21+1 = \boxed{365}.</math>
+~Tost (Solution)
+~MRENTHUSIASM (Reformatting)
 == See also ==
-* [[1993 AIME Problems]]
+{{AIME box|year=1993|num-b=7|num-a=9}}
+{{MAA Notice}}

1993 AIME (Problems • Answer Key • Resources)
Preceded by Problem 7	Followed by Problem 9
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search