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
SMOJ
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.
v_Enhance
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.)
TahsinSaffat
30.06.2014 23:52
Let the beautiful numbers in increasing order be $a_1,a_2,...$ and let $S_k=a_1+_2+...+a_k$. Also, for a positive integer $n$, let $f(n)$ be the sum of the beautiful numbers less than $n$.
Lemma 1: $f(n) \geq \frac{77}{60}n - \frac{317}{60} $
Proof: For a positive integer $r \neq 1$, let $t_r$ be the greatest power of $r$ less than $n$. Then, \[\frac{n}{r} \leq t_r < n\] Then, the sum of the powers of $r$ less than $n$, $j_r$, satisfies, \[j_r = r+r^2+...+t_r = \frac{r}{r-1}(t_r-1) \geq \frac{r}{r-1} \left( \frac{n}{r} -1 \right) = \frac{n-r}{r-1} \] \[j_r \geq \frac{n-r}{r-1}\] Note that $f(n)=j_3+j_4+j_5+j_6$, so applying the above inequality proves the lemma.
Lemma 2: For $k \geq 1$, $a_{k+1} \leq S_k -6$
Proof: We can check that the lemma is true for $k \leq 8$ by hand. Now, we prove the lemma for $k \geq 9$.
Let $k \geq 9$ be a positive integer. We will prove the lemma for $k$. Note that $a_{10}=64$, so $a_{k+1}
\geq 64$. Note that $S_k=f(a_{k+1})$, so by Lemma 1 it suffices to show $a_{k+1} \leq \frac{77}{60} a_{k+1}-\frac{677}{60}$ However, this is true for $a_{k+1} \geq \frac{677}{17}=39.82...$, so we are done.
Now, call an integer $k$-beautiful if it can be expressed as a sum of distinct elements of ${a_1,a_2,...,a_k}$. We show by induction that for $k \geq 4$, every integer in the interval $[3,S_k-3]$ is $k$-beautiful. For the base case, note that all integers in $[3,15]$ can be written as a sum of elements of ${3,4,5,6}$. Now, for the inductive step, assume the hypothesis is true for some $k=m$, where $m \geq 4$. Then, every integer in $[3,S_m-3]$ can be expressed as a sum of some of the first $m$ beautiful numbers. Then, every integer in $[3,S_m-3] \bigcup [3+a_{m+1},S_m-3+a_{m+1}]$ is $m+1$-beautiful. However, by Lemma 2, $S_m-3 \geq 3+a_{m+1}$, so all integers in $[3,S_{m+1}-3]$ are $m+1$-beautiful. Thus, the inductive hypothesis is true for $k=m+1$, so by induction, it is true for all $k \geq 4$. Thus, because beautiful numbers are unbounded, all integers greater than $2$ can be expressed as a sum of distinct beautiful numbers.
tim9099xxzz
01.07.2014 01:51
Let $a$ be the smallest positive integer that cant be represented, and let $w,x,y,z$ be the largest powers of $3,4,5,6$ that are less than $a$. Note that all representations of $a-w$ must contain a $w$, so $a>2w\to a>w+x$. Similarly, all representations of $a-w-x$ must contain either an $x$ or a $w$, so $a>w+2x\to a>w+x+y$. Continuing, we get $a>w+x+y+2z$, which is impossible regardless of the arrangement of $w,x,y,z$. However, this ignores the following difficulty: we may have $a=w+2$, or $a=w+x+y+2$. First suppose we have $a=w+2$. Then let $b_w\in(3,4,5,6)$ be the base of $w$, replace $w$ with $\frac{w}{b_w}$, and proceed as originally (since it will be still be impossible to satisfy $a>w+x+y+2z$ at the end). Suppose now that $a=w+x+2$. Since we had $a>2w$, this would mean $x+2>w$, so $x=w-1$. It follows from the Catalan Conjecture (there's probably a less lazy way to do this)* that this will occur only if $x$ and $w$ are both first-power beautiful numbers. Suppose $a=w+x+y+2$. Since we had $a>w+2x$ this would again imply that two beautiful numbers with power greater than 1 differ by exactly 1, and similarly for the case $a=w+x+y+z+2$. Thus all positive integers a>2 can be expressed as the sum of beautiful numbers.
(*)
1.$4^x-1=3^y$
$3(4^{x-1}...+1)=3^y$
$x=3k, a=4^k-1$
$a(a^2+3a+3)=3^y$
Clearly impossible if $a>0$ since the second term on the left side has to be divisble by more than just $3$.
2. $5^x-1=4^y$
$4(5^{x-1}...+1)=4^y$
$x=4k, a=5^{2k}$
$(a-1)(a+1)=4^y$, clearly impossible
3. $6^x-1=5^y$
$5(6^{x-1}...+1)=5^y$
$x=5k, a=6^k-1$
$a(a^4+5a^3+10a^2+10a+5)=5^y$
Again impossible since the second term on the left has to be divisible by more than just $5$.
The other nine cases are trivial.
dibyo_99
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.
cobbler
25.07.2014 03:54
Let $[x^n]$ denote "the coefficient of $x^n$".
Observe that $[x^n]$ in ${\prod_{k=1}^{\infty} \prod_{a=3}^{6} (1+x^{a^k}})$ gives us the number of ways to represent $n\ge 3$ as the sum of pairwise distinct beautiful numbers. Therefore, the problem boils down to proving that $[x^n]>0\ \forall n\ge 3$. First, we make a key observation.
Key: Notice that if $[x^k]>0$ for $k=0,1,2,...,n$ in $a_0+a_1x+\cdots +a_nx^n$, then in order to prove that $[x^k]>0$ for $k=0,1,2,...,n+m$ in $(a_0+a_1x+\cdots +a_nx^n)(1+x^m)$ with $m<n$, we must only prove that it is $>0$ for $(1+x+x^2+\cdots +x^n )(1+x^m)$. This follows by exponent laws. In other words, the conclusion of the problem isn't hurt by reducing all the coefficients in any intermediate step of the expansion to all $1$'s.
Now to attack the main problem. We proceed by induction.
For the base case, we must show that $[x^n]>0$ in ${\prod_{k=1}^{1} \prod_{a=3}^{6} (1+x^{a^k}})$ for $n=3,4,...,3^1+4^1+5^1+6^1=18$. This follows directly by expansion since $(1+x^3)(1+x^4)(1+x^5)(1+x^6)=1+x^3+x^4+\cdots +x^{18}$ (with the exception of $x^9$ appearing as $2x^9$). It is enough to proceed to the inductive step at this stage, but we will take some time out to quickly show how it will work. To show that $[x^n]>0$ for $n=3,4...,\sum_{i=1}^2 3^i+4^i+5^i+6^i=104$ in ${\prod_{k=1}^{2} \prod_{a=3}^{6} (1+x^{a^k}})$, then by turning the key (I've been reading too much "Prime Obsession" lately ) and the base case, we must only show that it is $>0$ in $(1+x^3+x^4+\cdots +x^{18})(1+x^9)(1+x^{16})(1+x^{25})(1+x^{36})$. We can do this in steps.
For the first step, we do $(1+x^3+x^4+\cdots +x^{18})(1+x^9)=1+x^3+x^4+\cdots +x^{18}+x^9(1+x^3+x^4+\cdots +x^{18})$
$=1+x^3+x^4+\cdots +x^{18}+x^9+x^{10}+\cdots +x^{27}$. Now, since the powers $x^9, x^{10}, ..., x^{18}$ are repeated exactly once, we can omit them once without hurting the desired conclusion (by the key), and end up with $1+x^3+x^4+\cdots +x^{27}$.
Similarly, the second step consists of multiplying this by $1+x^{16}$ to get ("not in practice, but in principle, and by the key"--let this statement be s0) $1+x^3+x^4+\cdots +x^{43}$; this by $1+x^{25}$ to get (s0) $1+x^3+x^4+\cdots +x^{68}$; and finally this by $x^{36}$ to get (s0) $1+x^3+x^4+\cdots +x^{104}$. Thus, $[x^n]>0$ for $n=3,4,...,104$ as required, and we have passed from the base case to the next largest case.
Now for the meat and potatoes of the problem. Assume that the proposition holds for all $3\le n\le \sum_{i=1}^k 3^i+4^i+5^i+6^i$, i.e. $[x^j]>0$ for $j=3,4,...,\sum_{i=1}^k 3^i+4^i+5^i+6^i$ in ${\prod_{n=1}^{k} \prod_{a=3}^{6} (1+x^{a^n}})$. As before, we multiply by $(1+x^{b^{k+1}})$ for $b=3,4,5,6$ respectively. By the key, it suffices to prove that $[x^n]>0$ for $n=3,4,...,\sum_{i=1}^{k+1} 3^i+4^i+5^i+6^i$ in $(1+x^3+x^4+\cdots +x^{\sum_{i=1}^k 3^i+4^i+5^i+6^i})\prod_{a=3}^6 (1+x^{a^{k+1}})$. Actually, we should also at this point let $s_k:=\sum_{i=1}^k 3^i+4^i+5^i+6^i$.
$\bf b=3$. We have $(1+x^3+x^4+\cdots +x^{s_k})(1+x^{3^{k+1}})$
$=1+x^3+x^4+\cdots +x^{s_k}+x^{3^{k+1}}(1+x^3+x^4+\cdots +x^{s_k})$
$=1+x^3+x^4+\cdots +x^{s_k}\color{red} + \color{black} x^{3^{k+1}}+x^{3^{k+1}+3}+x^{3^{k+1}+4}+\cdots +x^{s_k+3^{k+1}}$.
Since the exponents of $x$ to the right of the $\color{red} +$ after $x^{3^{k+1}}$ go up by $1$ (by inductive hypothesis), and since $s_k>3^{k+1}$ (note that $3^k+4^k+5^k+6^k>3^k+3^k+3^k+0=3^{k+1}$), it follows that the powers of $x^n$ for $n=3^{k+1}, 3^{k+1}+3, ..., s_k$ are repeated; once to the left of $\color{red} + \color{black}$ and once to the right. By the key, we may ignore these without hurting the conclusion. Furthermore, since the powers to the right of $\color{red} + \color{black}$ contain all powers of $x$ from $s_k$ to $s_k+3^{k+1}$, it follows that the powers to the right of $\color{red} + \color{black}$ contain $x^n$ for $n=s_k+1,s_k+2,...,s_k+3^{k+1}$ since they increase by $1$. Putting the left of $\color{red} + \color{black}$ and the right of $\color{red} + \color{black}$ together, we end up with $1+x^3+x^4+\cdots +x^{s_k+3^{k+1}}$, and since $[x^n]>0$ for $n=3,4,...,s_k+3^{k+1}$ in this expansion, the result follows for the case $b=3$.
It is not hard to see by the key and the case $b=3$ that, in general, $[x^n]>0$ for $n=3,4,...,n+m$ in $(1+x^3+x^4+\cdots +x^n)(1+x^m)$ if and only if $m<n$. Therefore, we can similarly get that $[x^n]>0$ for $n=3,4,...,s_k+3^{k+1}+4^{k+1}$ for $\bf b=4$; $[x^n]>0$ for $n=3,4,...,s_k+3^{k+1}+4^{k+1}+5^{k+1}$ for $\bf b=5$; 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$.
This completes the induction, and the result follows that $[x^n]>0$ for $n=3,4,...,s_m\ \forall m\in \mathbb{N}$ in ${\prod_{k=1}^{m} \prod_{a=3}^{6} (1+x^{a^k}})$. In particular, letting $m\rightarrow \infty$ we see that there is a positive number of ways to represent all natural numbers $n\ge 3$ as the sum of pairwise distinct beautiful numbers, as desired.
Konigsberg
26.07.2014 19:33
Does anyone else find this easier than problem 1?
lfetahu
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.
SMOJ
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
lfetahu
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.
Olemissmath
05.08.2014 13:24
The truth is #1 and #4 of IMO 2014 were easier than #1 and #3 of BMO 2014 !
cobbler
15.09.2014 12:18
Generalization: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=56&t=606362
JuanOrtiz
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$.
JackXD
06.01.2016 06:58
JuanOrtiz wrote: If $n-W < W$ there is a contradiction How contradiction??
leminscate
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?
WolfusA
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?
MathForesterCycle1
06.06.2021 17:35
dame dame
edfearay123
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$
Sprites
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
Credits to @nbdaaa for this and an Cono Sur which I solved a couple of months before.
Claim:Given the integer sequence $(a_n)$ such that $a_0=1$, $a_1,a_2,a_3,...$ satisfies:
$$a_n \le a_0 +a_1+a_2+...+a_{n-1}$$Prove that all the positive integer can be expressed as the sum of some diffirent elements in the sequence.
Proof: Trival by induction.
Let $N$ be the largest integer we want to express in this form $3^{X_1}+4^{X_2}+5^{X_3}+6^{X_4}$
We will use strong induction on $N$ where the base cases are clear.
Let $x_1>x_2>x_3>x_4$ be the largest powers of $3,4,5,6$ less than $N-3.$
Now we need to prove that $N-(x_1+x_2+x_3+x_4) \ge 3$ by claim 1 but this is obvious since $x_1+x_2+x_3+2x_4 \ge (N-3) \cdot (\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{6})>N-3$ and by induction we are done.$\blacksquare$
SerdarBozdag
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
Credits to @nbdaaa for this and an Cono Sur which I solved a couple of months before.
Claim:Given the integer sequence $(a_n)$ such that $a_0=1$, $a_1,a_2,a_3,...$ satisfies:
$$a_n \le a_0 +a_1+a_2+...+a_{n-1}$$Prove that all the positive integer can be expressed as the sum of some diffirent elements in the sequence.
Proof: Trival by induction.
Let $N$ be the largest integer we want to express in this form $3^{X_1}+4^{X_2}+5^{X_3}+6^{X_4}$
We will use strong induction on $N$ where the base cases are clear.
Let $x_1>x_2>x_3>x_4$ be the largest powers of $3,4,5,6$ less than $N-3.$
Now we need to prove that $N-(x_1+x_2+x_3+x_4) \ge 3$ by claim 1 but this is obvious since $x_1+x_2+x_3+x_4 \ge (N-3) \cdot (\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6})>N-3$ and by induction we are done.$\blacksquare$
$(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$.
Sprites
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
Credits to @nbdaaa for this and an Cono Sur which I solved a couple of months before.
Claim:Given the integer sequence $(a_n)$ such that $a_0=1$, $a_1,a_2,a_3,...$ satisfies:
$$a_n \le a_0 +a_1+a_2+...+a_{n-1}$$Prove that all the positive integer can be expressed as the sum of some diffirent elements in the sequence.
Proof: Trival by induction.
Let $N$ be the largest integer we want to express in this form $3^{X_1}+4^{X_2}+5^{X_3}+6^{X_4}$
We will use strong induction on $N$ where the base cases are clear.
Let $x_1>x_2>x_3>x_4$ be the largest powers of $3,4,5,6$ less than $N-3.$
Now we need to prove that $N-(x_1+x_2+x_3+x_4) \ge 3$ by claim 1 but this is obvious since $x_1+x_2+x_3+x_4 \ge (N-3) \cdot (\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6})>N-3$ and by induction we are done.$\blacksquare$
$(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.
nguyenvuthanhha
19.09.2021 18:13
TahsinSaffat wrote:
Let the beautiful numbers in increasing order be $a_1,a_2,...$ and let $S_k=a_1+_2+...+a_k$. Also, for a positive integer $n$, let $f(n)$ be the sum of the beautiful numbers less than $n$.
Lemma 1: $f(n) \geq \frac{77}{60}n - \frac{317}{60} $
Proof: For a positive integer $r \neq 1$, let $t_r$ be the greatest power of $r$ less than $n$. Then, \[\frac{n}{r} \leq t_r < n\]Then, the sum of the powers of $r$ less than $n$, $j_r$, satisfies, \[j_r = r+r^2+...+t_r = \frac{r}{r-1}(t_r-1) \geq \frac{r}{r-1} \left( \frac{n}{r} -1 \right) = \frac{n-r}{r-1} \]\[j_r \geq \frac{n-r}{r-1}\]Note that $f(n)=j_3+j_4+j_5+j_6$, so applying the above inequality proves the lemma.
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 \}$
ChanandlerBong
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$
emi3.141592
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.
john0512
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.