Prove that every positive integer can be represented in the form \[3^{u_1} \ldots 2^{v_1} + 3^{u_2} \ldots 2^{v_2} + \ldots + 3^{u_k} \ldots 2^{v_k}\] with integers $u_1, u_2, \ldots , u_k, v_1, \ldots, v_k$ such that $u_1 > u_2 >\ldots > u_k\ge 0$ and $0 \le v_1 < v_2 <\ldots < v_k$.
Problem
Source: ToT 2003-SA-2
Tags: induction, number theory unsolved, number theory
goodar2006
19.06.2011 08:34
I think induction will work, if $n=2k$, then there is a representation for $k$ with the above condition, so there is one for $n$, and if $n$ is odd, and $3^a$ is the largest power of $3$ not exceeding $n$, then $n-3^a$ has a representation, so has $n$.
pco
19.06.2011 09:30
goodar2006 wrote: ...$n-3^a$ has a representation, so has $n$. Not so simple : Maybe the representation of $n-3^a$ is $3^b+\prod 3^{u_k}2^{v_k}$ and so just adding $3^a$ does not gives a legal representation since the two summands $3^a$ and $3^b$ will have the same power of two ($2^0$) which is not allowed.
mavropnevma
19.06.2011 11:17
No, pco. You missed the fact that goodar2006 only does the trick with $3^a$ for odd $n$; then $n-3^a$ will be even, and so your representation cannot be. In fact now we apply the start of goodar's proof: we write $n-3^a = 2k$ and use a representation for $k$. This is also an Erdös problem. He stated it as to prove that any positive integer can be written as a sum of monomials $2^a3^b$, so that none divides another, which is equivalent to the problem at hand.
pco
19.06.2011 11:35
mavropnevma wrote: No, pco. You missed the fact that goodar2006 only does the trick with $3^a$ for odd $n$; then $n-3^a$ will be even, and so your representation cannot be. In fact now we apply the start of goodar's proof: we write $n-3^a = 2k$ and use a representation for $k$. You're right , as usual