Разделы 
Дополнительно
Задача по математике - 2907
2019-05-06 
Рассмотрим следующую последовательность наборов (натуральных) чисел. Первый набор $I_0$ образуют две единицы 1, 1. Затем между этими числами вставим их сумму $1 + 1 = 2$; мы получим набор $I_1 : 1, 2, 1$. Потом между каждыми двумя из чисел набора $I_1$ вставим сумму этих чисел; мы получим набор $I_2 : 1, 3, 2, 3, 1$; затем, поступая таким же образом и с набором $I_2$, мы придем к набору $I_3 : 1, 4, 3, 5, 2, 5, 3, 4, 1$, и т. д. Сколько раз в миллионном наборе $I_{1000000}$ встретится число 1973?
Решение:
Заметим, прежде всего, что каждый из наборов $I_0$, $I_1$, $I_2, \cdots$ получается из предшествующего добавлением к нему некоторого количества новых чисел; при этом все ранее имевшиеся числа в новом наборе сохраняются. Легко видеть, далее, что все вновь появляющиеся в наборе $I_n$ числа будут больше $n$; поэтому число 1973 в наборах с номерами, большими 1973, уже не возникает - и все такие наборы содержат одно и то же количество чисел 1973. Докажем теперь, что фиксированная пара чисел $a$, $b$ (где $а$ стоит, скажем, слева от $b$; таким образом, $a$, $b$ и $b$, а мы считаем разными парами!) встретится в последовательности $I_0, I_1, I_2, \cdots, I_n, \cdots$ наборов ровно один раз, если числа $а$ и $b$ взаимно просты, и не встретится ни разу в противном случае. Это утверждение очевидно для пар чисел $а$, $b$, наибольшее из которых не превосходит 2 (таких пар имеется всего две: 1, 2 и 2, 1 - и встречается каждая из этих пар один лишь раз, а именно, в последовательности $I_1: 1, 2, 1$); докажем его методом математической индукции. Предположим, что наше утверждение уже доказано для всех таких пар чисел $a$, $b$ что $max [a,b] < n$, и покажем что оно будет справедливо и для пар $а$, $b$, где $max [a,b] = n$. В самом деле, пусть $a$, $b$ - пара целых положительных чисел, где, скажем, $max [a,b] = b = n$. Ясно, что пара $a$, $b$ может появиться в каком-то наборе $I_k$ лишь в том случае, если в предыдущем наборе $I_{k-1}$ мы имели пару стоящих рядом чисел $a$, $b-a$. Но поскольку $max [a,b-a] < max [a,b] (=b=n)$, то в силу предположения индукции пара чисел $а$, $b-a$ встречалась в наших наборах $I_1, \cdots, I_{k-1}$ один раз, если $а$ и $b$ взаимно просты, и ни разу, если $а$ и $b-a$ имеют общий делитель $d>1$. Ho отсюда сразу следует, что и пара чисел $а$, $b$ встречается в наших наборах один раз, если $а$ и $b$ взаимно просты, и не встречается вовсе в противном случае: ведь числа $а$ и $b$ взаимно просты в том и только в том случае, если взаимно простыми являются числа $а$ и $b-a$.
Теперь уже ясно, что поскольку число 1973 - простое (проверьте это!), в наших наборах по одному разу встретится каждая из пар чисел $1,1972; 2,1971; 3,1970; \cdots ; 1971,2; 1972,1$ - ведь все это суть пары взаимно простых чисел. А отсюда следует, что число 1973 встречается в наборах $I_n$ с номерами $n > 1973$ (в частности, в наборе $I_{1000000}$) ровно 1972 раза (это число равно количеству пар $1,1972; 2,1971; \cdots ; 1972,1$).
Рассмотрим следующую последовательность наборов (натуральных) чисел. Первый набор $I_0$ образуют две единицы 1, 1. Затем между этими числами вставим их сумму $1 + 1 = 2$; мы получим набор $I_1 : 1, 2, 1$. Потом между каждыми двумя из чисел набора $I_1$ вставим сумму этих чисел; мы получим набор $I_2 : 1, 3, 2, 3, 1$; затем, поступая таким же образом и с набором $I_2$, мы придем к набору $I_3 : 1, 4, 3, 5, 2, 5, 3, 4, 1$, и т. д. Сколько раз в миллионном наборе $I_{1000000}$ встретится число 1973?
Решение:
Заметим, прежде всего, что каждый из наборов $I_0$, $I_1$, $I_2, \cdots$ получается из предшествующего добавлением к нему некоторого количества новых чисел; при этом все ранее имевшиеся числа в новом наборе сохраняются. Легко видеть, далее, что все вновь появляющиеся в наборе $I_n$ числа будут больше $n$; поэтому число 1973 в наборах с номерами, большими 1973, уже не возникает - и все такие наборы содержат одно и то же количество чисел 1973. Докажем теперь, что фиксированная пара чисел $a$, $b$ (где $а$ стоит, скажем, слева от $b$; таким образом, $a$, $b$ и $b$, а мы считаем разными парами!) встретится в последовательности $I_0, I_1, I_2, \cdots, I_n, \cdots$ наборов ровно один раз, если числа $а$ и $b$ взаимно просты, и не встретится ни разу в противном случае. Это утверждение очевидно для пар чисел $а$, $b$, наибольшее из которых не превосходит 2 (таких пар имеется всего две: 1, 2 и 2, 1 - и встречается каждая из этих пар один лишь раз, а именно, в последовательности $I_1: 1, 2, 1$); докажем его методом математической индукции. Предположим, что наше утверждение уже доказано для всех таких пар чисел $a$, $b$ что $max [a,b] < n$, и покажем что оно будет справедливо и для пар $а$, $b$, где $max [a,b] = n$. В самом деле, пусть $a$, $b$ - пара целых положительных чисел, где, скажем, $max [a,b] = b = n$. Ясно, что пара $a$, $b$ может появиться в каком-то наборе $I_k$ лишь в том случае, если в предыдущем наборе $I_{k-1}$ мы имели пару стоящих рядом чисел $a$, $b-a$. Но поскольку $max [a,b-a] < max [a,b] (=b=n)$, то в силу предположения индукции пара чисел $а$, $b-a$ встречалась в наших наборах $I_1, \cdots, I_{k-1}$ один раз, если $а$ и $b$ взаимно просты, и ни разу, если $а$ и $b-a$ имеют общий делитель $d>1$. Ho отсюда сразу следует, что и пара чисел $а$, $b$ встречается в наших наборах один раз, если $а$ и $b$ взаимно просты, и не встречается вовсе в противном случае: ведь числа $а$ и $b$ взаимно просты в том и только в том случае, если взаимно простыми являются числа $а$ и $b-a$.
Теперь уже ясно, что поскольку число 1973 - простое (проверьте это!), в наших наборах по одному разу встретится каждая из пар чисел $1,1972; 2,1971; 3,1970; \cdots ; 1971,2; 1972,1$ - ведь все это суть пары взаимно простых чисел. А отсюда следует, что число 1973 встречается в наборах $I_n$ с номерами $n > 1973$ (в частности, в наборе $I_{1000000}$) ровно 1972 раза (это число равно количеству пар $1,1972; 2,1971; \cdots ; 1972,1$).
