HMMT 二月 2015 · 冲刺赛 · 第 31 题
HMMT February 2015 — Guts Round — Problem 31
题目详情
- [ 20 ] Define a power cycle to be a set S consisting of the nonnegative integer powers of an integer a , 2 i.e. S = { 1 , a, a , . . . } for some integer a . What is the minimum number of power cycles required such that given any odd integer n , there exists some integer k in one of the power cycles such that n ≡ k (mod 1024)?
解析
- [ 20 ] Define a power cycle to be a set S consisting of the nonnegative integer powers of an integer a , 2 i.e. S = { 1 , a, a , . . . } for some integer a . What is the minimum number of power cycles required such 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 n a a n +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, then a S is in the union of class n and the residues 1 (mod 1024). Therefore, S cannot contain two of the a 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 between 256 any two is a positive power of 5 smaller than 5 , so the ratio is not congruent to 1 and any two terms are not congruent mod 1024. In addition, all terms are in class 1, and class 1 has 256 members, so S 5 contains members congruent to each element of class 1. 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 − n a , 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 . a Finally, S contains members congruent to the element of class 10. − 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 the n 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 we have the statement holds for n − 1 and we wish to show it for n where n ≥ 5. Suppose no such integer n − 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 for n − 4 n − 1 2 the above relation to be true we require 2 divides x − 1 for all odd x . However, by taking x to n − 3 n − 1 have order 2 modulo 2 (which exists by the inductive hypothesis) we get a contradiction so we are 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 k would 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) k but − 1 + 1024 m is never 1 (mod 4) for any integer m so it follows − 1 is not equal to x modulo 1024 for any integer k . Thus it follows that when we let S to be the set of powers of x , then no two elements in S and − S are congruent modulo 1024. As the order of x is 256 and there are 512 possible odd remainders upon dividing by 1024, it immediately follows that every integer x is congruent modulo k 1024 to ± x for some 1 ≤ k ≤ 256 and some choice of sign. 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 for k 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 show that we cannot do any better suppose there exist 9 power cycles which include all odd integers modulo k 2
- Then remark that − x is congruent to a number in a power cycle modulo 1024 if and only if k − 2 · a the 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 odd integers 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.