Difference between revisions of "1997 AIME Problems/Problem 10"

(category)
(solutions, (2) revised version of me@home's)
Line 10: Line 10:
 
How many different complementary three-card sets are there?
 
How many different complementary three-card sets are there?
  
 +
__TOC__
 
== Solution ==
 
== Solution ==
 +
=== Solution 1 ===
 +
*'''Case 1''': All three attributes are the same. This is impossible since sets contain distinct cards.
 +
*'''Case 2''': Two of the three attributes are the same. There are <math>{3\choose 2}</math> ways to pick the two attributes in question. Then there are <math>3</math> ways to pick the value of the first attribute, <math>3</math> ways to pick the value of the second attribute, and <math>1</math> way to arrange the positions of the third attribute, giving us <math>{3\choose 2} \cdot 3 \cdot 3 = 27</math> ways.
 +
*'''Case 3''': One of the three attributes are the same. There are <math>{3\choose 1}</math> ways to pick the one attribute in question, and then <math>3</math> ways to pick the value of that attribute. Then there are <math>3!</math> ways to arrange the positions of the next two attributes, giving us <math>{3\choose 1} \cdot 3 \cdot 3! = 54</math> ways.
 +
*'''Case 4''': None of the three attributes are the same. We fix the order of the first attribute, and then there are <math>3!</math> ways to pick the ordering of the second attribute and <math>3!</math> ways to pick the ordering of the third attribute. This gives us <math>(3!)^2 = 36</math> ways.
 +
 +
Adding the cases up, we get <math>27 + 54 + 36 = \boxed{117}</math>.
 +
 +
=== Solution 2 ===
 +
Let's say we have picked two cards. We now compare their attributes to decide how we can pick the third card to make a complement set. For each of the three attributes, should the two values be the same we have one option - choose a card with the same value for that attribute. Furthermore, should the two be different there is only one option- choose the only value that is remaining. In this way, every two card pick corresponds to exactly one set, for a total of <math>\binom{27}{2} = 27*13 = 351</math> possibilities. Note, however, that each set is generated by <math>{3\choose 2} = 3</math> pairs, so we've overcounted by a multiple of 3 and the answer is <math>\frac{351}{3} = \boxed{117}</math>.
 +
 +
=== Solution 3 ===
 
We call these three types of complementary sets <math>A,B,C</math> respectively. What we are trying to find is
 
We call these three types of complementary sets <math>A,B,C</math> respectively. What we are trying to find is
  
 
<cmath>n(A\cup B\cup C)</cmath>
 
<cmath>n(A\cup B\cup C)</cmath>
  
We know this is equivalent to
+
By [[Principle of Inclusion-Exclusion]], this is equivalent to
  
 
<cmath>n(A)+n(B)+n(C)-n(A\cap B)-n(B\cap C)-n(A\cap C)+n(A\cap B \cap C)</cmath>
 
<cmath>n(A)+n(B)+n(C)-n(A\cap B)-n(B\cap C)-n(A\cap C)+n(A\cap B \cap C)</cmath>
  
 
Now, <math>n(A)=\binom{9}{3}+9^3=813</math>. Obviously, <math>n(B)</math> and <math>n(C)</math> are the same. Thus, we have
 
Now, <math>n(A)=\binom{9}{3}+9^3=813</math>. Obviously, <math>n(B)</math> and <math>n(C)</math> are the same. Thus, we have
 
  
 
<cmath>2439-n(A\cap B)-n(B\cap C)-n(A\cap C)+n(A\cap B \cap C)</cmath>
 
<cmath>2439-n(A\cap B)-n(B\cap C)-n(A\cap C)+n(A\cap B \cap C)</cmath>

Revision as of 14:07, 22 November 2007

Problem

Every card in a deck has a picture of one shape - circle, square, or triangle, which is painted in one of the three colors - red, blue, or green. Furthermore, each color is applied in one of three shades - light, medium, or dark. The deck has 27 cards, with every shape-color-shade combination represented. A set of three cards from the deck is called complementary if all of the following statements are true:

i. Either each of the three cards has a different shape or all three of the card have the same shape.

ii. Either each of the three cards has a different color or all three of the cards have the same color.

iii. Either each of the three cards has a different shade or all three of the cards have the same shade.

How many different complementary three-card sets are there?

Solution

Solution 1

  • Case 1: All three attributes are the same. This is impossible since sets contain distinct cards.
  • Case 2: Two of the three attributes are the same. There are ${3\choose 2}$ ways to pick the two attributes in question. Then there are $3$ ways to pick the value of the first attribute, $3$ ways to pick the value of the second attribute, and $1$ way to arrange the positions of the third attribute, giving us ${3\choose 2} \cdot 3 \cdot 3 = 27$ ways.
  • Case 3: One of the three attributes are the same. There are ${3\choose 1}$ ways to pick the one attribute in question, and then $3$ ways to pick the value of that attribute. Then there are $3!$ ways to arrange the positions of the next two attributes, giving us ${3\choose 1} \cdot 3 \cdot 3! = 54$ ways.
  • Case 4: None of the three attributes are the same. We fix the order of the first attribute, and then there are $3!$ ways to pick the ordering of the second attribute and $3!$ ways to pick the ordering of the third attribute. This gives us $(3!)^2 = 36$ ways.

Adding the cases up, we get $27 + 54 + 36 = \boxed{117}$.

Solution 2

Let's say we have picked two cards. We now compare their attributes to decide how we can pick the third card to make a complement set. For each of the three attributes, should the two values be the same we have one option - choose a card with the same value for that attribute. Furthermore, should the two be different there is only one option- choose the only value that is remaining. In this way, every two card pick corresponds to exactly one set, for a total of $\binom{27}{2} = 27*13 = 351$ possibilities. Note, however, that each set is generated by ${3\choose 2} = 3$ pairs, so we've overcounted by a multiple of 3 and the answer is $\frac{351}{3} = \boxed{117}$.

Solution 3

We call these three types of complementary sets $A,B,C$ respectively. What we are trying to find is

\[n(A\cup B\cup C)\]

By Principle of Inclusion-Exclusion, this is equivalent to

\[n(A)+n(B)+n(C)-n(A\cap B)-n(B\cap C)-n(A\cap C)+n(A\cap B \cap C)\]

Now, $n(A)=\binom{9}{3}+9^3=813$. Obviously, $n(B)$ and $n(C)$ are the same. Thus, we have

\[2439-n(A\cap B)-n(B\cap C)-n(A\cap C)+n(A\cap B \cap C)\]

Template:Incomplete

1997 AIME (ProblemsAnswer KeyResources)
Preceded by
Problem 9
Followed by
Problem 11
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions
Invalid username
Login to AoPS