Croatian Mathematical Olympiad

Question

Prove that, for every positive integer n 2, there exist positive integers a_1, a_2, , a_n such that for all 1 i < j n the expression a_j + a_ia_j - a_i is a positive integer.

Accepted Answer

We will prove the claim using mathematical induction on

n

. We will call the set

{a_{1}, a_{2}, \dots, a_{n}}

good if it satisfies the given condition.

For

n = 2

the set

{1, 2}

is clearly good. Let us assume that for some positive integer

n \geq 2

there exists a good set

{a_{1}, a_{2}, \dots, a_{n}}

. Let

a

be the least common multiple of the set

{a_{1}, a_{2}, \dots, a_{n}} \cup {a_{j} - a_{i} ∣ 1 \leq i < j \leq n} .

We claim that the set

{a, a + a_{1}, a + a_{2}, ..., a + a_{n}}

, containing

n + 1

elements, is also good.

Notice that for all

i \in {1, 2, ..., n}

we have

\frac{( a + a _{i} ) + a}{( a + a _{i} ) - a} = \frac{2 a + a _{i}}{a _{i}} = 2 \frac{a}{a _{i}} + 1,

which is a positive integer since

a

is divisible by

a_{i}

(by definition).

Moreover, for all

1 \leq i < j \leq n

we have

\frac{( a + a _{j} ) + ( a + a _{i} )}{( a + a _{j} ) - ( a + a _{i} )} = \frac{2 a + ( 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.