Разделы 
Дополнительно
Задача по математике - 3529
2019-06-12 
а) Дана четверка положительных чисел ($a, b, c, d$). Из нее получается новая ($ab, bc, cd, da$) по следующему правилу: каждое число умножается на следующее, четвертое - на первое. Из новой четверки по этому же правилу получается третья и т.д. Докажите, что в полученной последовательности четверок никогда не встретится ($a, b, c, d$), кроме случая, когда $a = b = c = d = 1$.
б) Дан произвольный набор из чисел 1 и -1 длиной $2^k$. Из него получается новый по следующему правилу: каждое число умножается на следующее за ним; последнее $2^k$-е число умножается на первое. С новым набором из 1 и -1 проделывается то же самое и т. д. Докажите, что в конце концов получится набор, состоящий из одних единиц.
Решение:
а) Предположим, что четверка ($a, b, c, d$) встретилась вновь.
Докажем сначала, что в этом случае $abcd = 1$.
Пусть $abcd = p$. Тогда произведение чисел второй четверки равно $p^2$, третьей - $p^4$, четвертой - $p^8, \cdots$. Ясно, что при $p \neq 1$ в последовательности произведений не будет двух одинаковых чисел и, следовательно, все получающиеся четверки будут различны. Таким образом, $p = 1$.
Теперь рассмотрим вторую четверку: $ab, bc, cd, da$; так как $abcd = 1$, то, как легко проверить, четвертой четверкой будет $b^2c^2, c^2d^2, d^2a^2, a^2b^2$. Таким образом, четвертая четверка получается из второй возведением в квадрат и перестановкой. Точно так же из четвертой получается шестая четверка, из шестой - восьмая и т. д.
Если среди чисел второй четверки не все равны единице, то наибольшее из них больше единицы. Тогда наибольшее из чисел $2n$-й четверки будет с ростом $n$ неограниченно увеличиваться, а это противоречит тому, что они периодически повторяются.
Итак, $ab = bc = cd = da = 1$, а отсюда уже легко получить, что $a = b = c = d = 1$.
б) При $n = 1$ утверждение задачи, очевидно, справедливо.
Предположим, что оно справедливо при $n = k$, и докажем его справедливость при $n = k + l$.
Запишем первые три строчки:
$x_1, x_2, x_3, x_4, \cdots, x_{2^{k+1}}$,
$x_1x_2, x_2x_3, x_3x_4, \cdots, x_{2^{k+1}}x_1$,
$x_1x_3, x_2x_4, x_3x_5, \cdots, x_{2^{k+1}}x_2$.
Легко видеть, что числа, стоящие на нечетных местах, и числа, стоящие на четных местах, образуют строчки, $x_1, x_3, \cdots, x_{2^{k+1} - 1}$ и $x_2, x_4, \cdots, x_{2^{k+1}}$, которые "через шаг" преобразуются так, как это требуется в условии, а так как по предположению индукции строчка длины $2^k$ в конце концов преобразуется в строчку из одних единиц, то и из исходной строчки длины $2^{k+1}$ получится строчка из одних единиц.
Можно доказать, что из строки $x$ длины $m = 2^k r$, где $r$ нечетно, тогда и только тогда получится строка из одних единиц, когда $x$ состоит из $r$ одинаковых блоков длины $2^k$, т. е. имеет период $2^k$.
а) Дана четверка положительных чисел ($a, b, c, d$). Из нее получается новая ($ab, bc, cd, da$) по следующему правилу: каждое число умножается на следующее, четвертое - на первое. Из новой четверки по этому же правилу получается третья и т.д. Докажите, что в полученной последовательности четверок никогда не встретится ($a, b, c, d$), кроме случая, когда $a = b = c = d = 1$.
б) Дан произвольный набор из чисел 1 и -1 длиной $2^k$. Из него получается новый по следующему правилу: каждое число умножается на следующее за ним; последнее $2^k$-е число умножается на первое. С новым набором из 1 и -1 проделывается то же самое и т. д. Докажите, что в конце концов получится набор, состоящий из одних единиц.
Решение:
а) Предположим, что четверка ($a, b, c, d$) встретилась вновь.
Докажем сначала, что в этом случае $abcd = 1$.
Пусть $abcd = p$. Тогда произведение чисел второй четверки равно $p^2$, третьей - $p^4$, четвертой - $p^8, \cdots$. Ясно, что при $p \neq 1$ в последовательности произведений не будет двух одинаковых чисел и, следовательно, все получающиеся четверки будут различны. Таким образом, $p = 1$.
Теперь рассмотрим вторую четверку: $ab, bc, cd, da$; так как $abcd = 1$, то, как легко проверить, четвертой четверкой будет $b^2c^2, c^2d^2, d^2a^2, a^2b^2$. Таким образом, четвертая четверка получается из второй возведением в квадрат и перестановкой. Точно так же из четвертой получается шестая четверка, из шестой - восьмая и т. д.
Если среди чисел второй четверки не все равны единице, то наибольшее из них больше единицы. Тогда наибольшее из чисел $2n$-й четверки будет с ростом $n$ неограниченно увеличиваться, а это противоречит тому, что они периодически повторяются.
Итак, $ab = bc = cd = da = 1$, а отсюда уже легко получить, что $a = b = c = d = 1$.
б) При $n = 1$ утверждение задачи, очевидно, справедливо.
Предположим, что оно справедливо при $n = k$, и докажем его справедливость при $n = k + l$.
Запишем первые три строчки:
$x_1, x_2, x_3, x_4, \cdots, x_{2^{k+1}}$,
$x_1x_2, x_2x_3, x_3x_4, \cdots, x_{2^{k+1}}x_1$,
$x_1x_3, x_2x_4, x_3x_5, \cdots, x_{2^{k+1}}x_2$.
Легко видеть, что числа, стоящие на нечетных местах, и числа, стоящие на четных местах, образуют строчки, $x_1, x_3, \cdots, x_{2^{k+1} - 1}$ и $x_2, x_4, \cdots, x_{2^{k+1}}$, которые "через шаг" преобразуются так, как это требуется в условии, а так как по предположению индукции строчка длины $2^k$ в конце концов преобразуется в строчку из одних единиц, то и из исходной строчки длины $2^{k+1}$ получится строчка из одних единиц.
Можно доказать, что из строки $x$ длины $m = 2^k r$, где $r$ нечетно, тогда и только тогда получится строка из одних единиц, когда $x$ состоит из $r$ одинаковых блоков длины $2^k$, т. е. имеет период $2^k$.
