Problem:
Let be a set of 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 element, not elements. If is the least element of , then , and are available to be in , but and cannot both be in , so the largest possible size of is . If is the least element, then , and are available, but at most one of and can be in and at most one of and can be in , so again has size at most . The set has the required property, so is the least possible element of .
At most one integer can be selected for from each of the following groups: , and . Because consists of distinct integers, exactly one integer must be selected from each of these groups. Therefore , , and must be in . Because is in must not be in . This implies that either or must be selected from the second group, so neither nor can be selected from the first group. If is selected from the first group, the collection of integers is one possibility for the set . Therefore is the least possible element of .
Note: The two collections given in the solutions are the only ones with least element that have the given property. This problem is a special case of the following result of Paul ErdΕs from the s:
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