Some WOOTers might have been happy to see this problem...

alternate solution xD (1) any number in $[2^{100}-1,2^{101}-2]$ is a fancy number Pf: consider $2^{a_1}+2^{a_2}+\cdots+2^{a_{100}}$ where $a_i \in \left\{ i-1, i \right\}$, hence $a_1 =1 \text{ or } 2$, $a_2=2 \text{ or } 3$ and so on we can write this alternately as $(2^0+x_12^0)+(2^1+x_12^1)+\cdots+(2^{99}+x_i2^{99})$ where $x_i \in \left\{ 0, 1 \right\}$ this equals to $(2^0+2^1+\cdots + 2^{99})+(x_12^0+x_22^1+\cdots+x_{100}2^{99})$ notice that $x_12^0+x_22^1+\cdots+x_{100}2^{99}$ can take on any number in $[0,2^{100}-1]$ thus $(2^0+2^1+\cdots + 2^{99})+(x_12^0+x_22^1+\cdots+x_{100}2^{99})$ can be any number in $[2^{100}-1,2^{101}-2]$ (2) any positive integer less than $2^{101}-1$ have a multiple in $[2^{100}-1,2^{101}-2]$ obviously if it isn't in this range we can multiply it by 2 until it get into this range (3) $2^{101}-1 \nmid 2^{a_1}+2^{a_2}+\cdots + 2^{a_{100}}$ suppose $k$ is the minimum number that there exists $a_1,a_2,...,a_k$ such that $$2^{101}-1 \mid 2^{a_1}+2^{a_2}+\cdots + 2^{a_k}$$suppose $k \le 100$ Notice that $2^{a_i} \equiv 2^0,2^1,...,2^{100} \pmod {2^{101}-1}$ if there is $i,j$ that $2^{a_i}$ and $2^{a_j}$ have the same modulo i.e $2^{a_i} \equiv 2^{a_j} \equiv 2^m \pmod {2^{101}-1}$ then $2^{a_i}+2^{a_j} \equiv 2^{m+1} \pmod{2^{101}-1}$ so we can change $a_i,a_j$ to $m+1$ which is still divided by $2^{101}-1$ but with only $k-1$ terms, a contradiction if there is no $i,j$ that $2^{a_i}$ and $2^{a_j}$ have the same modulo then $2^{a_1}+2^{a_2}+\cdots + 2^{a_k} \equiv 2^{b_1}+2^{b_2}+\cdots + 2^{b_k} \pmod {2^{101}-1}$ where $b_1,b_2,...b_k$ are different number in $\left\{ 1,2,...,100 \right\}$ but $0<2^{b_1}+2^{b_2}+\cdots + 2^{b_k} \le 2^{101-k}+\cdots+2^{99}+2^{100} \le 2^1+\cdots+2^{99}+2^{100} = 2^{101}-2$ thus $2^{a_1}+2^{a_2}+\cdots + 2^{a_k}$ cannot be divided by $2^{101}-1$, a contradiction

What is the motivation for proving that no multiple of $2^{101}-1$ is fancy? Thanks!

