HMMT 二月 2020 · COMB 赛 · 第 7 题
HMMT February 2020 — COMB Round — Problem 7
题目详情
英文原题
- Anne-Marie has a deck of 16 cards, each with a distinct positive factor of 2002 written on it. Sheshuffles the deck and begins to draw cards from the deck without replacement. She stops when thereexists a nonempty subset of the cards in her hand whose numbers multiply to a perfect square. Whatis the expected number of cards in her hand when she stops?
解析
英文解析
- Anne-Marie has a deck of 16 cards, each with a distinct positive factor of 2002 written on it. Sheshuffles the deck and begins to draw cards from the deck without replacement. She stops when thereexists a nonempty subset of the cards in her hand whose numbers multiply to a perfect square. Whatis the expected number of cards in her hand when she stops?
Proposed by: Michael Ren
Answer:837
Solution: Note that 2002 = 2 · 7 · 11 · 13 , so that each positive factor of 2002 is included on exactly 208
one card. Each card can identified simply by whether or not it is divisible by each of the 4 primes, andwe can uniquely achieve all of the 2 possibilities. Also, when considering the product of the values on 4
many cards, we only care about the values of the exponents in the prime factorization modulo 2, aswe have a perfect square exactly when each exponent is even.
Now suppose Anne-Marie has already drawn k cards. Then there are 2 possible subsets of cards fromkthose she has already drawn. Note that if any two of these subsets have products with the same fourexponents modulo 2, then taking the symmetric difference yields a subset of cards in her hand whereall four exponents are 0 (mod 2) , which would cause her to stop. Now when she draws the ( k + 1)thcard, she achieves a perfect square subset exactly when the the exponents modulo 2 match those froma subset of the cards she already has. Thus if she has already drawn k cards, she will not stop if shedraws one of 16 − 2 cards that don’t match a subset she already has.k
Let p be the probability that Anne-Marie draws at least k cards. We have the recurrencek
16 − 2 kp = pk +2 k +1
16 − kbecause in order to draw k + 2 cards, the ( k + 1)th card, which is drawn from the remaining 16 − kcards, must not be one of the 16 − 2 cards that match a subset of Anne-Marie’s first k cards. We nowkcomputep = 1 ,
p = ,151
14 7162
p = p = ,
3 2
15 8
12 3
p = p = ,
4 3
14 4
8 6
p = p = ,
5 4
13 13
p = 0 .
The expected number of cards that Anne-Marie draws is 6
15 7 3 6 837
p + p + p + p + p = 1 + + + + = .
1 2 3 4 5
16 8 4 13 208