Maths Olympiad Prep

Library / /4 of 4

Number theory Difficulty 8.1 Shortlist Prove it Romania

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 {1}\{1\}, a maximal special set may have only 3, 4 or 5 elements. Begin by noticing that if a<ba < b are positive odd integers, and aa does not divide bb, then aa, bb and 2ba2b-a 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 a>b>ca > b > c form a special set, then b+cb+c is not divisible by aa. This is because aa is odd, and b+cb+c is a positive even integer less than 2a2a.

(2) If a>ba > b are members of a special set SS, then at most one of the members of SS less than bb does not divide the sum a+ba+b. Suppose, if possible, cc and dd are distinct members of SS less than bb, neither of which divides the sum a+ba+b. By (1), aa divides neither b+cb+c nor b+db+d, so a+ca+c and a+da+d are both divisible by bb. Then cd=(a+c)(a+d)|c-d| = |(a+c) - (a+d)| is a positive integer less than bb and divisible by bb — a contradiction.

(3) If a,b,c,da, b, c, d form a special set, and a+ba + b and a+ca + c are both divisible by dd, then b+cb+c is not divisible by dd. Otherwise, dd would divide (a+b)+(a+c)(b+c)=2a(a+b)+(a+c)-(b+c) = 2a, which is impossible, since dd is odd and does not divide aa.

We are now in a position to prove that a special set has at most five elements. Suppose, if possible, a1,a2,a3,b1,b2,b3a_1, a_2, a_3, b_1, b_2, b_3 are pairwise distinct members of a special set. We may and will assume a1>a2>a3>max(b1,b2,b3)a_1 > a_2 > a_3 > \max(b_1, b_2, b_3).

Fix a pair of distinct indices ii and jj, and write {i,j,k}={1,2,3}\{i, j, k\} = \{1, 2, 3\}. By (2), some bb divides both ai+aka_i + a_k and aj+aka_j + a_k, by (3), that bb does not divide ai+aja_i + a_j, so, with reference again to (2), it is the unique bb not dividing ai+aja_i + a_j.

Consequently, the three bb's may be labeled so that bib_i and bjb_j both divide ai+aja_i + a_j, while bkb_k does not, {i,j,k}={1,2,3}\{i, j, k\} = \{1, 2, 3\}.

By (1), a1a_1 does not divide a3+b2a_3 + b_2, and since b2b_2 does not divide a1+a3a_1 + a_3, it follows that a1+b2a_1 + b_2 is divisible by a3a_3. Similarly, a2+b1a_2 + b_1 is divisible by a3a_3, and hence so is (a1+b2)+(a2+b1)=(a1+a2)+(b1+b2)(a_1 + b_2) + (a_2 + b_1) = (a_1 + a_2) + (b_1 + b_2). Finally, since a1+a2a_1 + a_2 is divisible by a3a_3, by (2), so is b1+b2b_1 + b_2, 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 33, 55, 77 form a special set. To enlarge this set to a 4-element special set by adjoining a positive odd integer kk, notice that kk divides no 2-term sum from {3,5,7}\{3, 5, 7\}, to infer that kk satisfies one of the two systems of linear congruences below:

{k+10(mod2)k+50(mod3)k+30(mod7)k+70(mod5)or{k+10(mod2)k+30(mod5)k+50(mod7)k+70(mod3) \begin{cases} k + 1 \equiv 0 \pmod{2} \\ k + 5 \equiv 0 \pmod{3} \\ k + 3 \equiv 0 \pmod{7} \\ k + 7 \equiv 0 \pmod{5} \end{cases} \quad \text{or} \quad \begin{cases} k + 1 \equiv 0 \pmod{2} \\ k + 3 \equiv 0 \pmod{5} \\ k + 5 \equiv 0 \pmod{7} \\ k + 7 \equiv 0 \pmod{3} \end{cases}

By the Chinese remainder theorem, each of these systems has infinitely many solutions; in each case, two solutions differ by a multiple of 2357=2102 \cdot 3 \cdot 5 \cdot 7 = 210. The least positive solution of the former is 193193, and the least positive solution of the latter is 107107.

To enlarge the set {3,5,7,193}\{3, 5, 7, 193\} to a 5-element special set by adjoining a positive odd integer kk, notice again that kk divides no 2-term sum from {3,5,7,193}\{3, 5, 7, 193\}, to infer that kk satisfies the system of linear congruences

{k+10(mod2)k+30(mod5)k+50(mod7)k+70(mod3)k+70(mod193); \begin{cases} k+1 \equiv 0 \pmod{2} \\ k+3 \equiv 0 \pmod{5} \\ k+5 \equiv 0 \pmod{7} \\ k+7 \equiv 0 \pmod{3} \\ k+7 \equiv 0 \pmod{193} \end{cases} ;

clearly, 33 and 55 both divide k+193k+193. As before, the Chinese remainder theorem settles the case; incidentally, the least positive solution is 34673467, and all five numbers are prime.

Similarly, the set {3,5,7,107}\{3, 5, 7, 107\} extends to a 5-element special set by adjoining any positive odd integer kk satisfying the system of linear congruences

{k+10(mod2)k+50(mod3)k+30(mod7)k+70(mod5)k+70(mod107); \begin{cases} k+1 \equiv 0 \pmod{2} \\ k+5 \equiv 0 \pmod{3} \\ k+3 \equiv 0 \pmod{7} \\ k+7 \equiv 0 \pmod{5} \\ k+7 \equiv 0 \pmod{107} \end{cases} ;

clearly, 33 and 55 both divide k+107k+107. In this case, the least positive solution is 10693=1723710693 = 17^2 \cdot 37.

Remark. The 5-element special sets below are obtained in the same way:
{3,5,13,127,17267=31557},{3,5,17,97,14353=31463}, \{3, 5, 13, 127, 17267 = 31 \cdot 557\}, \quad \{3, 5, 17, 97, 14353 = 31 \cdot 463\},
{3,7,11,235=547,26309},{3,7,11,437=1923,60295=531389}. \{3, 7, 11, 235 = 5 \cdot 47, 26309\}, \quad \{3, 7, 11, 437 = 19 \cdot 23, 60295 = 5 \cdot 31 \cdot 389\}.

We now show that the special set consisting of 33, 55, 1313, 1717 is maximal. Suppose, if possible, that kk is a positive odd integer such that 33, 55, 1313, 1717, kk form a special set. It is easily seen that kk divides no 2-term sum from {3,5,13,17}\{3, 5, 13, 17\}.

We first show that k+5k+5 is divisible by 33 if and only if k+3k+3 is divisible by 55; since one holds, so does the other.

If k+5k+5 is divisible by 33, then k+13k+13 is not, so k+3k+3 is divisible by 1313. It follows that k+5k+5 is not divisible by 1313, so k+13k+13 is divisible by 55, showing that k+3k+3 is indeed divisible by 55.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.