Maths Olympiad Prep

Library / /8 of 22

Number theory Difficulty 6.1 National olympiad Prove it Croatia

Prove that, for every positive integer n2n \ge 2, there exist positive integers a1,a2,,ana_1, a_2, \dots, a_n such that for all 1i<jn1 \le i < j \le n the expression
aj+aiajai \frac{a_j + a_i}{a_j - a_i}
is a positive integer.

Solution

We will prove the claim using mathematical induction on nn. We will call the set {a1,a2,,an}\{a_1, a_2, \dots, a_n\} good if it satisfies the given condition.

For n=2n=2 the set {1,2}\{1,2\} is clearly good. Let us assume that for some positive integer n2n \ge 2 there exists a good set {a1,a2,,an}\{a_1, a_2, \dots, a_n\}. Let aa be the least common multiple of the set
{a1,a2,,an}{ajai1i<jn}. \{a_1, a_2, \dots, a_n\} \cup \{a_j - a_i \mid 1 \le i < j \le n\}.
We claim that the set {a,a+a1,a+a2,...,a+an}\{a, a+a_1, a+a_2, ..., a+a_n\}, containing n+1n+1 elements, is also good.

Notice that for all i{1,2,...,n}i \in \{1, 2, ..., n\} we have
(a+ai)+a(a+ai)a=2a+aiai=2aai+1, \frac{(a+a_i)+a}{(a+a_i)-a} = \frac{2a+a_i}{a_i} = 2\frac{a}{a_i} + 1,
which is a positive integer since aa is divisible by aia_i (by definition).

Moreover, for all 1i<jn1 \le i < j \le n we have
(a+aj)+(a+ai)(a+aj)(a+ai)=2a+(aj+ai)ajai=2aajai+aj+aiajai, \frac{(a+a_j)+(a+a_i)}{(a+a_j)-(a+a_i)} = \frac{2a+(a_j+a_i)}{a_j-a_i} = 2\frac{a}{a_j-a_i} + \frac{a_j+a_i}{a_j-a_i},
which is a positive integer as well.

This completes the inductive step, thereby proving the claim.

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 and solution reproduced as published; topic and difficulty added by this site.