Because it's the smallest number that is possibly a fancy number. Then you check that the multiple has to be at least $2^{101} \cdot (2^{101}-1)$, which makes you suspect it's fancy. Then, you proceed to use the lemma from PFTB(it's basically a generalization for any number of digits and any base, and the proof is by infinite descent using the fact that the multiple obviously has to be big enough).

MathPanda1 wrote: What is the motivation for proving that $2^{101}-1$ is fancy? Thanks! Sorry if I'm misunderstanding, but isn't $2^{101}-1$ not a fancy number?

bobthesmartypants wrote: MathPanda1 wrote: What is the motivation for proving that $2^{101}-1$ is fancy? Thanks! Sorry if I'm misunderstanding, but isn't $2^{101}-1$ not a fancy number? He means the motivation for proving that $2^{101}-1$ is the answer.

Thank you CantonMathGuy, that is what I mean. So, does anyone have any motivation, assuming that I have not been to WOOT or read PFTB? Thank you very much!

Well it is the smallest non-trivial non-fancy number, so one would reasonably predict that it was also the correct answer for $n$.

Sorry, I said it wrong. How does one come up with the proof that no multiple of $2^101-1$ is fancy?

My solution: We claim that the answer is $2^{101}-1$. We'll prove our claim in two steps.

MathPanda1 wrote: Sorry, I said it wrong. How does one come up with the proof that no multiple of $2^101-1$ is fancy?

The basic motivation comes from the fact that only 1 appears in the binary representation of the number.

Another approach: First we look at some small value of $n,$ let's see $n=2$ \[\begin{array}{ccccc} 2=2^0+2^0&3=2^1+2^0&4=2^1+2^1&5=2^2+2^0&6=2^2+2^1 \end{array}\]So I find that $7$ is not fancy when $n=2.$ Analogously we analyze the case that $n=3,$ and we can find that $15$ is not fancy. So I conjecture that the answer is $2^{n+1}-1$ for general $n.$ We consider module $2^{n+1}-1.$ Notice that $2^{n+1}\equiv 2^0 \pmod{2^{n+1}-1}.$ Hence it suffices to prove that \[2^{a_1}+2^{a_2}+\dots+2^{a_n}\neq 0 \pmod{2^{n+1}-1}.\]Where $0\le a_i \le n$ for each $i=1,2,\dots,n.$ Let \[s_2(n)\stackrel{\text{def}}{=}\text{the sum of the digits of $n$ when it is written in base $2$.}\]Clearly $s_2(\text{fancy number})\le n,$ but $s_2(2^{n+1}-1)=s_2\left(\overline{\underbrace{11\dots11}_{n+1\,\text{terms}}}\right)=n+1.$ Contradiction. To show the number that less than $2^{n+1}-1$ is fancy, see #2. $\square$

For motivation, you can consider smaller sums. The question asks for the smallest $n$ s.t. no multiple of $n$ can be expressed in the form $2^{a_1} + 2^{a_2} + \dots 2^{a_{100}}$. What is the smallest $n$ s.t. no multiple can be expressed in the form $2^{a_1}$? How about $2^{a_1} + 2^{a_2}$? And $2^{a_1} + 2^{a_2} + 2^{a_3}$? Working out these small cases can give you enough intuition for the given problem.

Never got around to doing this problem when it was posted. First to remove the tehnicallity of having two numbers in the $\{ a_1,a_2,...a_{100} \}$ we do the following $\bullet$ if $a_i=a_j$ merge $\{a_i,a_j\}$ into $\{a_j+1\}$ And keep doing this until all of the numbers are different (note by this two numbers that weren't equal could become equal). The former procedure allows to write every fancy in binary with no more than 100 non-zero digits .Now we prove a lemma: Lemma: In any base $b$,a number $a$ that satisfies $b^n-1\mid a$ has at least $n$ non-zero digits. Lemma isn't anything new as it appeared in PEN A33 and in ISL 1993. Proof of the lemma: Consider the smallest number with the smallest number of non-zero digits, call it $w$.Now if this number is at least $n$ then there's nothing to talk about.Assume the opposite ,let the number of non-zero digits be $f(w)$.If there exist two indexes $i,j$ such that $i\equiv_n j $ than: $\bullet a_{\max_{i,j}}>1 \vee a_{\min_{i,j}}<b-1 \implies a'_{\max_{i,j}}=a_{\max_{i,j}}-1,a'_{\min_{i,j}}=a_{\min_{i,j}}+1$ $\bullet a_{\max_{i,j}}=1 \wedge a_{\min_{i,j}}=b-1 \implies \text{erase both of numbers and write 1 in the max (i,j) +1 place}$ Both of the above actions either decrease number in the size or decrease the number of zeroes hence a contradiction.Hence there are no such indexes ,so now drop all the zero digits and we obtain a number with $f(w)<n$ digits a contradiction.Hence the lemma is proved. By the Lemma the number for which the assertation fails is $2^{101}-1$.Proving that all the numbers less than $2^{101}-1$ follows from the fact that they have at most $100$ non-zero digits so by writing them in binary and replace $\{a_i\}$ with $\{a_i-1,a_i-1\}$ if needed.

MathPanda1 wrote: What is the motivation for proving that no multiple of $2^{101}-1$ is fancy? Thanks! Actually, the motivation is realizing that you need to consider binary representation. After that, you can easily realize why all $n<2^{101}-1$ is fancy using $2^x=2^{x-1}+2^{x-1}$. shinichiman wrote: 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, \cdots, 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. I am not sure why but most of the solutions look fancy and flashy :-p . This problem is actually a classic one IMHO (mine is the same as official, so will use their notation). As pointed out already, if $n<2^{101}-1$ then $2^sn$ can be written as a sum of $100$ powers of $2$ if we choose $s$ appropriately. For proving that $n=2^{101}-1$ works, we can use Infinite descent. Assume that $kn=2^{b_1}+2^{b_2}+\cdots+2^{b_r}$ after merging same powers of $2$. So we have $r\leq100$ and WLOG $1\leq b_1<b_2<\cdots<b_r$. Consider the smallest $k$ for which $kn$ is fancy. If $b_r\leq100$ then we have $kn<2^0+2^1+\cdots+2^{100}=n$, contradiction. If $b_r\geq101$, then $2^{b_1}+\cdots+2^{b_{r-1}}=2^{b_r}-2^{b_r-101} = 2^{b_r-101}n$. Infinite Descent

Similar problem: s(n) is n's sum of digits in decimal. Then prove $s((10^l-1)k)>=s(10^l-1)$ It can be proved in a similar way.

For the problem above, take the least number contradicting the fact. Then construct a smaller one.

Nikolapavlovic said Quote: Consider the smallest number with the smallest number of non-zero digits, call it $w$.Now if this number is at least $n$ then there's nothing to talk about.Assume the opposite ,let the number of non-zero digits be $f(w)$.If there exist two indexes $i,j$ such that $i\equiv_n j $ than: $\bullet a_{\max_{i,j}}>1 \vee a_{\min_{i,j}}<b-1 \implies a'_{\max_{i,j}}=a_{\max_{i,j}}-1,a'_{\min_{i,j}}=a_{\min_{i,j}}+1$ $\bullet a_{\max_{i,j}}=1 \wedge a_{\min_{i,j}}=b-1 \implies \text{erase both of numbers and write 1 in the max (i,j) +1 place}$ Can someone explain what he means

We say that a positive integer $a$ is $k-fancy$ if there exists a multiple of $a$ that can be represented as the sum of $k$ positive integers, each of which is a power of $2$. We call any such representation of a multiple of $a$ a $k-fancy$ representation of $a$. Lemma 1: If $a$ is $k-fancy$, then $a$ is $(k+1)-fancy$ . Proof: Take any $k-fancy$ representation of $a$. If it consists of all $1$s, multiply all the powers of $2$ by $2$ to get another $k-fancy$ representation of $a$. Now, break any power of $2$ greater than $1$ into two parts to get a $(k+1) fancy$ representation of $a$. Lemma 2: Any positive integer $m$ less than $2^{k+1}-1$ is $k-fancy$. Proof: Consider the binary representation of $m$ and use Lemma 1. Lemma 3: $n = 2^{101} - 1$ isn't $100-fancy$ Proof: The possibles values (called residues from now on) of a power of $2$ modulo $n$ are $1, 2, ..., 2^{100}$. Any residue has a corresponding 'successor residue' obtained by multiplying the residue by $2$, with $2^{100}$'s successor residue being $1$. Now, consider any $100-fancy$ representation of $n$. We claim that if such a representation exists, we can get a corresponding $l-fancy$ representation of $n$ with $l \le 100$, such that each power of $2$ in this representation corresponds to a unique residue modulo $n$. This can be achieved if we keep adding two occurrences of the same residue to get a successor residue, and stopping if the successor residue was absent from the representation until now, otherwise repeating the same step again, this time with the newly obtained successor residue, until we obtain a residue which was absent from the representation before. This process is iterated till we get the required $l-representation$. Then, we'd have $\le 100$ distinct residues whose sum is congruent to zero modulo $n$, which is a contradiction considering the equality $1 + 2 +4 + ... 2^{100} = 2^{101} -1$, and we're done. Using Lemmas 2 and 3, the answer is $2^{101} -1$.

My solution: If $n$ has less than $101$ digits in binary representation, then just take $n*2^7$ and use the fact that $2^k$ can be split into $2^{k-1}+2^{k-1}$ to obtain the $100$ numbers. Hence, $n$ must have atleast $101$ digits. The smallest such number is $2^{101}-1$. Suppose a multiple of $2^{101}$ is fancy. This is just equivalent to the multiple having $100$ or fewer ones in binary and being more than $100$. Now just use the fact that $2^{101} \equiv 1$ mod $2^{101}-1$ to see that we can "shift" any of the ones by 101 places to the right (replacing $2^{101+k}$ by $2^k$) and still get a multiple of $2^{101}-1$. Hence, we can eventually get a binary number less than or equal to $2^{101}-1$ having at most 100 ones, and being a multiple of $2^{101}-1$. This is a contradiction, as the largest number satisfying said condition(being less than or equal to $2^{101}-1$, having at most $100$ ones) is $2^{101}-2$. As this contradiction arose on assuming that there is a multiple of $2^{101}-1$ being fancy, we can say that $2^{101}-1$ is the smallest integer satisfying the property that none of its multiples are fancy.

We claim that the answer is $2^{101}-1$. As every positive integer $a$ less than $2^{101}-1$ has at most 100 1's in their binary representation, we can consider $b=\overline{a0a0a\ldots 0a}$ where $a$ is written $\lfloor\frac{100}{s_2(a)}\rfloor$ times; $s_2(b)$ is at least 51 but at most 100, so we can separate exactly $100-s_2(b)$ of the 1's from $2^x$ into $2^{x-1}+2^{x-1}$. Now, it suffices to prove that $s_2(k(2^{101}-1))\ge 101$ for all $k$ which is a subcase of this problem. Turns out that I overcomplicated the first step oops

shinichiman wrote: A positive integer is called fancy if it can be expressed in the form $$2^{a_1}+2^{a_2}+ \cdots+ 2^{a_{n}},$$where $a_1,a_2, \cdots, a_{n}$ are non-negative integers that are not necessarily distinct. Find the smallest positive integer $\chi$ such that no multiple of $\chi$ is a fancy number.(n is prime) Senior Problems Committee of the Australian Mathematical Olympiad Committee We prove the answer is $\boxed{\chi=2^n-1}$ First of we show that $2^n-1$ works.Clearly this is fancy re-write this as $$2^n-1=1+2(1+2(1+2(1+............)))$$i.e $\overline{(\chi)}_2=\underbrace{1111111..........1111}_{n-1}0$ i.e $s_2(\chi) \ge \max(a_i) \stackrel{\text{WLOG}}{=} a_{n-1}$ yet $\;\;\;\;\;\;\;\ \bullet$ If $j$ is even then $s_2(j \chi)=a_{n-1}<a_{n-1}+1$ $\;\;\;\;\;\;\;\ \bullet$ If $j$ is odd then $s_2(j \chi) \le \frac{a_{n-1}}{2}$,contradiction. Moreover for all $\chi<2^n-1$ the $s_2<n-1$,contradiction so we are done.

First, we will rigidly characterize all fancy positive integers. Claim: A positive integer $n$ is fancy if and only if its binary representation contains at most $100$ 1's and the number itself is at least $100$. Let $s_2(n)$ denote the sum of the digits in binary. The smallest number of powers of 2 required to make $n$ is $s_2(n)$, while the largest is $n$. Since we can start with the $s_2(n)$ construction and "split" powers of 2 one at a time, anything in between is achievable. Thus, $n$ is fancy if and only if $$s_2(n)\leq 100\leq n.$$ We claim the answer is $n=2^{101}-1$. For $n\leq 100$, take the smallest multiple of $n$ larger than 100. Then, for $101\leq n\leq 2^{101}-2$, take $n$ itself, as $2^{101}-1$ is the smallest positive integer with more than 100 ones in binary. Thus, it suffices to show that a sum of 100 powers of 2 cannot be divisible by $2^{101}-1$. Since $2^{101}\equiv 1\pmod{2^{101}-1}$, we can WLOG all exponents are at most 100. Note that the first say 2024 multiples of $2^{101}-1$ all have exactly 101 1's in binary, since $$k(2^{101}-1)=k\cdot 2^{101}-k=(k-1)\cdot 2^{101} + (2^{101}-k),$$which means that the stuff above $2^{101}$ will be the compliment string of the stuff after it, and thus contain at total of 101 1's, so none of these multiples are achievable by a sum of 100 powers of 2. Furthermore, since we are WLOGging that each term out of the 100 is at most $2^{100}$, multiples higher than the first 2024 are also not achievable due to size, so we are done.

I claim the answer is $2^{101} - 1$. Let $m$ be the answer to the problem. If $m$ has at most 100 digits in its binary representation, we can multiply it by $2^{\infty}$ and freely split powers of $2$ to fill up to $100$ summands. Thus $m \geq 2^{101} - 1$. Now we show $2^{101} - 1$ suffices. Suppose some multiple $s(2^{101} - 1)$ can be written as $2^{a_1} + \cdots + 2^{a_{100}}$. Let $k$ be minimal over all choices $s$ where $s(2^{101} - 1) = 2^{a_1} + \cdots + 2^{a_k}$, then take the minimal $k$ and choose the minimal $s$. Then in this case, we must have $a_i < 101$ for all $i$ since otherwise we can subtract $2^{a_i - 101} (2^{101} - 1)$ to reduce $s$. Now we furthermore have that for any distinct $i, j$ we have $a_i \neq a_j$ since otherwise $2^{a_i}, 2^{a_j}$ can be combined into $2^{a_i + 1}$ to reduce $k$, giving contradiction. Hence all the $a_i$ are distinct, so since $k \leq 100$ we have $s(2^{101} - 1) < 2^{101} - 1$, giving contradiction as desired. So $m = 2^{101} - 1$.

The answer is $\boxed{2^{101} - 1}$. Suppose $n < 2^{101} - 1$. Fix $b_1, b_2, \ldots, b_k$ as distinct positive integers so that $2^{b_1} + 2^{b_2} + \cdots + 2^{b_k} = n$ and $b_1 < b_2 < \cdots < b_k$ (which is possible by expressing $n$ in binary). Now let $b_{k + 1}$ be a number so that $2^{b_{k+1}} \equiv 2^{b_k} \pmod n$ and $b_{k + 1}$ is greater than $10^{1434}$ (this has to exist because $b_k \ge \nu_2(n)$). Claim: For any positive integers $x > y$, we can write $2^x$ as the sum of $y$ powers of $2$ (not necessarily distinct). Proof: This follows by considering \[2^{x-y} + 2^{x-y } + 2^{x-y + 1} + 2^{x-y + 2} + \cdots + 2^{x - y + (y - 1) } \ \ \ \ \square\] Since $n$ has at most $100$ digits in binary, $k \le 100$. Write $2^{b_{k + 1}}$ as the sum of $101 - k $ powers of $2$. We have that \[ \left( \sum_{i=1}^{k - 1} 2^{b_i} \right) + 2^{b_{k + 1}}\]is both the sum of $100$ powers of $2$ and the same as $\sum_{i=1}^k 2^{b_i} \pmod n$, so $n$ must divide a sum of $100$ powers of $2$, meaning that $n < 2^{101} - 1$ fail. We now show that no multiple of $2^{101} - 1$ is fancy. Suppose otherwise. Perform the following algorithm on the fancy number that is a multiple of $2^{101} - 1$: The list starts at the $100$ powers of $2$ used to make this fancy number. In the first step, take all the exponents modulo $101$. For each move, whenever there are two numbers with the same value in the list, take any two (say they are $2^k$), and replace them with $2^{k + 1}$ if $0 \le k < 100$ and $2^0$ if $k = 100$. Notice that each move preserves the sum of elements in the list modulo $2^{101} - 1$ and the process must terminate (as each move decreases the number of elements in the list). Therefore, once this process finishes, we have at most $100$ distinct powers of $2$ less than $2^{101}$ adding up to a multiple of $2^{101} - 1$, which is absurd since their sum is less than $2^0 + 2^1 + \cdots + 2^{100} = 2^{101} - 1$. Thus, no multiple of $2^{101} -1$ is fancy, and we are done.