Maths Olympiad Prep

Library / /17 of 25

Number theory Difficulty 6.8 National olympiad Prove it Russia

n>3n > 3 distinct positive integers are written on a board, all these numbers are smaller than (n1)!=12(n1)(n-1)! = 1 \cdot 2 \cdot \dots \cdot (n-1). For each pair a>ba > b of these numbers, Sergey found a partial quotient of aa by bb and wrote up the result into his notebook (e.g., if a=100a = 100 and b=7b = 7, then 100=147+2100 = 14 \cdot 7 + 2, so Sergey would write the number 14 into the notebook). Prove that the notebook contains two equal numbers.

n>3n > 3 различных положительных целых чисел записаны на доске, все эти числа меньше (n1)!=12(n1)(n-1)! = 1 \cdot 2 \cdot \dots \cdot (n-1). Для каждой пары a>ba > b из этих чисел Сергей нашёл неполное частное от деления aa на bb и записал результат в тетрадь (например, если a=100a = 100 и b=7b = 7, то 100=147+2100 = 14 \cdot 7 + 2, и Сергей запишет число 14 в тетрадь). Докажите, что в тетради окажутся два одинаковых числа.

Solutions — 2

Solution 1

Enumerate the numbers in increasing order: a1<a2<<ana_1 < a_2 < \dots < a_n.

Suppose, for contradiction, that all the partial quotients qi,jq_{i,j} (for ai>aja_i > a_j) are distinct.

Consider the sequence of ratios:
anan1an1an2a2a1=ana1. \frac{a_n}{a_{n-1}} \cdot \frac{a_{n-1}}{a_{n-2}} \cdots \frac{a_2}{a_1} = \frac{a_n}{a_1}.

Each aia_i can be written as ai=qiai1+ria_i = q_i a_{i-1} + r_i, where 0ri<ai10 \leq r_i < a_{i-1} and qiq_i is the partial quotient of aia_i by ai1a_{i-1}.

Therefore,
aiai1=qi+riai1<qi+1. \frac{a_i}{a_{i-1}} = q_i + \frac{r_i}{a_{i-1}} < q_i + 1.

So,
ana1<(qn+1)(qn1+1)(q2+1). \frac{a_n}{a_1} < (q_n + 1)(q_{n-1} + 1) \cdots (q_2 + 1).

But since all qiq_i are distinct and positive, and an<(n1)!a_n < (n-1)!, the product (qn+1)(qn1+1)(q2+1)(q_n + 1)(q_{n-1} + 1) \cdots (q_2 + 1) must be less than (n1)!(n-1)! for n>3n > 3.

However, if all the partial quotients are distinct and positive, their product would be at least (n1)!(n-1)!, which is impossible since an<(n1)!a_n < (n-1)!.

Therefore, the notebook must contain two equal numbers.

Solution 2

Предположим противное. Пусть a1,a2,,ana_1, a_2, \dots, a_n — числа на доске в порядке возрастания. Пусть qiq_i — неполное частное от деления aia_i на ai1a_{i-1}, то есть ai=qiai1+ria_i = q_i a_{i-1} + r_i, 0ri<ai10 \leq r_i < a_{i-1}.

Тогда
ana1=anan1an1an2a2a1. \frac{a_n}{a_1} = \frac{a_n}{a_{n-1}} \cdot \frac{a_{n-1}}{a_{n-2}} \cdots \frac{a_2}{a_1}.

Поскольку ai<(n1)!a_i < (n-1)!, а все qiq_i различны и положительны, произведение qnqn1q2q_n q_{n-1} \dots q_2 не меньше (n1)!(n-1)!. Но тогда an(n1)!a_n \geq (n-1)!, что невозможно, так как an<(n1)!a_n < (n-1)!.

Значит, в тетради окажутся два одинаковых числа.

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.