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 ∑ i P ( x ) = x . Let X be the probability that P ( x ) is divisible by some nonconstant polynomial n i ∈ S Q ( x ) of degree at most 3 with integer coefficients satisfying Q (0) 6 = 0. Find the limit of X as n goes n to infinity.
解析
- Let S be a randomly chosen 6-element subset of the set { 0 , 1 , 2 , . . . , n } . Consider the polynomial ∑ i P ( x ) = x . Let X be the probability that P ( x ) is divisible by some nonconstant polynomial n i ∈ S Q ( x ) of degree at most 3 with integer coefficients satisfying Q (0) 6 = 0. Find the limit of X as n goes n to 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 have integer 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, all the symmetric expressions involving the roots of Q are also bounded, so by Vieta’s Theorem all the coefficients 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 divides a 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 since s 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 above 3 5 by the product of five fixed numbers divided by n / 5!, which vanishes as n goes to infinity. 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 that we 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 4 unity is impossible because x + 1 cannot be factored in the rationals). s Now we compute the probability of P ( r ) = 0 for each possible root r . Since the value of x cycles with s , and we only care about n → ∞ , we may even assume that the exponents are chosen independently at 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 = . 6 2 16 Case 2: When r = ± i , the number of exponents that are 0 modulo 4 need to be equal to those that 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 2 6 ( ) 2 , 2 , 2 10 each other, so the probability is = . 6 3 81 √ 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), i 2 then 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 deal with exponents modulo 3, the probabilities are independent from each other. So by complementary counting, we compute the final probability as 5 25 10 151 71 10015 1 − (1 − − )(1 − ) = 1 − · = . 16 256 81 256 81 20736