Maths Olympiad Prep

Library / /82 of 82

Combinatorics Difficulty 5.8 AIME, harder Prove it United States

Problem:

In the game of set, each card has four attributes, each of which takes on one of three values. A set deck consists of one card for each of the 8181 possible four-tuples of attributes. Given a collection of 33 cards, call an attribute good for that collection if the three cards either all take on the same value of that attribute or take on all three different values of that attribute. Call a collection of 33 cards two-good if exactly two attributes are good for that collection. How many two-good collections of 33 cards are there? The order in which the cards appear does not matter.

Solution

Solution:

In counting the number of sets of 33 cards, we first want to choose which of our two attributes will be good and which of our two attributes will not be good. There are (42)=6\binom{4}{2} = 6 such choices.

Now consider the two attributes which are not good, attribute XX and attribute YY. Since these are not good, some value should appear exactly twice. Suppose the value aa appears twice and bb appears once for attribute XX and that the value cc appears twice and dd appears once for attribute YY. There are three choices for aa and then two choices for bb; similarly, there are three choices for cc and then two choices for dd. This gives 3232=363 \cdot 2 \cdot 3 \cdot 2 = 36 choices of a,b,ca, b, c, and dd.

There are two cases to consider. The first is that there are two cards which both have aa and cc, while the other card has both bb and dd. The second case is that only one card has both aa and cc, while one card has aa and dd and the other has bb and cc.

Case 1:

Card 1Card 2Card 3
aab
ccd

The three cards need to be distinct. Card 3 is necessarily distinct from Card 1 and Card 2, but we need to ensure that Card 1 and Card 2 are distinct from each other. There are 99 choices for the two good attributes of Card 1, and then 88 choices for the two good attributes of Card 2. But we also want to divide by 22 since we do not care about the order of Card 1 and Card 2. So there are 982=36\frac{9 \cdot 8}{2} = 36 choices for the good attributes on Card 1 and Card 2. Then, the values of the good attributes of Card 1 and Card 2 uniquely determine the values of the good attributes of Card 3.

Case 2:

Card 1Card 2Card 3
aab
cdc

Card 1, Card 2, and Card 3 will all be distinct no matter what the values of the good attributes are, because the values of attributes XX and YY are unique to each card. So there are 99 possibilities for the values of the good attributes on Card 1, and then there are 99 more possibilities for the values of the good attributes on Card 2. We do not have to divide by 22 this time, since Card 1 and Card 2 have distinct values in XX and YY. So there are 92=819^2 = 81 possibilities here.

So our final answer is 662(36+81)=252726 \cdot 6^2 \cdot (36 + 81) = 25272.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.