Let be a set of integers, none of them is divisible by . Prove that there exists a -element subset of such that is not divisible by for any .
, 2007
Solution
Call a set of integers good if for any .
Consider the set . We claim that is good. Actually, for any the number is odd and
But there is no odd number divisible by between and .
For any consider the set
If is not good, then for some , hence . But set contains numbers with the same residues modulo , so also is not good. This is a contradiction; therefore each is a good subset of .
Then it suffices to prove that there exists a number such that . Note that each is contained in exactly sets . Then
hence for some value of we have
Looking for a route rather than an archive? The track puts 2,000
problems in a working order, from AMC 10 level to the IMO shortlist.