Задача 78714
|
|
 |
Условие
Из натуральных чисел составляются последовательности, в которых каждое последующее число больше квадрата предыдущего, а последнее число в последовательности равно 1969 (последовательности могут иметь разную длину). Доказать, что различных последовательностей такого вида меньше чем 1969.Решение
Докажем индукцией по n, что при n ≥ 3 количество последовательностей, оканчивающихся на n, меньше n. (Для n = 1 и 2 количество таких последовательностей равно n.) Рассмотрим последовательность, оканчивающуюся на n, и отбросим её последний член. Для всех последовательностей, состоящих более, чем из одного члена n, получаем последовательности, оканчивающиеся на 1, 2, ...,
[].
Поэтому по предположению индукции количество всех последовательностей, оканчивающихся на n, не превосходит
1 + 1 + 2 + ... + [] = 1 +
. При n ≥ 3 это число меньше n.
