返回题库

HMMT 二月 2018 · ALGNT 赛 · 第 5 题

HMMT February 2018 — ALGNT Round — Problem 5

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. 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 .
解析

英文解析

  1. 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.