HMMT 十一月 2010 · 冲刺赛 · 第 30 题
HMMT November 2010 — Guts Round — Problem 30
题目详情
- [ 17 ] 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.
解析
- [ 17 ] 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. 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 63 · 62 · 61 · 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 63 · 62 · 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 (63 · 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 63 · 62 · 4 · 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 63 · 62 · 61 · 60 − 63 · 62 · 60 − 63 · 62 · (61 − 1 − 4) 63 · 62 · 61 · 60 − 63 · 62 · 60 − 63 · 62 · 4 · 60 63 · 62 · 4 · 60, so our final answer is = = 63 · 31 · 56 = 109368. 120 2