Problem:
Let be a set of 6 integers taken from with the property that if and are elements of with , then is not a multiple of . What is the least possible value of an element of
Answer Choices:
A.
B.
C.
D.
E.
Solution:
If , then can have only 1 element, not 6 elements. If 2 is the least element of , then , and 11 are available to be in , but 3 and 9 cannot both be in , so the largest possible size of is 5 . If 3 is the least element, then , and 11 are available, but at most one of 4 and 8 can be in and at most one of 5 and 10 can be in , so again has size at most 5 . The set has the required property, so is the least possible element of .
OR
At most one integer can be selected for from each of the following 6 groups: , and . Because consists of 6 distinct integers, exactly one integer must be selected from each of these 6 groups. Therefore 7,9 , and 11 must be in . Because 9 is in must not be in . This implies that either 6 or 12 must be selected from the second group, so neither 1 nor 2 can be selected from the first group. If 4 is selected from the first group, the collection of integers is one possibility for the set . Therefore 4 is the least possible element of .
Note: The two collections given in the solutions are the only ones with least element 4 that have the given property. This problem is a special case of the following result of Paul Erdos from the 1930s: Given integers , no one of them dividing any other, with , let the integer be determined by the inequalities . Then , and this bound is sharp.
The problems on this page are the property of the MAA's American Mathematics Competitions