3^m*2^n representation

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

3^m*2^n representation

G H J

Reveal topic tags

strong induction

L

G H BBookmark kLocked kLocked NReply

Source: BdMO 2023 Secondary National P7

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

136 posts

sman96

#1 h Feb 12, 2023, 2:16 PM • 1 Y

Y by rightways

Prove that every positive integer can be represented in the form $3^{m_1}\cdot 2^{n_1}+3^{m_2}\cdot 2^{n_2} + \dots + 3^{m_k}\cdot 2^{n_k}$ where $m_1 > m_2 > \dots > m_k \geq 0$ and $0 \leq n_1 < n_2 < \dots < n_k$ are integers.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1072 posts

gghx

#2 h Feb 14, 2023, 11:50 AM

Y by

Induct, If it is even add one to every $n_1$ in the representation of $\frac{n}{2}$ , if it is odd remove $3^{\lfloor \log_3(n)\rfloor}$ and add one to every $n_1$ in $\frac{n-3^{\lfloor \log_3(n)\rfloor}}{2}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

136 posts

sman96

#3 h Feb 14, 2023, 12:16 PM

Y by

gghx wrote:

Induct, If it is even add one to every $n_1$ in the representation of $\frac{n}{2}$ , if it is odd remove $3^{\lfloor \log_3(n)\rfloor}$ and add one to every $n_1$ in $\frac{n-3^{\lfloor \log_3(n)\rfloor}}{2}$ .

What if there is a $3^{\lfloor \log_3(n)\rfloor}$ in the representation of $\frac{n-3^{\lfloor \log_3(n)\rfloor}}{2}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1435 posts

#4 h Feb 14, 2023, 1:39 PM

Y by

This is a classic. I prove it by strong induction.

Let $n=2k$ and assume all numbers $1,2,\dots,2k-1$ have such a representation. Letting $k=\textstyle \sum_{1\le i\le k}3^{m_i}2^{n_i}$ , we get $2k= \textstyle \sum_{1\le i\le k}3^{m_i}2^{n_i+1}$ . Assume now $n$ is odd. If $n$ is a power of $3$ , we are done, so assume $a$ is such that $3^a<n<3^{a+1}$ . Note that $n-3^a$ is even, less than $3^a$ , and admits a form above. Adding $3^a$ to this, we complete the proof.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1072 posts

gghx

#6 h Feb 14, 2023, 1:47 PM

Y by

sman96 wrote:

gghx wrote:

Induct, If it is even add one to every $n_1$ in the representation of $\frac{n}{2}$ , if it is odd remove $3^{\lfloor \log_3(n)\rfloor}$ and add one to every $n_1$ in $\frac{n-3^{\lfloor \log_3(n)\rfloor}}{2}$ .

What if there is a $3^{\lfloor \log_3(n)\rfloor}$ in the representation of $\frac{n-3^{\lfloor \log_3(n)\rfloor}}{2}$

$3^{\lfloor \log_3(n)\rfloor}$ is strictly more than $\frac{n-3^{\lfloor \log_3(n)\rfloor}}{2}$ .

This post has been edited 1 time. Last edited by gghx, Feb 14, 2023, 1:48 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

wasikgcrushedbi

52 posts

wasikgcrushedbi

#7 h Feb 20, 2023, 11:55 AM

Y by

grupyorum wrote:

This is a classic. I prove it by strong induction.

Let $n=2k$ and assume all numbers $1,2,\dots,2k-1$ have such a representation. Letting $k=\textstyle \sum_{1\le i\le k}3^{m_i}2^{n_i}$ , we get $2k= \textstyle \sum_{1\le i\le k}3^{m_i}2^{n_i+1}$ . Assume now $n$ is odd. If $n$ is a power of $3$ , we are done, so assume $a$ is such that $3^a<n<3^{a+1}$ . Note that $n-3^a$ is even, less than $3^a$ , and admits a form above. Adding $3^a$ to this, we complete the proof.

How are you sure that theres no $m_i=a$ or $n_i=0$ in the representation of $n-3^a$
(I dont think that if you just take common when theres some $m_i$ or $n_i$ , it will work, at least i wasnt able to take common factors and make it work. So if you would please elaborate this section)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

grey_hat_hacker

12 posts

grey_hat_hacker

#8 h Apr 15, 2023, 5:47 PM

Y by

Strong induction on n

Base case is obvious

If $n=6k= 2^1 * 3^1 * k$ , then k can be represented as the given expression and we have to just add 1 to the power of 2's and 3's

For $n= 6k \pm 2 = 2(3k \pm1)$ , $3k \pm1$ can be expressed as the given expression, we just add 1 to the powers of 2 in the expression to get n

Same goes for n=6k+3

Now for $n=6k \pm 1$ we chose $3^m$ s.t. $3^{m+1} > n$ then, $z= n-3^m$ is even, so we can express $\frac{z}{2}$ as above and multiply by 2 and add $3^m$ to get n

I don't know if this is correct

This post has been edited 4 times. Last edited by grey_hat_hacker, Apr 15, 2023, 5:52 PM
Reason: Latex

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5 posts

#9 h Jan 28, 2025, 2:09 PM

Y by

Hey solve esay other way. This is very difficult.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

16 posts

#10 h Apr 27, 2025, 4:42 PM

Y by

grey_hat_hacker wrote:

Strong induction on n

Base case is obvious

If $n=6k= 2^1 * 3^1 * k$ , then k can be represented as the given expression and we have to just add 1 to the power of 2's and 3's

For $n= 6k \pm 2 = 2(3k \pm1)$ , $3k \pm1$ can be expressed as the given expression, we just add 1 to the powers of 2 in the expression to get n

Same goes for n=6k+3

Now for $n=6k \pm 1$ we chose $3^m$ s.t. $3^{m+1} > n$ then, $z= n-3^m$ is even, so we can express $\frac{z}{2}$ as above and multiply by 2 and add $3^m$ to get n

I don't know if this is correct

It is same with my solution.
but I don't know whether it is valid!

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a