HMMT 十一月 2023 · 冲刺赛 · 第 26 题

HMMT November 2023 — Guts Round — Problem 26

[13] Compute the smallest multiple of 63 with an odd number of ones in its base two representation.

解析

[13] Compute the smallest multiple of 63 with an odd number of ones in its base two representation. Proposed by: Holden Mui Answer: 4221 6 Solution: Notice that 63 = 2 − 1 , so for any a we know 6 63 a = 64 a − a = 2 ( a − 1) + (64 − a ) . As long as a ≤ 64 , we know a − 1 and 64 − a are both integers between 0 and 63 , so the binary representation of 63 a is just a − 1 followed by 64 − a in binary (where we append leading 0s to make the latter 6 digits). Furthermore, a − 1 and 64 − a sum to 63 = 111111 , so a − 1 has 1s in binary where 64 − a has 0s, 2 and vice versa. Thus, together, they have six 1s, so 63 a will always have six 1s in binary when a ≤ 64 . 12 We can also check 63 · 65 = 2 − 1 has twelve 1s, while 63 · 66 = 2(63 · 33) has the same binary representation with an extra 0 at the end, so it also has six 1s. Finally, 12 63 · 67 = 2 + 125 = 1000001111101 2 has seven 1s, so the answer is 63 · 67 = 4221 .