HMMT 二月 2015 · 冲刺赛 · 第 31 题

英文解析

31. [ 20 ] Define a power cycle to be a set S consisting of the nonnegative integer powers of an integer a ,
    i.e. S = { 1 , a, a , . . . } for some integer a . What is the minimum number of power cycles required such 2
    that given any odd integer n , there exists some integer k in one of the power cycles such that n ≡ k
    (mod 1024)?
    Answer: 10 Solution 1. Partition the odd residues mod 1024 into 10 classes:
    • Class 1: 1 (mod 4).
    n n +1
    • Class n (2 ≤ n ≤ 9): 2 − 1 (mod 2 ).
    • Class 10: − 1 (mod 1024).
    Let S be the power cycle generated by a . If a is in class 1, all of S is in class 1. If a is in class na an +1
    (2 ≤ n ≤ 9), then S is in the union of class n and the residues 1 (mod 2 ). If a is in class 10, thena
    S is in the union of class n and the residues 1 (mod 1024). Therefore, S cannot contain two of thea a
    2 3 10
    following residues: 5 , 2 − 1 , 2 − 1 , . . . 2 − 1, and that at least 10 cycles are needed.
    128 2 64
    Note that 5 − 1 = (5 − 1)(5+1)(5 +1) · · · (5 +1) has exactly 9 factors of 2 in its prime factorization,
    256 128 128
    while 5 − 1 = (5 − 1)(5 + 1) is divisible by 1024 so the order of 5 modulo 1024, the smallest
    Guts
    0 1 255
    positive power of 5 that is congruent to 1, is 256. Observe that among 5 , 5 , . . . 5 , the ratio betweenany two is a positive power of 5 smaller than 5 , so the ratio is not congruent to 1 and any two terms 256
    are not congruent mod 1024. In addition, all terms are in class 1, and class 1 has 256 members, so Scontains members congruent to each element of class 1.5
    n 10 − n 9 − n
    Similarly, let 2 ≤ n ≤ 9. Then the order of a , where a = 2 − 1, is 2 . The 2 terms
    10 − n
    1 3 2 − 1 9 − na , a , . . . a are pairwise not congruent and all in class n . Class n only has 2 members,
    so S contains members congruent to each element of class n .
    Finally, S contains members congruent to the element of class 10.a − 1
    The cycles S , S , and 8 cycles S cover all the residues mod 1024, so the answer is 10.
    5 − 1 a
    Solution 2. Lemma. Given a positive integer n ≥ 3, there exists an odd integer x such that then n − 2
    order of x modulo 2 is 2 .
    Proof. We apply induction on n . The base cases of n = 3 , 4 are clearly true with x = 3, so suppose wehave the statement holds for n − 1 and we wish to show it for n where n ≥ 5. Suppose no such integern − 3 n − 4 n − 4
    2 n 2 2
    x exists, so we have x ≡ 1 (mod 2 ) for all odd x . But then remark that ( x − 1)( x + 1) ≡ 0
    n − 4
    n 2
    (mod 2 ). As n − 4 ≥ 1 we have x + 1 ≡ 2 (mod 4) as all squares are 1 (mod 4), so it follows forn − 4
    n − 1 2
    the above relation to be true we require 2 divides x − 1 for all odd x . However, by taking x ton − 3 n − 1
    have order 2 modulo 2 (which exists by the inductive hypothesis) we get a contradiction so weare done.
    8 10 k 10
    Now, let x have order 2 modulo 2 . Remark that if for some integer k we had x ≡ − 1 (mod 2 ), we
    2 k 10 7 kwould have x ≡ 1 (mod 2 ) so 2 | k . In that case k is even so as x is odd we have x ≡ 1 (mod 4)
    but − 1 + 1024 m is never 1 (mod 4) for any integer m so it follows − 1 is not equal to x modulo 1024 kfor any integer k . Thus it follows that when we let S to be the set of powers of x , then no two elementsin S and − S are congruent modulo 1024. As the order of x is 256 and there are 512 possible oddremainders upon dividing by 1024, it immediately follows that every integer x is congruent modulo
    1024 to ± x for some 1 ≤ k ≤ 256 and some choice of sign.k
    7 8
    2 4 2 2 a
    Now, it is easy so see that x, − x, − x , − x , . . . , − x , − x generating 10 power cycles works ( x fork k
    2 a 2
    any a is in the first, and then − x for odd a is in the power cycle generated by − x ). To showthat we cannot do any better suppose there exist 9 power cycles which include all odd integers modulo
    2 k
32. Then remark that − x is congruent to a number in a power cycle modulo 1024 if and only ifk − 2 · athe power cycle is generated by an integer congruent to x (mod 1024) where a is an odd integer.
    a 2 a 256 a
    1 2 9
    It follows that 9 integers must be congruent to − x , − x , . . . , − x (mod 1024) for some oddintegers a , a , . . . , a . But then 3 is clearly not in any of the power cycles, contradiction so it follows
    1 2 9
    we must have at least 10 power cycles so we are done.