# 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.

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

-
Which cases have you been able to prove? – abiessu Feb 1 '14 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 '14 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 '14 at 5:07
i have been able to prove the secondcase also – maths lover Feb 1 '14 at 5:08

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\}$.

-

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

-