Problem:
Let S be a subset of {1,2,3,…,30} with the property that no pair of distinct elements in S has a sum divisible by 5 . What is the largest possible size of S ?
Answer Choices:
A. 10
B. 13
C. 15
D. 16
E. 18
Solution:
For 1≤j≤5, let Sj​={5n+j:0≤n≤5}. Because no pair of elements in S can have a sum that is divisible by 5 , at least one of the sets S∩S1​ and S∩S4​ must be empty. Similarly, at least one of S∩S2​ and S∩S3​ must be empty, and S∩S5​ can contain at most one element. Thus S can contain at most 30−6−6−5=13​ elements. An example of a set that meets the requirements is S={1,2,6,7,11,12,16,17,21,22,26,27,30}.
OR
The set S from the previous solution shows that size 13​ is possible. Consider the following partition of {1,2,…,30} :
{5,10,15,20,25,30},{1,4},{2,3},{6,9},{7,8},{11,14},{12,13},{16,19},{17,18},{21,24},{22,23},{26,29},{27,28}.​
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 S with at least 14 elements has at least two elements whose sum is divisible by 5 . Therefore 13​ is the largest possible size of S.
The problems on this page are the property of the MAA's American Mathematics Competitions