Maths Olympiad Prep

Library / /69 of 82

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:

In the game of projective set, each card contains some nonempty subset of six distinguishable dots. A projective set deck consists of one card for each of the 63 possible nonempty subsets of dots. How many collections of five cards have an even number of each dot? The order in which the cards appear does not matter.

Solution

Solution:

Answer: 109368

We'll first count sets of cards where the order does matter. Suppose we choose the first four cards. Then there is exactly one card that can make each dot appear twice. However, this card could be empty or it could be one of the cards we've already chosen, so we have to subtract for these two cases. First, there are 6362616063 \cdot 62 \cdot 61 \cdot 60 ways to choose the first four cards.

Let's now count how many ways there are that the fifth card could be empty. The fifth card is empty if and only if the first four cards already have an even number of each dot. Suppose we choose the first two cards. There is a possible fourth card if the third card is not either of the first two or the card that completes a set. If that is the case, then the fourth card is unique. This comes to 63626063 \cdot 62 \cdot 60 cases.

Now consider how many ways there are for the fifth card to be a duplicate. This is just the number of ways for three cards to have an even number of each dot, then have two copies of the same card in the other two slots, one of which needs to be the fifth slot. The number of ways for three cards to have an even number of each dot is just the number of ways to choose two cards. Therefore, we'll choose two cards (636263 \cdot 62 ways), choose the slot in the first four positions for the duplicate card (4 ways), and the duplicate card, which can't be any of the nonduplicated cards, so there are 60 choices. Therefore, there are 636246063 \cdot 62 \cdot 4 \cdot 60 ways for the fifth card to be the same as one of the first four.

This means that the number of five card sets where the order does matter is 63626160636260636246063 \cdot 62 \cdot 61 \cdot 60 - 63 \cdot 62 \cdot 60 - 63 \cdot 62 \cdot 4 \cdot 60, so our final answer is
636261606362606362460120=6362(6114)2=633156=109368. \frac{63 \cdot 62 \cdot 61 \cdot 60 - 63 \cdot 62 \cdot 60 - 63 \cdot 62 \cdot 4 \cdot 60}{120} = \frac{63 \cdot 62 \cdot (61 - 1 - 4)}{2} = 63 \cdot 31 \cdot 56 = 109368.

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.