HMMT 二月 2023 · COMB 赛 · 第 7 题
HMMT February 2023 — COMB Round — Problem 7
题目详情
- Svitlana writes the number 147 on a blackboard. Then, at any point, if the number on the blackboard is n , she can perform one of the following three operations: n • if n is even, she can replace n with ; 2 n +255 • if n is odd, she can replace n with ; and 2 • if n ≥ 64, she can replace n with n − 64. Compute the number of possible values that Svitlana can obtain by doing zero or more operations.
解析
- Svitlana writes the number 147 on a blackboard. Then, at any point, if the number on the blackboard is n , she can perform one of the following three operations: n • if n is even, she can replace n with ; 2 n +255 • if n is odd, she can replace n with ; and 2 • if n ≥ 64, she can replace n with n − 64. Compute the number of possible values that Svitlana can obtain by doing zero or more operations. Proposed by: Jerry Liang, Vidur Jasuja Answer: 163 ( ) ∑ 4 8 8 Solution: The answer is 163 = . This is because we can obtain any integer less than 2 with i =0 i 7 4 1 0 less than or equal to 4 ones in its binary representation. Note that 147 = 2 + 2 + 2 + 2 . We work in binary. Firstly, no operation can increase the number of ones in n ’s binary representation. The first two operations cycle the digits of n to the right, and the last operation can change a 11 , 10 , 01 at the front of n to 10 , 01 , 00, respectively. This provides an upper bound. To show we can obtain any of these integers, we’ll show that given a number m with base 2 sum 1 of digits k , we can obtain every number with base 2 sum of digits k . Since we can, by cycling, change any 10 to an 01, we can move all of m ’s ones to the end, and then cycle so they’re all at 1 the front. From here, we can just perform a series of swaps to obtain any other integer with this same sum of digits. It’s also easy to see that we can decrement the sum of digits of n , by cycling a 1 to the second digit of the number and then performing the third operation. So this proves the claim.