HMMT 十一月 2010 · 冲刺赛 · 第 30 题

英文解析

30. [ 17 ] In the game of projective set, each card contains some nonempty subset of six distinguishabledots. 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 cardsappear does not matter.
    Answer: 109368 We’ll first count sets of cards where the order does matter. Suppose we choosethe 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 subtractfor these two cases. First, there are 63 · 62 · 61 · 60 ways to choose the first four cards. Let’s now counthow 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 ofthe first two or the card that completes a set. If that is the case, then the fourth card is unique. Thiscomes 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 ofways 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 havean even number of each dot is just the number of ways to choose two cards. Therefore, we’ll choosetwo cards (63 · 62 ways), choose the slot in the first four positions for the duplicate card (4 ways), andthe 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