HMMT 二月 2011 · 冲刺赛 · 第 32 题

英文解析

32. [ 18 ] Let p be a prime positive integer. Define a mod- p recurrence of degree n to be a sequence { a }
    k k ≥ 0
    of numbers modulo p satisfying a relation of the form a = c a + ... + c a + c a for alli + n n − 1 i + n − 1 1 i +1 0 ii ≥ 0, where c , c , . . . , c are integers and c 6 ≡ 0 (mod p ). Compute the number of distinct linear
    0 1 n − 1 0
    recurrences of degree at most n in terms of p and n .
    2 2 np ( p − 1)
    p − 1
    Answer: 1 − n +
    p +1 ( p +1)2
    Guts Round
    In the solution all polynomials are taken modulo p . Call a polynomial nice if it is monic with nonzeroconstant coefficient. We can associate each recurrence relation with a polynomial: associatec a + c a + ... + c a + c a = 0
    n i + n n − 1 i + n − 1 1 i +1 0 iwithn n − 1
    c x + c x + ... + c x + c .
    n n − 1 1 0
    Let D be the set of mod- p recurrences { a } where i is the least integer so that { a } has degreei k k ≥ 0 k k ≥ 0
    i , and let d = | D | .
    i i
    Let S be the set of pairs ( { a } , P ) where { a } is a mod- p recurrence, and P is a nice polynomialn k k ≥ 0 k k ≥ 0
    associated to a recurrence relation of degree at most n satisfied by { a } . To find d generally, wek k ≥ 0 ncount the number of elements in S in two ways.
    n − in
    One the one hand, for each sequence { a } in D , there exist p polynomials P such thatk k ≥ 0 i
    ( { a } , P ) ∈ S . Indeed, { a } satisfies any recurrence relation associated with a polynomialk k ≥ 0 k k ≥ 0
    multiple of P . When j = i there is just one nice degree j polynomial that is a multiple of P , P itself.
    j − i − 1
    For j > i , there are ( p − 1) p nice polynomials of degree j that are multiples of P , namely QPj − i − 1
    where Q is a nice polynomial of degree j − i . (There are p choices for the coefficients of x, . . . , xand p − 1 choices for the constant term.) So the number of nice polynomial multiples of degree at mostn is
    ( )
    n − in
    ∑
    p − 1
    j − i − 1 n − i
    1 + ( p − 1) p = 1 + ( p − 1) = p .
    p − 1
    j = i +1
    Hencen
    ∑
    n − i
    | S | = d p . (1)
    n ii =0
    On the other hand, given a monic polynomial P of degree i , there are p recurrences { a } such thatik k ≥ 0
    ( { a } , P ) ∈ S , since a , . . . , a can be chosen arbitrarily and the rest of the terms are determined.
    k k ≥ 0 0 i − 1
    i − 1
    Since there are ( p − 1) p nice polynomials of degree i 6 = 0 (and 1 nice polynomial for i = 0), summingover i gives
    ∑n
    2 i − 1
    | S | = 1 + ( p − 1) p (2)
    i =1 n
    Now clearly d = 1. Setting (1) and (2) equal for n and n + 1 given +1 n +10
    ∑ ∑
    n +1 − i 2 i − 1
    d p = 1 + ( p − 1) p (3)
    i =0 i =1 in n
    ∑ ∑
    n − i 2 i − 1
    d p = 1 + ( p − 1) pii =0 i =1
    n n
    ∑ ∑
    n +1 − i 2 i = ⇒ d p = p + ( p − 1) p . (4)
    i =0 i =1 i
    Guts Round
    Subtracting (4) from (3) yields:
    2 n +1
    ∑
    i +1 id = 1 − p + ( p − 1) ( − 1) pn +1
    i =1
    2 n +1
    ∑
    i +1 i = ( p − 1) ( − 1) pi =0
    ∑n
    2 2 m = ( p − 1) pi =0
    ( )
    2 n +2
    p − 1 = ( p − 1)2
    p − 12
    2 n +2
    ( p − 1)( p − 1)
    p + 1=
    Thus the answer isn n
    ∑ ∑
    p − 1
    2 id = 1 + ( p − 1)
    p + 1 ii =0 i =1
    ( )
    2 np − 1 p − 1 = 1 + − n + p ·2
    p + 1 p − 12
    2 2 np − 1 p ( p − 1) = 1 − n +
    p + 1 ( p + 1)2