Easiest problem of Apmo
Prove that $(36a+b)(36b+a)$ can never be a power of $2$
One one thing is neutral in the universe, that is $0$.
Re: Easiest problem of Apmo
@মাসুম- সমস্যাকে সহজ/কঠিন বলে বিশেষায়িত না করাই ভাল, কারণ ফোরামে বিভিন্ন দক্ষতার ছাত্র-ছাত্রী থাকবে, তারা এতে নিরুৎসাহিত বোধ করতে পারে।
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.
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
Re: Easiest problem of Apmo
I meant it easy with respect to APMO,not at all from me.Avik Roy wrote:মাসুম- সমস্যাকে সহজ/কঠিন বলে বিশেষায়িত না করাই ভাল, কারণ ফোরামে বিভিন্ন দক্ষতার ছাত্র-ছাত্রী থাকবে, তারা এতে নিরুৎসাহিত বোধ করতে পারে।
.
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$
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$.
Re: Easiest problem of Apmo
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
Re: Easiest problem of Apmo
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$.
Re: Easiest problem of Apmo
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$.
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)
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)
Re: Easiest problem of Apmo
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)
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)
Re: Easiest problem of Apmo
Why is that so? :SZzzz 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$.
What did I miss?
"Go down deep enough into anything and you will find mathematics." ~Dean Schlicter
Re: Easiest problem of Apmo
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$.
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)
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)
Re: Easiest problem of Apmo
except the factor $1$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$.
One one thing is neutral in the universe, that is $0$.