Maths Olympiad Prep

Track / Stage 6 / 126 of 400 #1606 of 2444

Problem 1606

National Olympiad, first round
Number theory Difficulty 6.1 Prove it Junior Balkan MO · JBMO

For any set A={x1,x2,x3,x4,x5}A=\{x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} of five distinct positive integers denote by SAS_{A} the sum of its elements, and denote by TAT_{A} the number of triples (i,j,k)(i, j, k) with 1i<j<k51 \leqslant i<j<k \leqslant 5 for which xi+xj+xkx_{i}+x_{j}+x_{k} divides SAS_{A}.
Find the largest possible value of TAT_{A}.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Solution:
We will prove that the maximum value that TAT_{A} can attain is 44. Let A={x1,x2,x3,x4,x5}A=\{x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} be a set of five positive integers such that x1<x2<x3<x4<x5x_{1}<x_{2}<x_{3}<x_{4}<x_{5}. Call a triple (i,j,k)(i, j, k) with 1i<j<k51 \leqslant i<j<k \leqslant 5 good if xi+xj+xkx_{i}+x_{j}+x_{k} divides SAS_{A}. None of the triples (3,4,5),(2,4,5),(1,4,5),(2,3,5),(1,3,5)(3,4,5),(2,4,5),(1,4,5),(2,3,5),(1,3,5) is good, since, for example
x5+x3+x1SAx5+x3+x1x2+x4 x_{5}+x_{3}+x_{1}\mid S_{A} \Rightarrow x_{5}+x_{3}+x_{1}\mid x_{2}+x_{4}
which is impossible since x5>x4x_{5}>x_{4} and x3>x2x_{3}>x_{2}. Analogously we can show that any triple of form (x,y,5)(x, y, 5) where y>2y>2 isn't good.

By above, the number of good triples can be at most 55 and only triples (1,2,5),(2,3,4)(1,2,5),(2,3,4), (1,3,4),(1,2,4),(1,2,3)(1,3,4),(1,2,4),(1,2,3) can be good. But if triples (1,2,5)(1,2,5) and (2,3,4)(2,3,4) are simultaneously good we have that:
x1+x2+x5x3+x4x5<x3+x4 x_{1}+x_{2}+x_{5} \mid x_{3}+x_{4} \Rightarrow x_{5}<x_{3}+x_{4}
and
x2+x3+x4x1+x5x2+x3+x4x1+x5<x1+x3+x4<x2+x3+x4, x_{2}+x_{3}+x_{4} \mid x_{1}+x_{5} \Rightarrow x_{2}+x_{3}+x_{4} \leqslant x_{1}+x_{5} < x_{1}+x_{3}+x_{4}<x_{2}+x_{3}+x_{4},
which is impossible. Therefore, TA4T_{A} \leqslant 4.

Alternatively, one can prove the statement above by adding up the two inequalities x1+x2+x4<x3+x4x_{1}+x_{2}+x_{4}<x_{3}+x_{4} and x2+x3+x4<x1+x5x_{2}+x_{3}+x_{4}<x_{1}+x_{5} that are derived from the divisibilities.

To show that TA=4T_{A}=4 is possible, consider the numbers 1,2,3,4,4941,2,3,4,494. This works because 6498,7497,84966|498,7|497,8|496, and 94959|495.

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