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

(Solution 3)
Line 1: Line 1:
 
== Problem ==
 
== 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\}\,</math>, <math>\{b, c, d, e, f\}\,</math> represents the same selection as the pair <math>\{b, c, d, e, f\}\,</math>, <math>\{a, c\}\,</math>.
+
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 1 ==
 
== Solution 1 ==
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</math>, <math>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>
+
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>
  
 
== Solution 2 ==
 
== Solution 2 ==
  
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 Binomial Theorem. But the order of the sets doesn't matter, so we get <math>\dfrac{729 - 1}{2} + 1 = \boxed{365}</math>.
+
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 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 (way too bashy, non-clever)==
+
== Solution 4 (Extremely Bashy)==
  
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->y</math>, which implies that we pick x numbers for the first set which then the second set can have y numbers.
+
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:
 
Clearly:
<cmath>0->6</cmath>
+
<cmath>\begin{align*}
<cmath>1->5/6</cmath>
+
0&\rightarrow6 \
<cmath>2->4/5/6</cmath>
+
1&\rightarrow5\mid6 \
<cmath>3->3/4/5/6</cmath>
+
2&\rightarrow4\mid5\mid6 \
<cmath>4->2/3/4/5/6</cmath>
+
3&\rightarrow3\mid4\mid5\mid6 \
<cmath>5->1/2/3/4/5/6</cmath>
+
4&\rightarrow2\mid3\mid4\mid5\mid6 \
<cmath>6->0/1/2/3/4/5/6</cmath>
+
5&\rightarrow1\mid2\mid3\mid4\mid5\mid6 \
 +
6&\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*}
 +
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*}</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.
  
However notice that many of the cases are double counted as direction does not matter, e.g. <math>2->4 = 4->2</math>. Get rid of those cases so we are just left with:
+
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.
<cmath>0->6</cmath>
 
<cmath>1->5/6</cmath>
 
<cmath>2->4/5/6</cmath>
 
<cmath>3->3/4/5/6</cmath>
 
<cmath>4->4/5/6</cmath>
 
<cmath>5->5/6</cmath>
 
<cmath>6->6</cmath>
 
  
Now we start computing, <math>0->6</math> is just <math>1</math> case, <math>1->5/6</math> is just <math>\binom{6}{1}*2</math>, <math>2->4/5/6</math> is just <math>\binom{6}{2}*2^2</math>, and <math>3->3/4/5/6</math> is just <math>\binom{6}{3}*2^3</math> (If you have trouble understanding this, write down the six letters and then try to understand what <math>x->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.
+
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).
  
One quick thing though. We have a double counted case with the <math>3->3</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.
+
Summing case by case, we have <math>1+12+60+150+120+21+1 = \boxed{365}.</math>
 
 
For computing <math>4->4/5/6</math>, we use the same process as before. We have <math>\binom{6}{4}*(3+4+1)</math> (Note, the <math>3</math> comes from <math>\frac{\binom{4}{2}}{2}</math>), and for <math>5->5/6</math> we have <math>\binom{6}{5}*(\frac{5}{2}+1)</math>, and then for <math>6->6</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>
 
  
 
Disclaimer: This is a terrible solution, it should only be done as practice for casework bashing and never should be done on a real AIME.
 
Disclaimer: This is a terrible solution, it should only be done as practice for casework bashing and never should be done on a real AIME.

Revision as of 01:26, 2 September 2021

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

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}.$

Solution 2

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 Binomial Theorem. But the order of the sets doesn't matter, so we get $\dfrac{729 - 1}{2} + 1 = \boxed{365}.$

Solution 4 (Extremely Bashy)

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}.$

Disclaimer: This is a terrible solution, it should only be done as practice for casework bashing and never should be done on a real AIME.

See also

1993 AIME (ProblemsAnswer KeyResources)
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png