A special set is a set of positive odd integers no element of which divides another, and each 3-element subset of which has a member dividing the sum of the other two. A special set is maximal if it is contained in no other special set. Determine the number of elements a maximal special set may have.
Yu. I. Ionin, Russia
Solution
Leaving aside the trivial case , a maximal special set may have only 3, 4 or 5 elements. Begin by noticing that if are positive odd integers, and does not divide , then , and form a special set, so a maximal special set has at least three elements.
At the other extreme, a special set — in particular, one that is maximal — has at most five elements. The proof relies on the three facts below:
(1) If form a special set, then is not divisible by . This is because is odd, and is a positive even integer less than .
(2) If are members of a special set , then at most one of the members of less than does not divide the sum . Suppose, if possible, and are distinct members of less than , neither of which divides the sum . By (1), divides neither nor , so and are both divisible by . Then is a positive integer less than and divisible by — a contradiction.
(3) If form a special set, and and are both divisible by , then is not divisible by . Otherwise, would divide , which is impossible, since is odd and does not divide .
We are now in a position to prove that a special set has at most five elements. Suppose, if possible, are pairwise distinct members of a special set. We may and will assume .
Fix a pair of distinct indices and , and write . By (2), some divides both and , by (3), that does not divide , so, with reference again to (2), it is the unique not dividing .
Consequently, the three 's may be labeled so that and both divide , while does not, .
By (1), does not divide , and since does not divide , it follows that is divisible by . Similarly, is divisible by , and hence so is . Finally, since is divisible by , by (2), so is , in contradiction with (1).
Consequently, a special set — in particular, one that is maximal — has at most five elements.
Next, we show that 5-element special sets actually exist. Clearly, the numbers , , form a special set. To enlarge this set to a 4-element special set by adjoining a positive odd integer , notice that divides no 2-term sum from , to infer that satisfies one of the two systems of linear congruences below:
By the Chinese remainder theorem, each of these systems has infinitely many solutions; in each case, two solutions differ by a multiple of . The least positive solution of the former is , and the least positive solution of the latter is .
To enlarge the set to a 5-element special set by adjoining a positive odd integer , notice again that divides no 2-term sum from , to infer that satisfies the system of linear congruences
clearly, and both divide . As before, the Chinese remainder theorem settles the case; incidentally, the least positive solution is , and all five numbers are prime.
Similarly, the set extends to a 5-element special set by adjoining any positive odd integer satisfying the system of linear congruences
clearly, and both divide . In this case, the least positive solution is .
Remark. The 5-element special sets below are obtained in the same way:
We now show that the special set consisting of , , , is maximal. Suppose, if possible, that is a positive odd integer such that , , , , form a special set. It is easily seen that divides no 2-term sum from .
We first show that is divisible by if and only if is divisible by ; since one holds, so does the other.
If is divisible by , then is not, so is divisible by . It follows that is not divisible by , so is divisible by , showing that is indeed divisible by .