BdMO Online Forum

Posted: **Mon Dec 21, 2020 7:39 pm**

Prove that for all positive integers n there is an n-digit multiple of 5^n all the the digits of which is odd.

Posted: **Mon Dec 21, 2020 11:39 pm**

Thephysimatician wrote: ↑
Mon Dec 21, 2020 7:39 pm
Prove that for all positive integers n there is an n-digit multiple of 5^n all the the digits of which is odd.

We will prove this by induction.
But first, notice that the set of odd digits $\{1,3,5,7,9\}$ is a complete set of residue modulo $5$

Base case : When $n=1$, We have $1$ digit number $5$ which is divisable by $5^1$.

Induction hypothesis : Let's assume we have $n=k$ digit number $b_kb_{k-1}\dots b_1=5^k\cdot a_k$ where $b_i$s are odd digits.

Inductive step : We claim that there exists an odd digit $b_{k+1}$ such that $b_{k+1}b_k\dots b_1$ is divisable by $5^{k+1}$.

Proof : Notice that, if $2^k\cdot x+a_k\equiv 2^k\cdot y+a_k\pmod{5}$,
Then, $x\equiv y\pmod{5}$
So, from a complete set $S$ of residue modulo $5$, there must exist $x\in S$ such that $2^k\cdot x+a_k\equiv0\pmod{5}$
So, there exists $b_{k+1}\in \{1,3,5,7,9\}$ such that $2^k\cdot b_{k+1}+a_{k}$ is divisable by $5$
Now, $b_{k+1}b_k\dots b_1=10^k\cdot b_{k+1}+\left(b_kb_{k-1}\dots b_1\right)=10^k\cdot b_{k+1}+5^k\cdot a_k=5^k\left(2^k\cdot b_{k+1}+a_{k}\right)$, which is divisable by $5^{k+1}$ (Proved)

Posted: **Mon Dec 21, 2020 11:54 pm**

Anindya Biswas wrote: ↑
Mon Dec 21, 2020 11:39 pm

Thephysimatician wrote: ↑
Mon Dec 21, 2020 7:39 pm
Prove that for all positive integers n there is an n-digit multiple of 5^n all the the digits of which is odd.

We will prove this by induction.
But first, notice that the set of odd digits <img src="jsMath/fonts/cmsy10/alpha/100/char66.png" style="height:15px; width:6px; vertical-align:-4px; margin-right:0.068em;">1<img src="jsMath/fonts/cmmi10/alpha/100/char3B.png" style=" width:3px; vertical-align:-3px; margin-right:0.062em;">3<img src="jsMath/fonts/cmmi10/alpha/100/char3B.png" style=" width:3px; vertical-align:-3px; margin-right:0.062em;">5<img src="jsMath/fonts/cmmi10/alpha/100/char3B.png" style=" width:3px; vertical-align:-3px; margin-right:0.062em;">7<img src="jsMath/fonts/cmmi10/alpha/100/char3B.png" style=" width:3px; vertical-align:-3px; margin-right:0.062em;">9<img src="jsMath/fonts/cmsy10/alpha/100/char67.png" style="height:15px; width:6px; vertical-align:-4px; margin-right:0.068em;"> is a complete set of residue modulo 5 

Base case : When n=1 , We have 1 digit number 5 which is divisable by 51 .

Induction hypothesis : Let's assume we have n=k digit number bkbk−1<img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;">b1=5k<img src="jsMath/fonts/cmsy10/alpha/100/char01.png" style=" width:3px; vertical-align:2px; margin-right:0.062em;">ak where bi s are odd digits.

Inductive step : We claim that there exists an odd digit bk+1 such that bk+1bk<img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;">b1 is divisable by 5k+1 .

