Выпишем подряд строки чисел, образующиеся в результате очередного шага. Получим некоторую таблицу. Попробуем выяснить, сколько раз в 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 раза.