Let , and be positive integers and let be the integers given in some order. If
holds for all , prove that one of the numbers and is divisible by .
Solution
Let us assume that does not divide and that , .
Since only the remainder of division of by is relevant, without loss of generality we may assume . We will prove that .
If we assume that , then the numbers would be equal to the numbers in some order. This is impossible since the first sequence has elements, and the second sequence has elements.
Hence and . There are numbers which are equal to numbers . This implies , i.e. . Since we assumed that it follows that .
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.