Задача 66151
|
|
 |
Условие
На доске написаны n > 3 различных натуральных чисел, меньших чем (n – 1)!. Для каждой пары этих чисел Серёжа поделил большее на меньшее с остатком и записал в тетрадку полученное неполное частное (так, если бы он делил 100 на 7, то он бы получил 100 = 14·7 + 2 и записал бы в тетрадку число 14). Докажите, что среди чисел в тетрадке найдутся два равных.
Решение
Предположим противное. Пусть a1, a2, ..., an – числа на доске в порядке возрастания, а qi – неполное частное от деления ai+1 на ai (i = 1, 2, ...,
n – 1); тогда ai+1 ≥ qiai. Так как все qi различны, то q1q2...qn–1 ≥ (n – 1)!. Значит, an/a1 = an/an–1·an–1/an–2·...·a2/a1 ≥ q1q2...qn–1 ≥ (n – 1)!. Но это невозможно, поскольку a1 и an – натуральные числа, меньшие (n – 1)!.