Proof : Notice that, if 2k<img src="jsMath/fonts/cmsy10/alpha/100/char01.png" style=" width:3px; vertical-align:2px; margin-right:0.062em;">x+ak<img src="jsMath/fonts/cmsy10/alpha/100/char11.png" style=" width:11px; margin-right:-0.013em;">2k<img src="jsMath/fonts/cmsy10/alpha/100/char01.png" style=" width:3px; vertical-align:2px; margin-right:0.062em;">y+ak(mod5) ,
Then, x<img src="jsMath/fonts/cmsy10/alpha/100/char11.png" style=" width:11px; margin-right:-0.013em;">y(mod5) 
So, from a complete set S of residue modulo 5 , there must exist x<img src="jsMath/fonts/cmsy10/alpha/100/char32.png" style=" width:9px; vertical-align:-1px; margin-right:0.019em;">S such that 2k<img src="jsMath/fonts/cmsy10/alpha/100/char01.png" style=" width:3px; vertical-align:2px; margin-right:0.062em;">x+ak<img src="jsMath/fonts/cmsy10/alpha/100/char11.png" style=" width:11px; margin-right:-0.013em;">0(mod5) 
So, there exists bk+1<img src="jsMath/fonts/cmsy10/alpha/100/char32.png" style=" width:9px; vertical-align:-1px; margin-right:0.019em;"><img src="jsMath/fonts/cmsy10/alpha/100/char66.png" style="height:15px; width:6px; vertical-align:-4px; margin-right:0.068em;">1<img src="jsMath/fonts/cmmi10/alpha/100/char3B.png" style=" width:3px; vertical-align:-3px; margin-right:0.062em;">3<img src="jsMath/fonts/cmmi10/alpha/100/char3B.png" style=" width:3px; vertical-align:-3px; margin-right:0.062em;">5<img src="jsMath/fonts/cmmi10/alpha/100/char3B.png" style=" width:3px; vertical-align:-3px; margin-right:0.062em;">7<img src="jsMath/fonts/cmmi10/alpha/100/char3B.png" style=" width:3px; vertical-align:-3px; margin-right:0.062em;">9<img src="jsMath/fonts/cmsy10/alpha/100/char67.png" style="height:15px; width:6px; vertical-align:-4px; margin-right:0.068em;"> such that 2k<img src="jsMath/fonts/cmsy10/alpha/100/char01.png" style=" width:3px; vertical-align:2px; margin-right:0.062em;">bk+1+ak is divisable by 5 
Now, bk+1bk<img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;">b1=10k<img src="jsMath/fonts/cmsy10/alpha/100/char01.png" style=" width:3px; vertical-align:2px; margin-right:0.062em;">bk+1+<img src="jsMath/fonts/cmex10/alpha/100/char00.png" style="height:18px; width:6px; vertical-align:-17px; margin-right:0.026em;">bkbk−1<img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;">b1<img src="jsMath/fonts/cmex10/alpha/100/char01.png" style="height:18px; width:5px; vertical-align:-17px; margin-right:0.098em;">=10k<img src="jsMath/fonts/cmsy10/alpha/100/char01.png" style=" width:3px; vertical-align:2px; margin-right:0.062em;">bk+1+5k<img src="jsMath/fonts/cmsy10/alpha/100/char01.png" style=" width:3px; vertical-align:2px; margin-right:0.062em;">ak=5k<img src="jsMath/fonts/cmex10/alpha/100/char00.png" style="height:18px; width:6px; vertical-align:-17px; margin-right:0.026em;">2k<img src="jsMath/fonts/cmsy10/alpha/100/char01.png" style=" width:3px; vertical-align:2px; margin-right:0.062em;">bk+1+ak<img src="jsMath/fonts/cmex10/alpha/100/char01.png" style="height:18px; width:5px; vertical-align:-17px; margin-right:0.098em;"> , which is divisable by 5k+1 (Proved)

I was just going to write the almost same solution!!! Right now I was writing it while you wrote it first. I guess the saying is right " You snooze you lose"

Posted: **Tue Dec 22, 2020 12:13 am**

Anindya Biswas wrote: ↑
Mon Dec 21, 2020 11:39 pm

Notice that, if $2^k.x+a_k \equiv 2^k.y+a_k(mod5)$,
Then, $x\equiv y(mod5)$
So, from a complete set S of residue modulo 5, there must exist $x\epsilon S$ such that $2^k.x+a_k \equiv 0(mod5)$

But why?

I know what you wrote is true. But is showing $\color{green}{x\equiv y(mod5)}$ enough to tell $\color{green}{2^k.x+a_k \equiv 0(mod5)}$. I don't get how you relate those 2 green statements.

Posted: **Tue Dec 22, 2020 12:29 am**

Mehrab4226 wrote: ↑
Tue Dec 22, 2020 12:13 am

Anindya Biswas wrote: ↑
Mon Dec 21, 2020 11:39 pm

Notice that, if $2^k.x+a_k \equiv 2^k.y+a_k(mod5)$,
Then, $x\equiv y(mod5)$
So, from a complete set S of residue modulo 5, there must exist $x\epsilon S$ such that $2^k.x+a_k \equiv 0(mod5)$
But why?
I know what you wrote is true. But is showing $x\equiv y(mod5)$ enough to tell $2^k.x+a_k \equiv 0(mod5)$. I don't get how you relate those 2 statement.

Yeah, I missed some details. Let's just prove this part.
Let $S=\{2^k\cdot x+a_k | x\in A\}$ where $A$ is a complete residue modulo $5$
So, $S$ must also be a complete residue modulo $5$ since different $x$ produces different $2^k\cdot x+a_k$ modulo $5$.
So, there must exists $x$ for which $2^k\cdot x+a_k\equiv0\pmod{5}$

Posted: **Tue Dec 22, 2020 12:35 am**

I got it. You actually simplified it. Guess what I was going to write in my solution. CASE WORK! For all kinds of values of $2^k$,$x$ and $a_k$. Which is really inefficient. You won this round not only by solving it faster but also by more elegant and efficient solution.

BdMO Online Forum

A problem from USAMO 2003

A problem from USAMO 2003

Re: A problem from USAMO 2003

Re: A problem from USAMO 2003

Re: A problem from USAMO 2003

Re: A problem from USAMO 2003

Re: A problem from USAMO 2003