Dhaka Secondary 2011/9

Problem for Secondary Group from Divisional Mathematical Olympiad will be solved here.
Forum rules
Please don't post problems (by starting a topic) in the "Secondary: Solved" forum. This forum is only for showcasing the problems for the convenience of the users. You can post the problems in the main Divisional Math Olympiad forum. Later we shall move that topic with proper formatting, and post in the resource section.
BdMO
Posts:134
Joined:Tue Jan 18, 2011 1:31 pm
Dhaka Secondary 2011/9

Unread post by BdMO » Fri Jan 28, 2011 10:10 pm

$x$ is a positive integer so that $2^x$ and $x^2$ leaves same remainder when divided by $3$. There are many possible values for $x$. What will be the remainder when the sum of the first $2011$ values of $x$ is divided by $1000$?

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Dhaka Secondary 2011/9

Unread post by *Mahi* » Sat Jan 29, 2011 11:01 pm

This one is really tricky,here is how I tamed it-
Solution:
We know that
$2\equiv -1(mod 3)
\Rightarrow2^x\equiv (-1)^x(mod 3)$
So we can strike out the numbers divisible by $3$.
Now again the numbers which 'survive' are always like this-
$x^2\equiv 1 (mod 3)$
So we have to just sum up the first $2011$ even numbers which are not divisible by $3$ and get it $(mod 1000)$
:D
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

the arrivals
Posts:41
Joined:Tue Dec 21, 2010 10:17 pm

Re: Dhaka Secondary 2011/9

Unread post by the arrivals » Mon Jan 31, 2011 8:58 pm

my approach is this
suppose (x,3)=1 where (a,b) means their gcd
by euler x^2=1 mod 3
and again (2,3)=1
so 2^(2y)=1mod 3
let x=2y
so we need to sort out all those numbers coprime to 3 .but note problem occurs with 6.but in this case PIE (principle of inclusion exclusion) perhaps paves da way
women of purity are for men of purity and hence men of purity are for women of purity - THE HOLY QURAN

Shifat
Posts:53
Joined:Sun Jul 31, 2011 12:21 pm
Location:Dhaka, Bangladesh

Re: Dhaka Secondary 2011/9

Unread post by Shifat » Sat Aug 27, 2011 12:34 am

Since if the values of x=2y typed then $X^2$ and $2^x$ will give the same remainder divided by 3, so, x is obviously even, for the first even number y=1, so actually the question becomes like this

(2+4+6+8+........................4020+4022)(mod 1000)=??
or $2011.2012 (mod 1000)$
$2011.2012$=
$(2000+11)(2000+12)$
(x+a)(x+b) apply and we get
$2000^2+ 23.2000+132$
or $0(mod 1000)+ 0(mod 1000)+ 132(mod 1000)$
so the answer is $132$...:?

Any apottis??

User avatar
Abdul Muntakim Rafi
Posts:173
Joined:Tue Mar 29, 2011 10:07 pm
Location:bangladesh,the earth,milkyway,local group.

Re: Dhaka Secondary 2011/9

Unread post by Abdul Muntakim Rafi » Mon Aug 29, 2011 1:13 am

For, $x=6, 2^6=64$ which leaves 1 as a remainder when divided by 3.And $6^2=36$ which leaves 0 as a remainder... So how come 6 is a possible value of x?
Man himself is the master of his fate...

Shifat
Posts:53
Joined:Sun Jul 31, 2011 12:21 pm
Location:Dhaka, Bangladesh

Re: Dhaka Secondary 2011/9

Unread post by Shifat » Mon Aug 29, 2011 3:27 am

then maybe x= 2y where 2y mod 3 not equals 0 should be applied, suppose, 2,4,8,10,14,16,20........???(i am too interested in the problem, thinking randomly and making a mess please accept the apology??)
Last edited by Shifat on Mon Aug 29, 2011 5:04 am, edited 1 time in total.

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Dhaka Secondary 2011/9

Unread post by *Mahi* » Mon Aug 29, 2011 4:24 am

This is not right.
$10^2 \equiv 2^{10} \equiv 1 (mod 3)$
You left many of this kind...
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

Shifat
Posts:53
Joined:Sun Jul 31, 2011 12:21 pm
Location:Dhaka, Bangladesh

Re: Dhaka Secondary 2011/9

Unread post by Shifat » Mon Aug 29, 2011 5:19 am

yes I think this time it is okay, obviously it asks mod 3not equals 0 so, if x=(3n)^2 typed something then the mod will be 0, where 2^x will remain a remainder, and not any odd numbers of course..... and x^2 equiv 1 (mod3) when it is even,so the series should be(hope no more casualties) 2+4+8+10+14+16+...........??? we miss an even number after going through 2 consecutive even. so the last even number should be 2011*(3/2)=3016.5 or 3017th even number, But now, how can we sum them?? and ofcourse, if done, how can the (mod 1000) be found???

User avatar
Abdul Muntakim Rafi
Posts:173
Joined:Tue Mar 29, 2011 10:07 pm
Location:bangladesh,the earth,milkyway,local group.

Re: Dhaka Secondary 2011/9

Unread post by Abdul Muntakim Rafi » Mon Aug 29, 2011 1:20 pm

The possible values of x are all even numbers except the multiples of 6...

$ x= 2,4,8,10,14,16,.....................................$

Now how to find the summation of them...
we can do it easily by taking two integers at a time...
$ 2+4=6, 8+10=18, 14+16=30, .....................$
We got a new series...
It's $ 6+18+30+............. $
Any term of the series is $6(2n-1)$
The 1005th term of the series would be $6(1005*2-1) = 12054 $
So,the series is $ 6+18+30+..........................+12054$
The sum of them is $6060150$
Now not to forget,the sum of this series equal to the sum of first 2010 possible values of x.
2011th possible value of x is 2010th value $+4=6028+4=6032 $
so the sum of first 2011 values is $6066182$
so the remainder would be $182$
There might be any mistake in the calculation but I think the way is right... :D
Man himself is the master of his fate...

Shifat
Posts:53
Joined:Sun Jul 31, 2011 12:21 pm
Location:Dhaka, Bangladesh

Re: Dhaka Secondary 2011/9

Unread post by Shifat » Thu Sep 08, 2011 7:57 pm

Yes the answer is 182 and (before posting the solution I like to thank Mahi and rafi) .......
the series is $2+ 4+8+10+14+16+20+22+...........$... 2011 numbers
we can notice in the series the nth value is either 3n-1(n odd) or 3n-2(n even)
so the 2011 th number is (3.2011-1)= 6032= 32(mod 1000)
the series can be written like this $(2+4)+(8+10)+........... $..... 1005 pair of numbers
or $6+18+30+........$.. here "podoshonkha" n is 1005
as it is a particular series whare the common difference is 12
so the sum is after calculating $1005.6030$
$= 1005.(1005.6)$
$= 6.(1005)^2$
$= 6. ( 5 (mod 1000))^2$
$= 6. 25(mod 1000)$
$=150 (mod 1000)$
so the total remainder is $182(mod 1000)$
hope no jmore casualties....... :? :)

Post Reply