Problem:
Let be a subset of such that no two members of differ by or . What is the largest number of elements can have?
Solution:
We first show that, given any set of 11 consecutive integers from , at most of these can be elements of . We prove this fact for the set , but the same proof works for any set of consecutive integers. Consider the following partition of , where each subset was formed so that it can contribute at most one element to :
If it were possible to have elements of in , then each of the sets in would have to contribute exactly one element. That this is impossible is shown by the following chain of implications:
With the aid of , or otherwise, it is easy to find a -element subset of that satisfies the key property of (i.e., no two numbers differ by or ). One such set is
We also find (perhaps to our surprise) that has the remarkable property of allowing for a periodic continuation. That is, if denotes the set of integers, then
also has the property that no two elements in the set differ by or . Moreover, since , it is clear that cannot have more than elements. Because the largest element in is , it follows that the set
has elements and hence shows that the upper bound of on the size of the desired set can be attained. This completes the argument.
The problems on this page are the property of the MAA's American Mathematics Competitions