HMMT 二月 2018 · ALGNT 赛 · 第 5 题
HMMT February 2018 — ALGNT Round — Problem 5
题目详情
- Let ω , ω , . . . , ω be the roots of (in some order). Consider the set 1 2 100 x − 1 1 2 3 100 S = { ω , ω , ω , . . . , ω } . 1 2 3 100 Let M be the maximum possible number of unique values in S , and let N be the minimum possible number of unique values in S . Find M − N .
解析
- Let ω , ω , . . . , ω be the roots of (in some order). Consider the set 1 2 100 x − 1 1 2 3 100 S = { ω , ω , ω , . . . , ω } . 1 2 3 100 Let M be the maximum possible number of unique values in S , and let N be the minimum possible number of unique values in S . Find M − N . Proposed by: Henrik Boecken Answer: 98 Throughout this solution, assume we’re working modulo 101. 1 /n First, N = 1. Let ω be a primitive 101st root of unity. We then let ω = ω , which we can do n because 101 is prime, so 1 /n exists for all nonzero n and 1 /n = 1 /m = ⇒ m = n . Thus the set contains only one distinct element, ω . π ( n ) M = 100 is impossible. Fix ζ , a primitive 101st root of unity, and let ω = ζ for each n . Suppose n that there are 100 distinct such nπ ( n ) exponents; then π permutes the set { 1 , 2 , · · · , 100 } . Fix g , a e τ ( e ) n n primitive root of 101; write n = g and π ( n ) = g . Then { e } = { 0 , 1 , 2 , . . . , 100 } and τ is a n ∑ 100 permutation of this set, as is e + τ ( e ). However, this is impossible: e + τ ( e ) = 5050 + 5050 ≡ n n n n n =1 5050 (mod 100), which is a contradiction. Thus there cannot be 100 distinct exponents. 1 / ( n +1) M = 99 is possible. Again, let ζ be a primitive root of unity and let ω = ζ , except when n n m n = 100, in which case let ω be the last possible root. Notice that = if and only if n = m , 100 n +1 m +1 so this will produce 99 different elements in the set. Thus M − N = 99 − 1 = 98.