Tuymaada 2008,Junior League,D2,P8

For discussing Olympiad Level Number Theory problems
tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh
Tuymaada 2008,Junior League,D2,P8

Unread post by tanmoy » Sun Feb 21, 2016 12:44 pm

$250$ numbers are chosen among positive integers not exceeding $501$.Prove that for every integer $t$ there are four chosen numbers $a_{1}$,$a_{2}$,$a_{3}$,$a_{4}$,such that $a_{1}+a_{2}+a_{3}+a_{4}-t$ is divisible by 23.

Author: K. Kokhas
"Questions we can't answer are far better than answers we can't question"

Ragib Farhat Hasan
Posts:62
Joined:Sun Mar 30, 2014 10:40 pm

Re: Tuymaada 2008,Junior League,D2,P8

Unread post by Ragib Farhat Hasan » Tue Feb 23, 2016 9:15 pm

What is t=501?

User avatar
nahin munkar
Posts:81
Joined:Mon Aug 17, 2015 6:51 pm
Location:banasree,dhaka

Re: Tuymaada 2008,Junior League,D2,P8

Unread post by nahin munkar » Mon Apr 04, 2016 10:57 pm

From the ques.,a1+a2+a3+a4-t≡0 (mod 23).so,a1+a2+a3+a4≡t(mod 23). The residue classes of modulo 23 is{0,1,2,.....,22}.so,it can be, t≡0/1/2/3/..../22(mod 23)(***1). Here we see,the integers can't exceed 501.so one residue class among(0,1,2,...,22)must be of the 21 integers not exceeding 501.as,23*21+18=501.from here we can tell,different 22 integers have 18(1,...18) res.classes.& different 21 int. have 5(0,19,20,21,22) res. class.here,501=22*18+21*5. Now if we choose 250 numbers from these integers not exceeding 501,let,we choose 250 numbers among modulo 1 to mod 18.there are 22 numbers for each modulo.we choose all the 22 num. for single modulo. as,250=22*11+8.so,we take 22 int. of 11 mod class.there are 12 mod class remaining.we take remaining 8 numbers from other mod class.so,we have atleast 12 mod class among 0,1,2,....,22.it is possible to write the sum of four integers (of the 12 mod class) mod 23 is congruent to any of 0,1,2,...22 . so, it is true that, a1+a2+a3+a4≡t(mod 23)...(from ***1) .SO, a1+a2+a3+a4-t is divisible by 23. [proved]

Post Reply