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 possiblenumber 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 possiblenumber 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 101 st root of unity. We then let ω = ω , which we can donbecause 101 is prime, so 1 /n exists for all nonzero n and 1 /n = 1 /m = ⇒ m = n . Thus the setcontains only one distinct element, ω .
π ( n )
M = 100 is impossible. Fix ζ , a primitive 101 st root of unity, and let ω = ζ for each n . Supposenthat there are 100 distinct such nπ ( n ) exponents; then π permutes the set { 1 , 2 , · · · , 100 } . Fix g , ae τ ( e )
n nprimitive root of 101; write n = g and π ( n ) = g . Then { e } = { 0 , 1 , 2 , . . . , 100 } and τ is a
∑npermutation of this set, as is e + τ ( e ). However, this is impossible: e + τ ( e ) = 5050 + 5050 ≡100
n n n nn =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 whennn mn = 100, in which case let ω be the last possible root. Notice that = if and only if n = m ,
n +1 m +1100
so this will produce 99 different elements in the set.
Thus M − N = 99 − 1 = 98.