Problem:
Let be a subset of with the property that no pair of distinct elements in has a sum divisible by 5 . What is the largest possible size of ?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
For , let . Because no pair of elements in can have a sum that is divisible by 5 , at least one of the sets and must be empty. Similarly, at least one of and must be empty, and can contain at most one element. Thus can contain at most elements. An example of a set that meets the requirements is .
OR
The set from the previous solution shows that size is possible. Consider the following partition of :
There are 13 sets in this partition, and the sum of any pair of elements in the same part is a multiple of 5 . Thus by the pigeon-hole principle any set with at least 14 elements has at least two elements whose sum is divisible by 5 . Therefore is the largest possible size of .
The problems on this page are the property of the MAA's American Mathematics Competitions