Maths Olympiad Prep

Library / /4 of 32

Combinatorics Difficulty 5.0 AIME, harder Prove it Estonia

Let mm be a positive integer. Prove that if Mari writes at least m+3m+3 numbers on the board, then Jüri can choose 4 of those such that the sum of some two of those and the sum of the other two give the same remainder when divided by mm.

Solution

As Mari writes down m+3m+3 numbers and there are only mm different remainders when dividing by mm, there must be two that give equal remainders when divided by mm; let those numbers be aa and bb. The rest of the m+1m+1 include two that also give equal remainders when divided by mm; let those be cc and dd. Now a+ca+c and b+db+d give the same remainder when divided by mm, thus Jüri can choose the numbers aa, bb, cc and dd.

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.