APMO, 2016

Let $k$ be any positive integer less than $2^{101}-1$. Then $k$ can be expressed in binary notation using at most 100 ones, and therefore there exists a positive integer $r$ and non-negative integers $a_{1}, a_{2}, \ldots, a_{r}$ such that $r \leq 100$ and $k = 2^{a_{1}} + \cdots + 2^{a_{r}}$. Notice that for a positive integer $s$ we have:
$$\begin{aligned} 2^{s} k & = 2^{a_{1}+s} + 2^{a_{2}+s} + \cdots + 2^{a_{r-1}+s} + \left(1 + 1 + 2 + \cdots + 2^{s-1}\right) 2^{a_{r}} \\ & = 2^{a_{1}+s} + 2^{a_{2}+s} + \cdots + 2^{a_{r-1}+s} + 2^{a_{r}} + 2^{a_{r}} + \cdots + 2^{a_{r}+s-1} \end{aligned}$$
This shows that $k$ has a multiple that is a sum of $r+s$ powers of two. In particular, we may take $s = 100 - r \geq 0$, which shows that $k$ has a multiple that is a fancy number.

We will now prove that no multiple of $n = 2^{101} - 1$ is a fancy number. In fact we will prove a stronger statement, namely, that no multiple of $n$ can be expressed as the sum of at most 100 powers of 2.

For the sake of contradiction, suppose that there exists a positive integer $c$ such that $c n$ is the sum of at most 100 powers of 2. We may assume that $c$ is the smallest such integer. By repeatedly merging equal powers of two in the representation of $c n$ we may assume that
$$c n = 2^{a_{1}} + 2^{a_{2}} + \cdots + 2^{a_{r}}$$
where $r \leq 100$ and $a_{1} < a_{2} < \ldots < a_{r}$ are distinct non-negative integers. Consider the following two cases:

- If $a_{r} \geq 101$, then $2^{a_{r}} - 2^{a_{r}-101} = 2^{a_{r}-101} n$. It follows that $2^{a_{1}} + 2^{a_{2}} + \cdots + 2^{a_{r-1}} + 2^{a_{r}-101}$ would be a multiple of $n$ that is smaller than $c n$. This contradicts the minimality of $c$.

- If $a_{r} \leq 100$, then $\{a_{1}, \ldots, a_{r}\}$ is a proper subset of $\{0, 1, \ldots, 100\}$. Then
$$n \leq c n < 2^{0} + 2^{1} + \cdots + 2^{100} = n.$$
This is also a contradiction.

From these contradictions we conclude that it is impossible for $c n$ to be the sum of at most 100 powers of 2. In particular, no multiple of $n$ is a fancy number.