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

Revision as of 13: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 (Problems • Answer Key • Resources)
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

@@ Line 10: / Line 10: @@
 How many different complementary three-card sets are there?
+__TOC__
 == 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
 <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>
 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>

Page

Toolbox

Search