HMMT 二月 2018 · ALGNT 赛 · 第 10 题
HMMT February 2018 — ALGNT Round — Problem 10
题目详情
英文原题
- Let S be a randomly chosen 6-element subset of the set { 0 , 1 , 2 , . . . , n } . Consider the polynomial
∑
P ( x ) = x . Let X be the probability that P ( x ) is divisible by some nonconstant polynomialini ∈ S
Q ( x ) of degree at most 3 with integer coefficients satisfying Q (0) 6 = 0. Find the limit of X as n goesnto infinity.
解析
英文解析
- Let S be a randomly chosen 6-element subset of the set { 0 , 1 , 2 , . . . , n } . Consider the polynomial
∑
P ( x ) = x . Let X be the probability that P ( x ) is divisible by some nonconstant polynomialini ∈ S
Q ( x ) of degree at most 3 with integer coefficients satisfying Q (0) 6 = 0. Find the limit of X as n goesnto infinity.
Proposed by: Allen Liu
10015
Answer:
20736
We begin with the following claims:
Claim 1: There are finitely many Q ( x ) that divide some P ( x ) of the given form.
Proof: First of all the leading coefficient of Q must be 1, because if Q divides P then P/Q must haveinteger coefficients too. Note that if S = { s , s , s , s , s , s } with elements in increasing order, then
1 2 3 4 5 6
s s s s s s s s
6 5 4 1 6 5 4 1
| P ( x ) | ≥ | x | − | x | − | x | − · · · − | x | = | x | − | x | − | x | − · · · − | x | ,
so all the roots of P must have magnitude less than 2, and so do all the roots of Q . Therefore, allthe symmetric expressions involving the roots of Q are also bounded, so by Vieta’s Theorem all thecoefficients of Q of a given degree are bounded, and the number of such Q is therefore finite.
Claim 2: If Q has a nonzero root that does not have magnitude 1, then the probability that it dividesa randomly chosen P vanishes as n goes to infinity.
Proof: WLOG suppose that Q has a root r with | r | > 1 (similar argument will apply for | r | < 1).
Then from the bound given in the proof of Claim 1, it is not difficult to see that s − s is bounded
6 5
sinces s s − s
6 5 6 5
| P ( r ) | > | r | − 5 | r | > | r | − 5 ,
which approaches infinity as s − s goes to infinity. By similar argument we can show that s − s , s −
6 5 5 4 4
s , . . . are all bounded. Therefore, the probability of choosing the correct coefficients is bounded aboveby the product of five fixed numbers divided by n / 5!, which vanishes as n goes to infinity.53
From the claims above, we see that we only need to consider polynomials with roots of magnitude
1, since the sum of all other possibilities vanishes as n goes to infinity. Moreover, this implies thatwe only need to consider roots of unity. Since Q has degree at most 3, the only possible roots are
√ √
− 1 ± i 3 1 ± i 3 2 2 2 − 1 , ± i, , , corresponding to x + 1 , x + 1 , x + x + 1 , x − x + 1 (note that eighth root of
2 2
unity is impossible because x + 1 cannot be factored in the rationals).4
Now we compute the probability of P ( r ) = 0 for each possible root r . Since the value of x cycles withss , and we only care about n → ∞ , we may even assume that the exponents are chosen independentlyat random, with repetition allowed.
Case 1: When r = − 1, the number of odd exponents need to be equal to the number of even exponents,
( )6
3 5
which happens with probability = .
2 166
Case 2: When r = ± i , the number of exponents that are 0 modulo 4 need to be equal to thosethat are 2 modulo 4, and same for 1 modulo 4 and 3 modulo 4, which happens with probability
6 0 6 6 2 4 6 4 2 6 6 0
( ) ( )( ) ( ) ( )( ) ( ) ( )( ) ( ) ( )( )
0 0 3 2 1 2 4 2 1 6 3 0 25
· + · + · + · = . Note that Case 1 and Case 2 have no overlaps,
6 6 6 6 6 6 6 6
2 2 2 2 2 2 2 2 256
since the former requires 3 even exponents, and the latter requires 0 , 2 , 4 , or 6 even exponents.
√
− 1 ± i 3
Case 3: When r = , the number of exponents that are 0 , 1 , 2 modulo 3 need to be equal to
( )62
2 , 2 , 2 10
each other, so the probability is = .
3 816
√
1 ± i 3
Case 4: When r = , then if n is the number of exponents that are i modulo 6 ( i = 0 , 1 , 2 , 3 , 4 , 5),
2 ithen n − n = n − n = n − n = k for some k . Since 3 k ≡ n + n + · · · + n = 6 ≡ 0 (mod 2),
0 3 2 5 4 1 0 1 5
k must be one of − 2 , 0 , 2. When k = 0, we have n + n + n = n + n + n , which is the same as
0 2 4 1 3 5
Case 1. When k = 2, we have n = n = n = 2, which is covered in Case 3, and similar for k = − 2.
0 2 4
Therefore we do not need to consider this case.
Now we deal with over-counting. Since Case 1 and 2 deal with the exponents modulo 4 and Case 3 dealwith exponents modulo 3, the probabilities are independent from each other. So by complementarycounting, we compute the final probability as
5 25 10 151 71 10015
1 − (1 − − )(1 − ) = 1 − · = .
16 256 81 256 81 20736