A positive integer is called fancy if it can be expressed in the form

$$
2^{a_{1}}+2^{a_{2}}+\cdots+2^{a_{100}},
$$

where $a_{1}, a_{2}, \ldots, a_{100}$ are non-negative integers that are not necessarily distinct.

Find the smallest positive integer $n$ such that no multiple of $n$ is a fancy number.

Answer: The answer is $n=2^{101}-1$.
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 $\left\{a_{1}, \ldots, a_{r}\right\}$ 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.