|
|
 |
Условие
В концах отрезка пишутся две единицы. Посередине между ними пишется их сумма – число 2. Затем посередине между каждыми двумя соседними из написанных чисел снова пишется их сумма и так далее 1973 раза. Сколько раз будет написано число 1973?
Решение
Выпишем подряд строки чисел, образующиеся в результате очередного шага. Получим некоторую таблицу. Попробуем выяснить, сколько раз в n-й строке этой таблицы встретится число n (понятно, что в каждой следующей строке – с номером, большим n, – число n будет встречаться точно столько же раз, сколько и в n-й: все вновь образующиеся числа будут уже больше n).
Будем говорить, что в нашей таблице встречается пара натуральных чисел (a, b), если числа a и b стоят рядом в одной строке, причём b справа от a.
Лемма. Если натуральные числа а и b взаимно просты, то пара (a, b) встречается в таблице ровно один раз; если же a и b имеют общий делитель (отличный от 1), то пара (a, b) не встретится в таблице ни разу.
Доказательство. Индукция по m = max{a, b}. База (m = 2) очевидна.
Шаг индукции. Пусть a ≤ b = m (случай a > b аналогичен). Пара (a, b) может встретиться в таблице в том и только том случае, когда в ней встречалась пара
(а, b − a). Числа (a, b) и (a, b − a) являются одновременно либо взаимно простыми, либо нет. Для пары (a, b − a) утверждение справедливо по предположению индукции. Поэтому утверждение верно и для пары (a, b).
Каждый раз, когда n пишется как сумма двух соседних чисел a и b = n − a, оно встречается в парах (a, n) и ( n, n − a). Мы доказали, что это
бывает ровно один раз для каждого а, меньшего n и взаимно простого с ним (тогда, конечно, и n − a взаимно просто с n). Итак, каждое число n будет написано на отрезке столько раз, сколько существует натуральных чисел, меньших n и взаимно простых с ним.
Число 1973 – простое, поэтому оно встретится 1972 раза.
Ответ
1972 раза.
