BdMO 2010 higher secondary Q. 6

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
User avatar
TIUrmi
Posts:61
Joined:Tue Dec 07, 2010 12:13 am
Location:Dinajpur, Bangladesh
Contact:
BdMO 2010 higher secondary Q. 6

Unread post by TIUrmi » Wed Dec 22, 2010 1:56 pm

$a$ and $b$ are two positive integers both less than $2010$; $a$ Find the number of ordered
pairs $(a, b)$ such that $a^{2} + b^{2}$ is divisible by $5$. Find $a + b$ so that $a^{2} + b^{2}$ is maximum.

Is the solutions correct? :S

The last digit $d$ of $a^{2}$ or $b^{2}$ is from the set $S$ = $\{ d \in d: a^{2} \equiv d (mod 10)\}$ or $S$ = $\{1, 4, 9, 6, 5, 6, 9, 4, 1, 0\}$. There are $201$ digits ending with each of these numbers.
Now we are to find pairs $(a, b)$ such that their last digits are $(1, 4), (1, 9), (4, 6), (9, 1), (6, 4), (5, 5), (5, 0),(9, 1), (4, 6), (1, 4), (1, 9), (0, 5), (0, 0)$. Note: I am dealing only with the last digits because that determines it's divisibility by 5.

So, for every digit ending with 1 number from $S$, we get 2 possible pairs.
As $(a, b)$ is ordered, $(16, 8)$ and $(8, 16)$ are different. We will count by fixing a number for $a$ and counting possible $b$'s. Hence, as we are fixing one distinct number for $a$ each time, no double counting occurs.

Answer: $201*402*10$
"Go down deep enough into anything and you will find mathematics." ~Dean Schlicter

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

Re: BdMO 2010 higher secondary Q. 6

Unread post by Avik Roy » Wed Dec 22, 2010 2:40 pm

If the condition $a \ne b$ is not imposed, the result is correct.
However, dealing with quadratic residue of $5$ gives a much direct access to the problem. What Urmi did is just a "broken into pieces" method of the easier one.

Nice solution :)
"Je le vois, mais je ne le crois pas!" - Georg Ferdinand Ludwig Philipp Cantor

User avatar
sm.joty
Posts:327
Joined:Thu Aug 18, 2011 12:42 am
Location:Dhaka

Re: BdMO 2010 higher secondary Q. 6

Unread post by sm.joty » Sun Dec 18, 2011 4:20 pm

সব বুঝলাম কিন্তু শেষে কেন $201*402*10$ লেখা হল বুঝলাম না।
২০১ টা সংখ্যা পাওয়া যায় এটা বুঝছি কিন্তু ১০ আর ৪০২ কেন আসল ????
হার জিত চিরদিন থাকবেই
তবুও এগিয়ে যেতে হবে.........
বাধা-বিঘ্ন না পেরিয়ে
বড় হয়েছে কে কবে.........

Shihab
Posts:11
Joined:Mon Dec 26, 2011 1:11 am

Re: BdMO 2010 higher secondary Q. 6

Unread post by Shihab » Wed Dec 28, 2011 9:54 pm

I'm confoused. Apu, I think you have counted (a^2,b^2). But we have to count (a,b). @Urmi apu
God has made the integers, all the rest is the work of man.
-Leopold Kronecker

User avatar
Nadim Ul Abrar
Posts:244
Joined:Sat May 07, 2011 12:36 pm
Location:B.A.R.D , kotbari , Comilla

Re: BdMO 2010 higher secondary Q. 6

Unread post by Nadim Ul Abrar » Sat Jan 07, 2012 5:01 pm

$a^2\equiv0^2,1^2,2^2,3^2,4^2\equiv0,1,-1,-1,1 (mod5)$

There are $804$ numbers of form $5n+2$ and $5n+3$ less then $2010$.
There are $804$ numbers of form $5n+1$ and $5n+4$ less then $2010$.
There are $401$ numbers of form $5n$ less then $2010$.

So that number of pair $(a,b)$ be $2.804^2+401^2$.

And (a^2+b^2)_{max} can be found for the pair $(2009,2008),(2008,2009)$ , So that required value of $a+b$ be $4017 $:)
$\frac{1}{0}$

User avatar
bristy1588
Posts:92
Joined:Sun Jun 19, 2011 10:31 am

Re: BdMO 2010 higher secondary Q. 6

Unread post by bristy1588 » Sat Jan 21, 2012 11:19 am

@Nadim,
$a \ne b$ if this condition is maintained, then the ans will be $2.(804)^2 + 401.400$.
Bristy Sikder

User avatar
SANZEED
Posts:550
Joined:Wed Dec 28, 2011 6:45 pm
Location:Mymensingh, Bangladesh

Re: BdMO 2010 higher secondary Q. 6

Unread post by SANZEED » Wed Feb 06, 2013 10:47 pm

Nadim Ul Abrar wrote:$a^2\equiv0^2,1^2,2^2,3^2,4^2\equiv0,1,-1,-1,1 (mod5)$

There are $804$ numbers of form $5n+2$ and $5n+3$ less then $2010$.
There are $804$ numbers of form $5n+1$ and $5n+4$ less then $2010$.
There are $401$ numbers of form $5n$ less then $2010$.

So that number of pair $(a,b)$ be $2.804^2+401^2$.

And (a^2+b^2)_{max} can be found for the pair $(2009,2008),(2008,2009)$ , So that required value of $a+b$ be $4017 $:)
Why did you considered $a,b$ of the forms $5n+2,5n+3$ ? Because $(5n+2)^{2}+(5n+3)^{2}\equiv 3(mod 5)$.
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

sakib.creza
Posts:26
Joined:Sat Nov 03, 2012 6:36 am

Re: BdMO 2010 higher secondary Q. 6

Unread post by sakib.creza » Thu Feb 07, 2013 7:08 pm

SANZEED wrote:
Nadim Ul Abrar wrote:$a^2\equiv0^2,1^2,2^2,3^2,4^2\equiv0,1,-1,-1,1 (mod5)$

There are $804$ numbers of form $5n+2$ and $5n+3$ less then $2010$.
There are $804$ numbers of form $5n+1$ and $5n+4$ less then $2010$.
There are $401$ numbers of form $5n$ less then $2010$.

So that number of pair $(a,b)$ be $2.804^2+401^2$.

And $(a^2+b^2)_{max}$ can be found for the pair $(2009,2008),(2008,2009)$ , So that required value of $a+b$ be $4017 $:)
Why did you considered $a,b$ of the forms $5n+2,5n+3$ ? Because $(5n+2)^{2}+(5n+3)^{2}\equiv 3(mod 5)$.
The pairs Nadim Bhai should be considering are $5n+1$ and $5n+2$, $5n+1$ and $5n+3$, $5n+2$ and $5n+4$, $5n+3$ and $5n+4$. No matter which pair you take the sum of the squares, $S\equiv 0(mod 5)$.

There are $402$ numbers of form $5n+1$, $402$ numbers of form $5n+2$, $402$ numbers of form $5n+3$ and $402$ numbers of form $5n+4$ less then $2010$.
There are $401$ numbers of form $5n$ less then $2010$.

As $a \ne b$ total ordered pairs should be $4.402^2+401.400$

Post Reply