HMMT 二月 2021 · ALGNT 赛 · 第 8 题
HMMT February 2021 — ALGNT Round — Problem 8
题目详情
- For positive integers a and b , let M ( a, b ) = , and for each positive integer n ≥ 2, define gcd( a,b ) x = M (1 , M (2 , M (3 , . . . , M ( n − 2 , M ( n − 1 , n )) . . . ))) . n 2 2 Compute the number of positive integers n such that 2 ≤ n ≤ 2021 and 5 x + 5 x = 26 x x . n n +1 n n +1
解析
- For positive integers a and b , let M ( a, b ) = , and for each positive integer n ≥ 2, define gcd( a,b ) x = M (1 , M (2 , M (3 , . . . , M ( n − 2 , M ( n − 1 , n )) . . . ))) . n 2 2 Compute the number of positive integers n such that 2 ≤ n ≤ 2021 and 5 x + 5 x = 26 x x . n n +1 n n +1 Proposed by: Hahn Lheem Answer: 20 Solution: The desired condition is that x = 5 x or x = 5 x . n n +1 n +1 n Note that for any prime p , we have ν ( M ( a, b )) = | ν ( a ) − ν ( b ) | . Furthermore, ν ( M ( a, b )) ≡ ν ( a ) + p p p p p ν ( b ) mod 2. So, we have that p ν ( x ) ≡ ν (1) + ν (2) + · · · + ν ( n ) mod 2 . p n p p p Subtracting gives that ν ( x ) − ν ( x ) ≡ ν ( n + 1) mod 2. In particular, for p 6 = 5, ν ( n + 1) must be p n +1 p n p p ⌊√ ⌋ 2021 even, and ν ( n + 1) must be odd. So n + 1 must be a 5 times a perfect square. There are = 20 5 5 such values of n in the interval [2 , 2021]. Now we show that it is sufficient for n + 1 to be 5 times a perfect square. The main claim is that if ∑ B > 0 and a sequence a , a , . . . , a of nonnegative real numbers satisfies a ≤ B + a for all 1 2 B n i i<n 1 ≤ n ≤ N , then ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ a − a − · · · − a − a · · · ≤ B. ∣ ∣ ∣ ∣ 1 2 N − 1 N ∣ ∣ ∣ ∣ This can be proved by a straightforward induction on N . We then apply this claim, with B = 1, to the sequence a = ν ( i ); it is easy to verify that this sequence satisfies the condition. This gives i p ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ν ( x ) = ν (1) − ν (2) − · · · − ν ( n − 1) − ν ( n ) · · · ≤ 1 , ∣ ∣ ∣ ∣ p n p p p p ∣ ∣ ∣ ∣ ( ) 2 so ν ( x ) must be equal to ν (1) + · · · + ν ( n ) mod 2. Now suppose n + 1 = 5 k for some k ; then p n p p ν ( n + 1) ≡ 0 mod 2 for p 6 = 5 and ν ( n + 1) ≡ 1 mod 2. Therefore ν ( x ) = ν ( x ) for p 6 = 5, and p 5 p n +1 p n ν ( x ) = ( ν ( x ) + 1) mod 2, and this implies x /x ∈ { 1 / 5 , 5 } as we wanted. 5 n +1 5 n n +1 n