November 2000
<<October November December>>
Part A:
1,2,3,4,5, 17,18,19,20,21, 33,34,35,36,37, ..., 225,226,227,228,229.
The pattern is: Take 5, skip 11, take 5, skip 11.
Part B:
First we show that among any 16 consecutive integers we can take at most five.
Suppose, to the contrary, that our collection included six integers among (1,2,3,...,15,16).
Consider the following six sets:
(1,6,12), (2,7,13), (3,8,14), (4,9,15), (5,10,16), (11).
Within each set, any two elements differ by either 5, 6, or 11.
So each set can contribute at most one to our collection.
Since our collection needs six elements, we must take exactly one from each set; in particular, we must take element 11 from the last set.
Similarly, consider the six sets:
(1,7,12), (2,8,13), (3,9,14), (4,10,15), (5,11,16), (6).
The same argument tells us that our collection must contain 6.
But we cannot take both 6 and 11, since they differ by 5.
Now the integers from 1 to 240 can be partitioned into 15 sets, each containing 16 consecutive integers. We have just shown that our collection can contain at most 5 from each of these sets, or at most 75 in all. So we have shown that we cannot have 76 integers between 1 and 240 inclusive, an even stronger result than was asked for.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com