Maths Olympiad Prep

Library / /94 of 121

Number theory Difficulty 6.7 National Olympiad Prove it India

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

Solution

Solution:
Suppose there are four numbers a,b,c,da, b, c, d among the given nine numbers which leave the same remainder modulo 2020. Then a+bc+d(mod20)a+b \equiv c+d \pmod{20} and we are done.

If not, there are two possibilities:

(1) We may have two disjoint pairs {a,c}\{a, c\} and {b,d}\{b, d\} obtained from the given nine numbers such that ac(mod20)a \equiv c \pmod{20} and bd(mod20)b \equiv d \pmod{20}. In this case we get a+bc+d(mod20)a+b \equiv c+d \pmod{20}.

(2) Or else there are at most three numbers having the same remainder modulo 2020 and the remaining six numbers leave distinct remainders which are also different from the first remainder (i.e., the remainder of the three numbers). Thus there are at least 77 distinct remainders modulo 2020 that can be obtained from the given set of nine numbers. These 77 remainders give rise to (72)=21\binom{7}{2} = 21 pairs of numbers. By pigeonhole principle, there must be two pairs (r1,r2),(r3,r4)\left(r_1, r_2\right), \left(r_3, r_4\right) such that r1+r2r3+r4(mod20)r_1 + r_2 \equiv r_3 + r_4 \pmod{20}. Going back we get four numbers a,b,c,da, b, c, d such that a+bc+d(mod20)a+b \equiv c+d \pmod{20}.

If we take the numbers 0,0,0,1,2,4,7,120, 0, 0, 1, 2, 4, 7, 12, we check that the result is not true for these eight numbers.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.