Define a beautiful number to be an integer of the form $a^n$, where $a\in\{3,4,5,6\}$ and $n$ is a positive integer. Prove that each integer greater than $2$ can be expressed as the sum of pairwise distinct beautiful numbers. Proposed by Matthew Babbitt
Problem
Source: ELMO 2014, Problem 2, by Matthew Babbitt
Tags: inequalities, induction, number theory, number theory unsolved
30.06.2014 17:12
Someone said that noting that $\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{9}>1$ is the key idea.
30.06.2014 17:21
This is indeed a crucial step in the solution I gave to this problem. (There seem to be a couple different solutions.)
30.06.2014 23:52
01.07.2014 01:51
05.07.2014 10:45
Even though the idea remains the same, I'll post my proof which is essentially the same as tim's without the messy cases and stuff (mainly because I am temporarily jobless). My claim is a bit stronger - I'll show that every natural number $>6$ can be expressed as a sum of distinct beautiful numbers smaller than itself. Suppose, for the sake of argument, that $n$ is the smallest positive integer that cannot be expressed as a sum of smaller distinct beautiful numbers. Let $a<b<c<d$ be the largest powers of $3,4,5$ and $6$ in some order, $\le n-3$. Note that \[2a+b+c+d = (a+b+c+d)+a > (n-3) \left( \frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{6} \right) > n-3\]We can write $n = (n-d)+d$ (both terms are $\ge 3$) and therefore, $d$ must occur in the representation of $n-d$. All numbers $<d$ and $d+1,d+2$ don't have $d$ in their representation. Due to minimality, $d$ doesn't contain $d$ in its representation either. Therefore, $n-d \ge d+3$ $ \implies n \ge 2d+3> d+c+3$. Repeating the same argument, $n-d-c \ge c+3$ $ \implies n \ge 2c+d+3$ $ > b+c+d+3$. Continuing this way, we have $n \ge 2a+b+c+d + 3 > (n-3)+3=n$, contradiction.
25.07.2014 03:54
26.07.2014 19:33
Does anyone else find this easier than problem 1?
30.07.2014 16:55
Actually, I solved the first problem, which is the system of functional equations. But I didn't solve this problem, although I clearly got the idea of how to induct. This problem really surprised me, since I had solved before IMO 2012 #6, much harder than this. But, this is ELMO at all, you see problems of good quality.
30.07.2014 16:59
Well, you are a honourable mention receiver and I am pretty sure all people in MOP can get at least your score. I probably can do only 1 question though
30.07.2014 20:34
SMOJ wrote: Well, you are a honourable mention receiver and I am pretty sure all people in MOP can get at least your score. I probably can do only 1 question though Honestly, I highly doubt in the truth behind your words. Without making any silly assumption, I want to point out the fact that the success in math olympiads, such as IMO, depends highly in the selection of the problems: it depends in the number of the problems from a specific field, and in the position of a problem. For this reason, I think that one's result in a math olympiad is never predictable. Your phrase "I am pretty sure all people in MOP can get at least your score, I probably can do only 1 question" is 100% not based in stats and facts, and consequently not believable. So, what can be said is that I GUESS (NOT I AM PRETTY SURE, NEVER SAY IT), or IN MY OPINION, most of those who attend MOP can get at least 1-2 problems, and a few of them can get less than that, so 0-1 problem (which is 0-7 points). But, even the previous statement is questionable, because it's truth 1) depends in one's definition of "most of those", and 2) in the skills of the contestants. So, there may be a considerable possibility that many of MOPpers can score no more than 3-4 points in IMO. The motivation that I'm pointing out these facts, is that I've noticed a few interesting things in IMO 2014, and in general in all IMOs. The first is that I came at this year's IMO with the goal of solving at least 3 problems, which means scoring 21 points in the worst case that could happen, but normally I was fighting for a silver medal (22 points or more). But guess what: my weak fields, geometry and combinatorics, punished me heavily. My bad luck was that there was no number theory, which stopped me from getting that silver; AND there was ONLY 1 algebra and moreover it was a #1 (which means extremely easy); AND there were 3 COMBOS and 2 GEOS, which mean "EXTREMELY UNLUCKY" for me. In the worst case (that was definitely the worst case, because there was no number theory), I would prefer as a #2 or #5 an algebra problem, and 2 algebras would be very nice, but even in these things I was let down by the fate. So, with some good luck I could even win the gold medal, but as you can see I didn't even win the bronze, which is a very bad story for me (I want to forget my experience in IMO 2014). But, IF IT WAS THE END OF THE WORLD, I would like a C #1 and that A #1 would better be a #2 or #5, because this way I could get out of the contest with 3 full problems. Secondly, I'm repeating: don't be sure for the MOPpers and yourself. There is the risk that, if you participated in IMO 2014, you could get 0 points as well as some contestants who did. It is interesting to see that Alex Song, an extremely great performer in the last 4 IMOs, couldn't get full 7 points in the first problem at IMO 2010. And that first problem is definitely one of the easiest functional equations of all IMOs, but I'm not going to make any remark on how short its solution is. I just want to point out that Alex Song, 4-time gold medallist, scored 5 points in that problem and he also got only 1 point in the second problem, which was indeed an easy geometry problem. But, you can also focus in the IMO 2014 results: observe yourself and find that there are many good contestants from traditional strong countries that haven't received much points in #1 and #4 this year, and judge whether if it is a surprise or not. Thirdly, this year there were some contestants who were punished only by a few points to get gold medals, and there were others who suffered the selection of that #6. For example, I thought (as in your post for MOPpers and yourself) that v_Enhance would be a perfect scorer this year, but he was unlucky: the #6 appeared to be fatal for him. If there was a number theory, geometry or an algebra problem instead of that #6, v_Enhance would probably be a perfect scorer. So, don't make any predictions if you don't know the situation in details. This lesson is especially for people like you, who have not participated in IMO and don't know its secrets.
05.08.2014 13:24
The truth is #1 and #4 of IMO 2014 were easier than #1 and #3 of BMO 2014 !
15.09.2014 12:18
Generalization: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=56&t=606362
12.04.2015 04:25
Let $n$ be the smallest number not expressible as the sum of distinct beautiful numbers. Let $W,X,Y,Z$ be the biggest powers of $3,4,5,6$ that are smaller than $n-2$, in order such that $W > X > Y > Z$. If $n-W < W$ there is a contradiction, otherwise if $n-W-X<X$ there is a contradiction, otherwise if $n-W-X-Y<Y$ there is a contradiction, otherwise if $n-W-X-Y-Z<Z$ there is a contradiction. Therefore $n-W-X-Y-Z \ge Z$. But notice that the biggest power of $k$ that is smaller than $n$ is bigger than or equal to $n/k$, and therefore $n \ge W+X+Y+2Z \ge n(\frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{2}{6}) > n(1.1) > n$, contradiction. Therefore $n$ does not exist so we win. Some minor details are needed in case $n-W-X=1$ or something, so just check small $n$.
06.01.2016 06:58
JuanOrtiz wrote: If $n-W < W$ there is a contradiction How contradiction??
27.12.2016 06:29
arkanm wrote: and $[x^n]>0$ for $n=3,4,...,s_k+3^{k+1}+4^{k+1}+5^{k+1}+6^{k+1}$ for $\bf b=6$. Unfortunately I don't think this works, because we'll need $3^{k+1}+4^{k+1}+5^{k+1}+3^k+4^k+5^k+6^k \geq 6^{k+1}+2$, which is not true for sufficiently large $k$. To fix this solution we would have to arrange the beautiful numbers in an order $a_1, a_2, \cdots$ such that $a_1+a_2+\cdots +a_k\geq a_{k+1}+2$, which should be possible, but I haven't proved it yet. Can anybody fix the solution or am I wrong that it doesn't work?
12.06.2019 14:55
Official solution wrote: the construction for $N$' cannot use any of $\lbrace{x_1,...,x_k\rbrace}$ since $N$'$-x_k <3$. What if $x_k=N'$? Do you still claim above sentence?
06.06.2021 17:35
dame dame
27.07.2021 03:39
What refers with distinct pairwise? (a, b) and (c,d) are differents if at least $a \neq c$ or $b \neq d$
18.09.2021 20:58
v_Enhance wrote: Define a beautiful number to be an integer of the form $a^n$, where $a\in\{3,4,5,6\}$ and $n$ is a positive integer. Prove that each integer greater than $2$ can be expressed as the sum of pairwise distinct beautiful numbers. Proposed by Matthew Babbitt
19.09.2021 17:04
Sprites wrote: v_Enhance wrote: Define a beautiful number to be an integer of the form $a^n$, where $a\in\{3,4,5,6\}$ and $n$ is a positive integer. Prove that each integer greater than $2$ can be expressed as the sum of pairwise distinct beautiful numbers. Proposed by Matthew Babbitt
$(N-3) \cdot (\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6})>N-3$. This is not true because $\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}=0.95$.
19.09.2021 17:17
SerdarBozdag wrote: Sprites wrote: v_Enhance wrote: Define a beautiful number to be an integer of the form $a^n$, where $a\in\{3,4,5,6\}$ and $n$ is a positive integer. Prove that each integer greater than $2$ can be expressed as the sum of pairwise distinct beautiful numbers. Proposed by Matthew Babbitt
$(N-3) \cdot (\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6})>N-3$. This is not true because $\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}=0.95$. Fixed this.
19.09.2021 18:13
TahsinSaffat wrote:
I think that this solution is not correct. The beautiful number can be sum of multiples of $3$ and $4;5;6$ In your solution, you misunderstood that beautiful number can only be sum of multiples of one in $\{3;4;5;6 \}$
24.08.2023 17:27
Suppose $3=x_1<x_2<x_3<\dots$ are all beautiful numbers in increasing order. Claim: For $n\geq 4$, each integer in the set $$S_n:=\{3,4,\dots,2+\max\{x_{n+1},x_{n+2}-x_{n+1},x_{n+3}-x_{n+2}-x_{n+1},x_{n+4}-x_{n+3}-x_{n+2}-x_{n+1}\}\}$$can be expressed as the sum of the elements of a subset of $\{x_1,x_2,\dots,x_n\}$. Obviously the claim is an instant kill for the problem. Proof of the claim: Induct on $n$. The case $n=4$ is checked by hand. Assume the claim holds for $n\geq 4$. Let $K$ be the set of integers that can be expressed as the sum of the elements of a subset of $\{x_1,x_2,\dots,x_{n+1}\}$ , then $K\supset S_n\cup (S_n+x_{n+1})$. Note that $$x_{n+1}+(x_{n+2}-x_{n+1})\geq x_{n+2}$$$$x_{n+1}+(x_{n+3}-x_{n+2}-x_{n+1})\geq x_{n+3}-x_{x+2}$$$$x_{n+1}+(x_{n+4}-x_{n+3}-x_{n+2}-x_{n+1})\geq x_{n+4}-x_{n+3}-x_{n+2}$$For $a\in \{3,4,5,6\}$, consider the beautiful numbers $a^p$ where $a^p<x_{n+5}\leq a^{p+1}$. Thus there exist four distinct beautiful numbers $x_{i_a}$, such that $i_a<n+5$ and $x_{i_a}\geq \frac{x_{n+5}}{a}$. Therefore $2x_{n+1}+x_{n+2}+x_{n+3}+x_{n+4}\geq x_{n+5}(\frac{2}{6}+\frac{1}{5}+\frac{1}{4}+\frac{1}{3})\geq x_{n+5}$, which shows that $$x_{n+1}+x_{n+1}\geq x_{n+5}-x_{n+4}-x_{n+3}-x_{n+2}$$Hence the claim is also true for $n+1$. $\blacksquare$
05.09.2024 04:52
Suppose there exists a positive integer $N$ greater than two that is not the sum of pairwise distinct beautiful numbers. Let $N$ be the smallest integer that does not satisfy this property. It is easy to verify that $3, 4, 5, 6, 7, 8$ satisfy the property, so $N \geq 9$. Now, let $D > B > C > A$ be the largest powers of $3, 4, 5, 6$ less than $N-2$ in some order. Observe that $N-D \geq D$, because if $N-D < D$, then $N-D$ would have a representation as a sum of beautiful numbers that does not contain $D$, so $(N-D) + D = N$ would also have such a representation. By the same argument, we would have $N-D-C \geq C$, because if this were not the case, $(N-D-C) + (D + C)$ would have a representation as a sum of beautiful numbers. Similarly, we would have $(N-D-C-B) \geq B$ and $(N-D-C-B-A) \geq A$, from which we obtain: \[ N = D + B + C + 2A \geq N \left( \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{2}{6} \right) > N. \]Which is not possible. We are done.
28.09.2024 02:15
Let $b_n$ denote the $n$th smallest beautiful number. Note that $3,4,5,6$ together cover everything from $3$ to $15$. The idea is that, if we allow a new beautiful number $b$, the range shifted up by $b$ will also work, and as long as $b$ isn't too large there won't be a gap. Thus, we show the following claim. Claim: For all positive integers $n\geq 5$, we have $$b_{n}\leq b_1+b_2+\dots+b_{n-1}-6.$$ We have $$b_5=9,b_6=16,b_7=25,b_8=27,b_9=36,$$which all satisfy the claim. Assume $b_n\geq 40$ from now on. The largest power of $3$ below $b_n$ is at least $\frac{b_n}{3}$. Thus, the sum of powers of $3$ under $b_n$ is at least $$3+3^2+\dots +3^{\lceil \log_{3}b_n\rceil -1}=\frac{3^{\lceil \log_{3}b_n\rceil}-3}{2}\geq \frac{b_n-3}{2}.$$Repeating this with $4,5,6$, the sum of beautiful numbers less than $b_n$ is at least $$\frac{b_n-3}{2}+\frac{b_n-4}{3}+\frac{b_n-5}{4}+\frac{b_n-6}{5}.$$If $b_n\geq 40$, then this is at least $b_n+6$, as desired. Now, we finish by induction. Suppose that $b_1$ through $b_{n}$ cover everything from $3$ to $b_1+\dots +b_n-3$. We know this is true for $n=4$. Now, due to the above claim, for any $s$ covered by $b_1$ through $b_n$, if we add in $b_{n+1}$, $s+b_{n+1}$ is also covered. Thus, as $b_{n+1}\leq b_1+\dots +b_n-6$, no gap is left, so we now cover everything from $3$ to $b_1+\dots +b_n+b_{n+1}-3$. We are done.