HMMT 二月 2023 · 团队赛 · 第 6 题
HMMT February 2023 — Team Round — Problem 6
题目详情
- [50] For any odd positive integer n , let r ( n ) be the odd positive integer such that the binary rep- resentation of r ( n ) is the binary representation of n written backwards. For example, r (2023) = r (11111100111 ) = 11100111111 = 1855. Determine, with proof, whether there exists a strictly in- 2 2 creasing eight-term arithmetic progression a , . . . , a of odd positive integers such that r ( a ), . . . , 1 8 1 r ( a ) is an arithmetic progression in that order. 8
解析
- [50] For any odd positive integer n , let r ( n ) be the odd positive integer such that the binary rep- resentation of r ( n ) is the binary representation of n written backwards. For example, r (2023) = r (11111100111 ) = 11100111111 = 1855. Determine, with proof, whether there exists a strictly in- 2 2 creasing eight-term arithmetic progression a , . . . , a of odd positive integers such that r ( a ), . . . , 1 8 1 r ( a ) is an arithmetic progression in that order. 8 Proposed by: Daniel Zhu Solution: The main idea is the following claim. Claim: If a, b, c are in arithmetic progression and have the same number of digits in their binary representations, then r ( a ) , r ( b ) , r ( c ) cannot be in arithmetic progression in that order. Proof. Consider the least significant digit that differs in a and b. Then c will have the same value of that digit as a , which will be different from b. Since this becomes the most significant digit in r ( a ) , r ( b ) , r ( c ) , then of course b cannot be between a and c. To finish, we just need to show that if there are 8 numbers in arithmetic progression, which we’ll write as a , a + d, a + 2 d, . . . , a + 7 d , three of them have the same number of digits. We have a few cases. 1 1 1 1 k • If a + 3 d < 2 ≤ a + 4 d, then a + 4 d, a + 5 d, a + 6 d will have the same number of digits. 1 1 1 1 1 k • If a + 4 d < 2 ≤ a + 5 d , then a + 5 d, a + 6 d, a + 7 d will have the same number of digits. 1 1 1 1 1 • If neither of these assumptions are true, a + 3 d, a + 4 d, a + 5 d will have the same number of 1 1 1 digits. Having exhausted all cases, we are done.