A problem from USAMO 2003

For discussing Olympiad Level Number Theory problems
Thephysimatician
Posts:6
Joined:Sun Dec 13, 2020 6:51 pm
A problem from USAMO 2003

Unread post by Thephysimatician » 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.

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: A problem from USAMO 2003

Unread post by Anindya Biswas » 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)
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: A problem from USAMO 2003

Unread post by Mehrab4226 » 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 <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:5.339em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><img src="jsMath/fonts/cmsy10/alpha/100/char66.png" style="height:15px; width:6px; vertical-align:-4px; margin-right:0.068em;"><span class="icmr10">1</span><img src="jsMath/fonts/cmmi10/alpha/100/char3B.png" style=" width:3px; vertical-align:-3px; margin-right:0.062em;"><span style="position: relative; margin-left:0.166em;"><span class="icmr10">3</span></span><img src="jsMath/fonts/cmmi10/alpha/100/char3B.png" style=" width:3px; vertical-align:-3px; margin-right:0.062em;"><span style="position: relative; margin-left:0.166em;"><span class="icmr10">5</span></span><img src="jsMath/fonts/cmmi10/alpha/100/char3B.png" style=" width:3px; vertical-align:-3px; margin-right:0.062em;"><span style="position: relative; margin-left:0.166em;"><span class="icmr10">7</span></span><img src="jsMath/fonts/cmmi10/alpha/100/char3B.png" style=" width:3px; vertical-align:-3px; margin-right:0.062em;"><span style="position: relative; margin-left:0.166em;"><span class="icmr10">9</span></span><img src="jsMath/fonts/cmsy10/alpha/100/char67.png" style="height:15px; width:6px; vertical-align:-4px; margin-right:0.068em;"> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:1.104em;vertical-align:-0.3em"></span></span></nobr></span> is a complete set of residue modulo <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:0.526em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmr10">5</span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:0.854em;vertical-align:-0.05em"></span></span></nobr></span>

Base case : When <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:2.105em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmmi10">n</span><span style="position: relative; margin-left:0.277em;"><span class="icmr10">=</span></span><span style="position: relative; margin-left:0.277em;"><span class="icmr10">1</span></span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:0.854em;vertical-align:-0.05em"></span></span></nobr></span>, We have <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:0.526em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmr10">1</span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:0.854em;vertical-align:-0.05em"></span></span></nobr></span> digit number <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:0.526em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmr10">5</span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:0.854em;vertical-align:-0.05em"></span></span></nobr></span> which is divisable by <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:0.902em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmr10">5</span><span style="position: relative; top:-0.362em;"><span class="size2"><span class="icmr10">1</span></span><span class="spacer" style="margin-left:0.05em"></span></span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:0.944em;vertical-align:-0.05em"></span></span></nobr></span>.

Induction hypothesis : Let's assume we have <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:2.105em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmmi10">n</span><span style="position: relative; margin-left:0.277em;"><span class="icmr10">=</span></span><span style="position: relative; margin-left:0.277em;"><span class="icmmi10">k</span><span class="spacer" style="margin-left:0.031em"></span></span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:0.854em;vertical-align:-0.05em"></span></span></nobr></span> digit number <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:8.498em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.022em"></span><span class="size2"><span class="icmsy10">−</span><span class="icmr10">1</span></span><span class="spacer" style="margin-left:0.05em"></span></span><span style="position: relative; margin-left:0.166em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"><span style="position: relative; margin-left:0.166em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"></span><span style="position: relative; margin-left:0.166em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"></span></span><span style="position: relative; margin-left:0.166em;"><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmr10">1</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span><span style="position: relative; margin-left:0.277em;"><span class="icmr10">=</span></span><span style="position: relative; margin-left:0.277em;"><span class="icmr10">5</span><span style="position: relative; top:-0.362em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span><span style="position: relative; margin-left:0.222em;"><img src="jsMath/fonts/cmsy10/alpha/100/char01.png" style=" width:3px; vertical-align:2px; margin-right:0.062em;"></span><span style="position: relative; margin-left:0.222em;"><span class="icmmi10">a</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:1.277em;vertical-align:-0.336em"></span></span></nobr></span> where <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:0.752em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">i</span></span><span class="spacer" style="margin-left:0.05em"></span></span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:1.076em;vertical-align:-0.318em"></span></span></nobr></span>s are odd digits.

