HMMT 二月 2014 · 代数 · 第 10 题
HMMT February 2014 — Algebra — Problem 10
题目详情
- For an integer n , let f ( n ) denote the number of positive integers d 9 dividing n . Suppose that m is 9 P m a positive integer and b , b , . . . , b are real numbers such that f ( n ) = b f ( n j ) for all n > m . 1 2 m 9 j 9 j =1 Find the smallest possible value of m . HMMT 2014 Saturday 22 February 2014 Algebra PUT LABEL HERE Name Team ID# Organization Team
Score:
解析
- For an integer n , let f ( n ) denote the number of positive integers d ≤ 9 dividing n . Suppose that m is 9 ∑ m a positive integer and b , b , . . . , b are real numbers such that f ( n ) = b f ( n − j ) for all n > m . 1 2 m 9 j 9 j =1 Find the smallest possible value of m . Answer: 28 Let M = 9. Consider the generating function M M d ∑ ∑ ∑ ∑ x n dk F ( x ) = f ( n ) x = x = . M d 1 − x n ≥ 1 d =1 k ≥ 1 d =1 Observe that f ( n ) = f ( n + M !) for all n ≥ 1 (in fact, all n ≤ 0 as well). Thus f ( n ) satisfies a M M M degree m linear recurrence if and only if it eventually satisfies a degree m linear recurrence. But the latter occurs if and only if P ( x ) F ( x ) is a polynomial for some degree m polynomial P ( x ). (Why?) s Suppose P ( x ) F ( x ) = Q ( x ) is a polynomial for some polynomial P of degree m . We show that x − 1 | P ( x ) for s = 1 , 2 , . . . , M , or equivalently that P ( ω ) = 0 for all primitive s th roots of unity 1 ≤ s ≤ M ). Fix a primitive s th root of unity ω , and define a function d d ∑ ∑ z z − 1 F ( z ) = (1 − ω z ) + ω d − 1 − 1 d − 1 1 − z 1 + ( ω z ) + · · · + ( ω z ) s | d ≤ M s ∤ d ≤ M for all z where all denominators are nonzero (in particular, this includes z = ω ). − 1 1 2 M Yet F ( z ) − F ( z )(1 − ω z ) = 0 for all complex z such that z , z , . . . , z 6 = 1, so P ( z ) F ( z ) − Q ( z )(1 − ω ω − 1 − 1 ω z ) = 0 holds for all such z as well. In particular, the rational function P ( x ) F ( x ) − Q ( x )(1 − ω x ) ω has infinitely many roots, so must be identically zero once we clear denominators . But no denominator vanishes at x = ω , so we may plug in x = ω to the polynomial identity and then divide out by the − 1 original (nonzero) denominators to get 0 = P ( ω ) F ( ω ) − Q ( ω )(1 − ω ω ) = P ( ω ) F ( ω ). However, ω ω d ∑ ∑ ω 1 F ( ω ) = = ω − 1 − 1 d − 1 1 + ( ω ω ) + · · · + ( ω ω ) d s | d ≤ M s | d ≤ M is a positive integer multiple of 1 /d , and therefore nonzero. Thus P ( ω ) = 0, as desired. s Conversely, if x − 1 | P ( x ) for s = 1 , 2 , . . . , M , then P ( x ) will clearly suffice. So we just want the s degree of the least common multiple of the x − 1 for s = 1 , 2 , . . . , M , or just the number of roots of ∑ M unity of order at most M , which is φ ( s ) = 1 + 1 + 2 + 2 + 4 + 2 + 6 + 4 + 6 = 28. s =1 Comment: Only at the beginning do we treat F ( x ) strictly as a formal power series; later once we get ∑ d 6 x the rational function representation , we can work with polynomial identities in general and d d =1 1 − x don’t have to worry about convergence issues for | x | ≥ 1.