HMMT-Nov 2023 guts, Problem 26

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

Solution: Solution: Notice that $63=2^{6}-1$, so for any $a$ we know \[ 63 a=64 a-a=2^{6}(a-1)+(64-a) \] As long as $a \leq 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 0 s to make the latter 6 digits). Furthermore, $a-1$ and $64-a$ sum to $63=111111_{2}$, so $a-1$ has 1 s in binary where $64-a$ has 0 s, and vice versa. Thus, together, they have six 1 s, so $63 a$ will always have six 1 s in binary when $a \leq 64$. We can also check $63 \cdot 65=2^{12}-1$ has twelve 1 s, while $63 \cdot 66=2(63 \cdot 33)$ has the same binary representation with an extra 0 at the end, so it also has six 1 s. Finally, \[ 63 \cdot 67=2^{12}+125=1000001111101_{2} \] has seven 1 s, so the answer is $63 \cdot 67=4221$. $\fbox{4221}$.

Answer: 4221