Inductive step : We claim that there exists an odd digit <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:1.654em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.022em"></span><span class="size2"><span class="icmr10">+1</span></span><span class="spacer" style="margin-left:0.05em"></span></span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:1.141em;vertical-align:-0.336em"></span></span></nobr></span> such that <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:4.888em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.022em"></span><span class="size2"><span class="icmr10">+1</span></span><span class="spacer" style="margin-left:0.05em"></span></span><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span><span style="position: relative; margin-left:0.166em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"><span style="position: relative; margin-left:0.166em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"></span><span style="position: relative; margin-left:0.166em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"></span></span><span style="position: relative; margin-left:0.166em;"><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmr10">1</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:1.141em;vertical-align:-0.336em"></span></span></nobr></span> is divisable by <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:1.654em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmr10">5</span><span style="position: relative; top:-0.362em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.022em"></span><span class="size2"><span class="icmr10">+1</span></span><span class="spacer" style="margin-left:0.05em"></span></span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:0.990em;vertical-align:-0.05em"></span></span></nobr></span>.

Proof : Notice that, if <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:13.537em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmr10">2</span><span style="position: relative; top:-0.362em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span><span style="position: relative; margin-left:0.222em;"><img src="jsMath/fonts/cmsy10/alpha/100/char01.png" style=" width:3px; vertical-align:2px; margin-right:0.062em;"></span><span style="position: relative; margin-left:0.222em;"><span class="icmmi10">x</span></span><span style="position: relative; margin-left:0.222em;"><span class="icmr10">+</span></span><span style="position: relative; margin-left:0.222em;"><span class="icmmi10">a</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span><span style="position: relative; margin-left:0.277em;"><img src="jsMath/fonts/cmsy10/alpha/100/char11.png" style=" width:11px; margin-right:-0.013em;"></span><span style="position: relative; margin-left:0.277em;"><span class="icmr10">2</span><span style="position: relative; top:-0.362em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span><span style="position: relative; margin-left:0.222em;"><img src="jsMath/fonts/cmsy10/alpha/100/char01.png" style=" width:3px; vertical-align:2px; margin-right:0.062em;"></span><span style="position: relative; margin-left:0.222em;"><span class="icmmi10">y</span><span class="spacer" style="margin-left:0.035em"></span></span><span style="position: relative; margin-left:0.222em;"><span class="icmr10">+</span></span><span style="position: relative; margin-left:0.222em;"><span class="icmmi10">a</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span><span style="position: relative; margin-left:1em;"><span class="icmr10">(</span></span><span class="icmr10">mod</span><span style="position: relative; margin-left:0.333em;"><span class="icmr10">5</span></span><span class="icmr10">)</span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:1.277em;vertical-align:-0.336em"></span></span></nobr></span>,
Then, <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:6.543em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmmi10">x</span><span style="position: relative; margin-left:0.277em;"><img src="jsMath/fonts/cmsy10/alpha/100/char11.png" style=" width:11px; margin-right:-0.013em;"></span><span style="position: relative; margin-left:0.277em;"><span class="icmmi10">y</span><span class="spacer" style="margin-left:0.035em"></span></span><span style="position: relative; margin-left:1em;"><span class="icmr10">(</span></span><span class="icmr10">mod</span><span style="position: relative; margin-left:0.333em;"><span class="icmr10">5</span></span><span class="icmr10">)</span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:1.054em;vertical-align:-0.25em"></span></span></nobr></span>
So, from a complete set <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:0.601em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmmi10">S</span><span class="spacer" style="margin-left:0.057em"></span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:0.854em;vertical-align:-0.05em"></span></span></nobr></span> of residue modulo <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:0.526em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmr10">5</span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:0.854em;vertical-align:-0.05em"></span></span></nobr></span>, there must exist <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:2.256em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmmi10">x</span><span style="position: relative; margin-left:0.277em;"><img src="jsMath/fonts/cmsy10/alpha/100/char32.png" style=" width:9px; vertical-align:-1px; margin-right:0.019em;"></span><span style="position: relative; margin-left:0.277em;"><span class="icmmi10">S</span><span class="spacer" style="margin-left:0.057em"></span></span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:0.893em;vertical-align:-0.089em"></span></span></nobr></span> such that <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:10.077em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmr10">2</span><span style="position: relative; top:-0.362em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span><span style="position: relative; margin-left:0.222em;"><img src="jsMath/fonts/cmsy10/alpha/100/char01.png" style=" width:3px; vertical-align:2px; margin-right:0.062em;"></span><span style="position: relative; margin-left:0.222em;"><span class="icmmi10">x</span></span><span style="position: relative; margin-left:0.222em;"><span class="icmr10">+</span></span><span style="position: relative; margin-left:0.222em;"><span class="icmmi10">a</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span><span style="position: relative; margin-left:0.277em;"><img src="jsMath/fonts/cmsy10/alpha/100/char11.png" style=" width:11px; margin-right:-0.013em;"></span><span style="position: relative; margin-left:0.277em;"><span class="icmr10">0</span></span><span style="position: relative; margin-left:1em;"><span class="icmr10">(</span></span><span class="icmr10">mod</span><span style="position: relative; margin-left:0.333em;"><span class="icmr10">5</span></span><span class="icmr10">)</span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:1.277em;vertical-align:-0.336em"></span></span></nobr></span>
So, there exists <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:8.197em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.022em"></span><span class="size2"><span class="icmr10">+1</span></span><span class="spacer" style="margin-left:0.05em"></span></span><span style="position: relative; margin-left:0.277em;"><img src="jsMath/fonts/cmsy10/alpha/100/char32.png" style=" width:9px; vertical-align:-1px; margin-right:0.019em;"></span><span style="position: relative; margin-left:0.277em;"><img src="jsMath/fonts/cmsy10/alpha/100/char66.png" style="height:15px; width:6px; vertical-align:-4px; margin-right:0.068em;"></span><span class="icmr10">1</span><img src="jsMath/fonts/cmmi10/alpha/100/char3B.png" style=" width:3px; vertical-align:-3px; margin-right:0.062em;"><span style="position: relative; margin-left:0.166em;"><span class="icmr10">3</span></span><img src="jsMath/fonts/cmmi10/alpha/100/char3B.png" style=" width:3px; vertical-align:-3px; margin-right:0.062em;"><span style="position: relative; margin-left:0.166em;"><span class="icmr10">5</span></span><img src="jsMath/fonts/cmmi10/alpha/100/char3B.png" style=" width:3px; vertical-align:-3px; margin-right:0.062em;"><span style="position: relative; margin-left:0.166em;"><span class="icmr10">7</span></span><img src="jsMath/fonts/cmmi10/alpha/100/char3B.png" style=" width:3px; vertical-align:-3px; margin-right:0.062em;"><span style="position: relative; margin-left:0.166em;"><span class="icmr10">9</span></span><img src="jsMath/fonts/cmsy10/alpha/100/char67.png" style="height:15px; width:6px; vertical-align:-4px; margin-right:0.068em;"> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:1.141em;vertical-align:-0.336em"></span></span></nobr></span> such that <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:5.038em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmr10">2</span><span style="position: relative; top:-0.362em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span><span style="position: relative; margin-left:0.222em;"><img src="jsMath/fonts/cmsy10/alpha/100/char01.png" style=" width:3px; vertical-align:2px; margin-right:0.062em;"></span><span style="position: relative; margin-left:0.222em;"><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.022em"></span><span class="size2"><span class="icmr10">+1</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span><span style="position: relative; margin-left:0.222em;"><span class="icmr10">+</span></span><span style="position: relative; margin-left:0.222em;"><span class="icmmi10">a</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:1.277em;vertical-align:-0.336em"></span></span></nobr></span> is divisable by <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:0.526em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmr10">5</span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:0.854em;vertical-align:-0.05em"></span></span></nobr></span>
Now, <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:33.091em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.022em"></span><span class="size2"><span class="icmr10">+1</span></span><span class="spacer" style="margin-left:0.05em"></span></span><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span><span style="position: relative; margin-left:0.166em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"><span style="position: relative; margin-left:0.166em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"></span><span style="position: relative; margin-left:0.166em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"></span></span><span style="position: relative; margin-left:0.166em;"><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmr10">1</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span><span style="position: relative; margin-left:0.277em;"><span class="icmr10">=</span></span><span style="position: relative; margin-left:0.277em;"><span class="icmr10">1</span></span><span class="icmr10">0</span><span style="position: relative; top:-0.362em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span><span style="position: relative; margin-left:0.222em;"><img src="jsMath/fonts/cmsy10/alpha/100/char01.png" style=" width:3px; vertical-align:2px; margin-right:0.062em;"></span><span style="position: relative; margin-left:0.222em;"><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.022em"></span><span class="size2"><span class="icmr10">+1</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span><span style="position: relative; margin-left:0.222em;"><span class="icmr10">+</span></span><span style="position: relative; margin-left:0.222em;"><span style="position: relative; top:-0.859em;"><img src="jsMath/fonts/cmex10/alpha/100/char00.png" style="height:18px; width:6px; vertical-align:-17px; margin-right:0.026em;"></span><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.022em"></span><span class="size2"><span class="icmsy10">−</span><span class="icmr10">1</span></span><span class="spacer" style="margin-left:0.05em"></span></span><span style="position: relative; margin-left:0.166em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"><span style="position: relative; margin-left:0.166em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"></span><span style="position: relative; margin-left:0.166em;"><img src="jsMath/fonts/cmmi10/alpha/100/char3A.png" style=" width:3px; margin-right:0.062em;"></span></span><span style="position: relative; margin-left:0.166em;"><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmr10">1</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span><span style="position: relative; top:-0.859em;"><img src="jsMath/fonts/cmex10/alpha/100/char01.png" style="height:18px; width:5px; vertical-align:-17px; margin-right:0.098em;"></span></span><span style="position: relative; margin-left:0.277em;"><span class="icmr10">=</span></span><span style="position: relative; margin-left:0.277em;"><span class="icmr10">1</span></span><span class="icmr10">0</span><span style="position: relative; top:-0.362em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span><span style="position: relative; margin-left:0.222em;"><img src="jsMath/fonts/cmsy10/alpha/100/char01.png" style=" width:3px; vertical-align:2px; margin-right:0.062em;"></span><span style="position: relative; margin-left:0.222em;"><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.022em"></span><span class="size2"><span class="icmr10">+1</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span><span style="position: relative; margin-left:0.222em;"><span class="icmr10">+</span></span><span style="position: relative; margin-left:0.222em;"><span class="icmr10">5</span><span style="position: relative; top:-0.362em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span><span style="position: relative; margin-left:0.222em;"><img src="jsMath/fonts/cmsy10/alpha/100/char01.png" style=" width:3px; vertical-align:2px; margin-right:0.062em;"></span><span style="position: relative; margin-left:0.222em;"><span class="icmmi10">a</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span><span style="position: relative; margin-left:0.277em;"><span class="icmr10">=</span></span><span style="position: relative; margin-left:0.277em;"><span class="icmr10">5</span><span style="position: relative; top:-0.362em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span><span style="position: relative; margin-left:0.166em;"><span style="position: relative; top:-0.859em;"><img src="jsMath/fonts/cmex10/alpha/100/char00.png" style="height:18px; width:6px; vertical-align:-17px; margin-right:0.026em;"></span><span class="icmr10">2</span><span style="position: relative; top:-0.362em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span><span style="position: relative; margin-left:0.222em;"><img src="jsMath/fonts/cmsy10/alpha/100/char01.png" style=" width:3px; vertical-align:2px; margin-right:0.062em;"></span><span style="position: relative; margin-left:0.222em;"><span class="icmmi10">b</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.022em"></span><span class="size2"><span class="icmr10">+1</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span><span style="position: relative; margin-left:0.222em;"><span class="icmr10">+</span></span><span style="position: relative; margin-left:0.222em;"><span class="icmmi10">a</span><span style="position: relative; top:0.286em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.05em"></span></span></span><span style="position: relative; top:-0.859em;"><img src="jsMath/fonts/cmex10/alpha/100/char01.png" style="height:18px; width:5px; vertical-align:-17px; margin-right:0.098em;"></span></span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:1.3em;vertical-align:-0.350em"></span></span></nobr></span>, which is divisable by <span class="typeset"><nobr><span class="scale"><span style="display:inline-block; width:1.654em"><span style="position:relative;"><span style="position:absolute; top:-0.097em; left:0em;"><span class="icmr10">5</span><span style="position: relative; top:-0.362em;"><span class="size2"><span class="icmmi10">k</span></span><span class="spacer" style="margin-left:0.022em"></span><span class="size2"><span class="icmr10">+1</span></span><span class="spacer" style="margin-left:0.05em"></span></span> </span><span class="blank" style="height:0.827em;"></span></span></span><span class="blank" style="height:0.990em;vertical-align:-0.05em"></span></span></nobr></span> (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" :cry: :cry: :cry: :cry:
Last edited by Mehrab4226 on Tue Dec 22, 2020 12:14 am, edited 1 time in total.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: A problem from USAMO 2003

Unread post by Mehrab4226 » 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.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: A problem from USAMO 2003

Unread post by Anindya Biswas » 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}$
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: A problem from USAMO 2003

Unread post by Mehrab4226 » 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.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Post Reply