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,\dots ,a_r$ such that $r\le 100$ and $k=2^{a_1}+\cdots +2^{a_r}$. Notice that for a positive integer $s$ we have: $$\begin{array}{rl}{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{array}$$ 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\ge 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 $cn$ 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 $cn$ we may assume that $$cn=2^{a_1}+2^{a_2}+\cdots +2^{a_r}$$ where $r\le 100$ and $a_1<a_2<\dots <a_r$ are distinct non-negative integers. Consider the following two cases:

- If $a_r\ge 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 $cn$. This contradicts the minimality of $c$.

- If $a_r\le 100$, then $\{a_1,\dots ,a_r\}$ is a proper subset of $\{0,1,\dots ,100\}$. Then $$n\le cn<2^0+2^1+\cdots +2^{100}=n.$$ This is also a contradiction.

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