返回题库

HMMT 二月 2018 · ALGNT 赛 · 第 10 题

HMMT February 2018 — ALGNT Round — Problem 10

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. 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.
解析

英文解析

  1. 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