Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given any nine integers show that it is possible to choose, from among them, four integers a, b, c, d such that a + b − c − d is divisible by 20. Further show that such a selection is not possible if we start with eight integers instead of nine.

i cant prove it in all cases

share|improve this question
    
Which cases have you been able to prove? –  abiessu Feb 1 at 5:04
    
Suppose there are four numbers a, b, c, d among the given nine numbers which leave the same remainder modulo 20. Then a + b ≡ c + d (mod 20) and we are done –  maths lover Feb 1 at 5:06
    
If not, there are two possibilities: (1) We may have two disjoint pairs { a, c } and { b, d } obtained from the given nine numbers such that a ≡ c (mod 20) and b ≡ d (mod 20). In this case we get a + b ≡ c + d (mod 20) –  maths lover Feb 1 at 5:07
    
i have been able to prove the secondcase also –  maths lover Feb 1 at 5:08

2 Answers 2

Look at all the remainders $\pmod{20}$.

Case I. Some remainder occurs $4$ times, i.e., we have four distinct numbers $a,b,c,d$ with $a\equiv b\equiv c\equiv d\pmod{20}$. Then $a+b-c-d\equiv0\pmod{20}$.

Case II. Two remainders occur twice each, i.e., we have four distinct numbers $a,b,c,d$ with $a\equiv c\pmod{20}$ and $b\equiv d\pmod{20}$. Then $a+b-c-d\equiv0\pmod{20}$.

Case III. No remainder occurs more than thrice, and at most one remainder occurs more than once. In that case, among the $9$ numbers we can choose $7$ with different remainders. Among the $\binom72=21$ pairwise sums of those $7$ numbers, we can find two which are congruent $\pmod{20}$; i.e., we have $a+b\equiv c+d\pmod{20}$, while $a\neq b,\ c\neq d$ and $\{a,b\}\neq\{c,d\}$. The four numbers $a,b,c,d$ must all be distinct because, if we had (say) $a=c$, then we would have $b\equiv d\pmod{20}$ but $b\neq d$, contradicting the fact that the numbers were chosen to have different remainders $\pmod{20}$. So $a,b,c,d$ are four distinct numbers, and $a+b-c-d\equiv0\pmod{20}$.

P.S. It doesn't work with eight integers; e.g., the set $\{1,2,4,7,12,20,40,60\}$.

share|improve this answer

Hint: The remainders of the division through $20$ are $0,\pm1,\pm2,\pm3,\pm4,\pm5,\pm6,\pm7,\pm8,\pm9,\pm10$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.