Problem:
Let S be a subset of {1,2,3,…,1989} such that no two members of S differ by 4 or 7. What is the largest number of elements S can have?
Solution:
We first show that, given any set of 11 consecutive integers from {1,2,3,…,1989}, at most 5 of these 11 can be elements of S. We prove this fact for the set T={1,2,3,…,11}, but the same proof works for any set of 11 consecutive integers. Consider the following partition of T, where each subset was formed so that it can contribute at most one element to S:
{1,5}{2,9}{3,7}{4,11}{6,10}{8}(1)
If it were possible to have 6 elements of T in S, then each of the sets in (1) would have to contribute exactly one element. That this is impossible is shown by the following chain of implications:
8∈S​⟹1∈/S⟹5∈S⟹9∈/S⟹2∈S⟹6∈/S⟹10∈S⟹3∈/S⟹7∈S⟹11∈/S⟹4∈S⟹8∈/S​
With the aid of (1), or otherwise, it is easy to find a 5-element subset of T that satisfies the key property of S (i.e., no two numbers differ by 4 or 7 ). One such set is
T′={1,3,4,6,9}
We also find (perhaps to our surprise) that T′ has the remarkable property of allowing for a periodic continuation. That is, if I denotes the set of integers, then
S′={k+11n∣k∈T′ and n∈I}
also has the property that no two elements in the set differ by 4 or 7. Moreover, since 1989=180⋅11+9, it is clear that S cannot have more than 181⋅5=905 elements. Because the largest element in T′ is 9, it follows that the set
S=S′∩{1,2,3,…,1989}
has 905 elements and hence shows that the upper bound of 905​ 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