HMMT 二月 2011 · 冲刺赛 · 第 32 题
HMMT February 2011 — Guts Round — Problem 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 all i + n n − 1 i + n − 1 1 i +1 0 i i ≥ 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th 14 HARVARD-MIT MATHEMATICS TOURNAMENT, 12 FEBRUARY 2011 — GUTS ROUND
解析
- [ 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 all i + n n − 1 i + n − 1 1 i +1 0 i i ≥ 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 n p ( p − 1) p − 1 Answer: 1 − n + 2 p +1 ( p +1) Guts Round In the solution all polynomials are taken modulo p . Call a polynomial nice if it is monic with nonzero constant coefficient. We can associate each recurrence relation with a polynomial: associate c a + c a + ... + c a + c a = 0 n i + n n − 1 i + n − 1 1 i +1 0 i with n 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 degree i 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 polynomial n k k ≥ 0 k k ≥ 0 associated to a recurrence relation of degree at most n satisfied by { a } . To find d generally, we k k ≥ 0 n count the number of elements in S in two ways. n n − i One the one hand, for each sequence { a } in D , there exist p polynomials P such that k k ≥ 0 i ( { a } , P ) ∈ S . Indeed, { a } satisfies any recurrence relation associated with a polynomial k 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 QP j − i − 1 where Q is a nice polynomial of degree j − i . (There are p choices for the coefficients of x, . . . , x and p − 1 choices for the constant term.) So the number of nice polynomial multiples of degree at most n is ( ) n n − i ∑ p − 1 j − i − 1 n − i 1 + ( p − 1) p = 1 + ( p − 1) = p . p − 1 j = i +1 Hence n ∑ n − i | S | = d p . (1) n i i =0 i On the other hand, given a monic polynomial P of degree i , there are p recurrences { a } such that k 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), summing over i gives n ∑ 2 i − 1 | S | = 1 + ( p − 1) p (2) n i =1 Now clearly d = 1. Setting (1) and (2) equal for n and n + 1 give 0 n +1 n +1 ∑ ∑ n +1 − i 2 i − 1 d p = 1 + ( p − 1) p (3) i i =0 i =1 n n ∑ ∑ n − i 2 i − 1 d p = 1 + ( p − 1) p i i =0 i =1 n n ∑ ∑ n +1 − i 2 i = ⇒ d p = p + ( p − 1) p . (4) i i =0 i =1 Guts Round Subtracting (4) from (3) yields: 2 n +1 ∑ i +1 i d = 1 − p + ( p − 1) ( − 1) p n +1 i =1 2 n +1 ∑ i +1 i = ( p − 1) ( − 1) p i =0 n ∑ 2 2 m = ( p − 1) p i =0 ( ) 2 n +2 p − 1 2 = ( p − 1) 2 p − 1 2 n +2 ( p − 1)( p − 1) = p + 1 Thus the answer is n n ∑ ∑ p − 1 2 i d = 1 + ( p − 1) i p + 1 i =0 i =1 ( ) 2 n p − 1 p − 1 2 = 1 + − n + p · 2 p + 1 p − 1 2 2 n p − 1 p ( p − 1) = 1 − n + 2 p + 1 ( p + 1)