Let be a positive integer. Prove that if Mari writes at least 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 .
Solution
As Mari writes down numbers and there are only different remainders when dividing by , there must be two that give equal remainders when divided by ; let those numbers be and . The rest of the include two that also give equal remainders when divided by ; let those be and . Now and give the same remainder when divided by , thus Jüri can choose the numbers , , and .
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.