Easiest problem of Apmo

Discussion on Asian Pacific Mathematical Olympiad (APMO)
User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh
Easiest problem of Apmo

Unread post by Masum » Thu Dec 09, 2010 4:46 am

Prove that $(36a+b)(36b+a)$ can never be a power of $2$
One one thing is neutral in the universe, that is $0$.

User avatar
Avik Roy
Posts:156
Joined:Tue Dec 07, 2010 2:07 am

Re: Easiest problem of Apmo

Unread post by Avik Roy » Sat Dec 11, 2010 1:07 am

@মাসুম- সমস্যাকে সহজ/কঠিন বলে বিশেষায়িত না করাই ভাল, কারণ ফোরামে বিভিন্ন দক্ষতার ছাত্র-ছাত্রী থাকবে, তারা এতে নিরুৎসাহিত বোধ করতে পারে।

As it was in the original problem the solution for positive $a$ and $b$ follows:

Let,
$36a+b=2^p$
$a+36b=2^q$
Without loss of generalization, let $p>q$. Hence,
$37(a+b)=2^q(2^{p-q}+1)$
and $35(a-b)=2^q(2^{p-q}-1)$
From this we can deduce that,
$2^{p-q}+1=d.37$
and $2^{p-q}-1=f.35$
Thus $a+b=d.2^q$
and $a-b=e.2^q$
where $37d-35e=2$
It can be easily seen that $e \ge d$ and that leaves us with $b$ being negative.
"Je le vois, mais je ne le crois pas!" - Georg Ferdinand Ludwig Philipp Cantor

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: Easiest problem of Apmo

Unread post by Masum » Sat Dec 11, 2010 8:08 pm

Avik Roy wrote:মাসুম- সমস্যাকে সহজ/কঠিন বলে বিশেষায়িত না করাই ভাল, কারণ ফোরামে বিভিন্ন দক্ষতার ছাত্র-ছাত্রী থাকবে, তারা এতে নিরুৎসাহিত বোধ করতে পারে।

.
I meant it easy with respect to APMO,not at all from me. :)
Now I am posting solutions using different ideas.
First solution(my,using Fermat's Method Of Descent or Infinite Descent or Descent Inifini):Obviously $a,b$ even,let $a=2a_1,b=2b_2$.Then $(36a+b)(36b+a)=2^2(36a_1+b_1)(36b_1+a_1)$.Again $a_1,b_1$ even and $(36a_1+b_1)(36b_1+a_1)$ is a power of $2$.So let $a_1=2a_2,b_1=2b_2$,then $(36a_2+b_2)(36b_2+a_2)$ is a power of $2,....,a=2^na_n,b=2^nb_n$ for all $n$.This means $a=b=0$
We get an infinite decreasing sequence of positive integers $a_1,a_2,...$
Second solution(Official,using Extremal Principle):Let $(a,b)$ to be the smallest pair such that $(36a+b)(36b+a)$ is a power of $2,$let $a=2x,b=2y$.Then $(36x+y)(36y+x)$ is a power of $2,$contradictiong the minimality of $a,b$
Hint to third solution:let $a=2^kx,b=2^ly$ with $x,y$ odd.Now replace them in the original expression and see what happens.
One one thing is neutral in the universe, that is $0$.

User avatar
Avik Roy
Posts:156
Joined:Tue Dec 07, 2010 2:07 am

Re: Easiest problem of Apmo

Unread post by Avik Roy » Sun Dec 12, 2010 1:38 am

The solutions using infinite descent and extremal principle are seemingly of the same essence
"Je le vois, mais je ne le crois pas!" - Georg Ferdinand Ludwig Philipp Cantor

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: Easiest problem of Apmo

Unread post by Masum » Sun Dec 12, 2010 1:50 am

Yes,my solution is a variation of the official one but smarter than mine.
One one thing is neutral in the universe, that is $0$.

User avatar
Zzzz
Posts:172
Joined:Tue Dec 07, 2010 6:28 am
Location:22° 48' 0" N / 89° 33' 0" E

Re: Easiest problem of Apmo

Unread post by Zzzz » Sun Dec 12, 2010 6:55 am

Hey, I got the $5^{th}$ solution also. But I couldn't post it as I didn't know that $a,b>0$ :(

Here it is:
Obviously $(36a+b)=2^m$ and $(36b+a)=2^n$ for some $m,n$.

WLOG, let $m\ge n$

\[\therefore 2^n|2^m\]
\[\Rightarrow 2^n|36a+b\]
\[\Rightarrow 2^n|(36a+b)+2^n\]
\[\Rightarrow 2^n|(36a+b)+(36b+a)\]
\[\Rightarrow 2^n|37(a+b)\]

As, $gcd(2^n,37)=1$ \[2^n|a+b\]
\[\Rightarrow 2^n\le a+b\]
\[\Rightarrow 36b+a\le a+b\]
\[\Rightarrow b\le 0\]

This solution also shows that $(36a+b)(36b+a)$ can never be a power of $p$. Here $a,b>0$ and $p$ is any prime except $37$.
Every logical solution to a problem has its own beauty.
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)

User avatar
Zzzz
Posts:172
Joined:Tue Dec 07, 2010 6:28 am
Location:22° 48' 0" N / 89° 33' 0" E

Re: Easiest problem of Apmo

Unread post by Zzzz » Sun Dec 12, 2010 7:31 am

I meant, with same arguments, we can show...
Every logical solution to a problem has its own beauty.
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)

User avatar
TIUrmi
Posts:61
Joined:Tue Dec 07, 2010 12:13 am
Location:Dinajpur, Bangladesh
Contact:

Re: Easiest problem of Apmo

Unread post by TIUrmi » Sun Dec 12, 2010 7:06 pm

Zzzz wrote:Hey, I got the $5^{th}$ solution also. But I couldn't post it as I didn't know that $a,b>0$ :(

Here it is:
Obviously $(36a+b)=2^m$ and $(36b+a)=2^n$ for some $m,n$.
Why is that so? :S
What did I miss?
"Go down deep enough into anything and you will find mathematics." ~Dean Schlicter

User avatar
Zzzz
Posts:172
Joined:Tue Dec 07, 2010 6:28 am
Location:22° 48' 0" N / 89° 33' 0" E

Re: Easiest problem of Apmo

Unread post by Zzzz » Sun Dec 12, 2010 7:26 pm

Ops, I forgot to state that, its a proof by contradiction. First I assumed that $(36a+b)(36b+a)=2^k$ for some $k$. Then I showed $b\le 0$.

If $Z=(36a+b)(36b+a)$ is a power of $2$, all the factors of $Z$ must be power of $2$.
Every logical solution to a problem has its own beauty.
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: Easiest problem of Apmo

Unread post by Masum » Sun Dec 12, 2010 8:19 pm

Zzzz wrote:Ops, I forgot to state that, its a proof by contradiction. First I assumed that $(36a+b)(36b+a)=2^k$ for some $k$. Then I showed $b\le 0$.

If $Z=(36a+b)(36b+a)$ is a power of $2$, all the factors of $Z$ must be power of $2$.
except the factor $1$
One one thing is neutral in the universe, that is $0$.

Post Reply