Информация о задаче

Задача 78263

Темы:	[	Рекуррентные соотношения	]
	[	Принцип крайнего (прочее)	]
	[	Перебор случаев	]

Сложность: 4+
Классы: 8,9,10

Прислать комментарий

Условие

Дана четвёрка ненулевых чисел a, b, c, d. Из неё получается новая ab, bc, cd, da по следующему правилу: каждое число умножается на следующее, четвёртое — на первое. Из новой четвёрки по этому же правилу получается третья и т.д. Доказать, что в полученной последовательности четвёрок никогда не встретится вновь четверка a, b, c, d, кроме случая, когда a = b = c = d = 1.

Решение

Пусть, напротив, где-нибудь в построенной последовательности встретилась четвёрка (а, b, с, d). Покажем, что в этом случае все числа данной четвёрки положительны. Пусть сперва в четвёрке имеется одно отрицательное число, т. е. знаки в ней расположены так (с точностью до циклической перестановки):

+ + + - .

Рассмотрим тогда первые пять шагов исследуемого процесса:

1. + + + - 2. + + - - 3. + - + - 4. - - - - 5. + + + + .

Мы видим, что ни на каком шагу не получается четвёрка, содержащая одно отрицательное число (как исходная), а после пятого шага вообще все числа становятся положительными. Заметим, что мы попутно разобрали случай двух отрицательных членов: эти случаи соответствуют второму и третьему шагам разобранного примера (отрицательные числа стоят в четвёрке рядом или не рядом). Мы видели, что и в этих случаях повторения не возникает. Случай четырёх отрицательных чисел также разобран (четвёртый шаг примера). Осталось рассмотреть тот случай, когда лишь одно число в четвёрке положительно:

1. + - - - 2. - + + - 3. - + - + 4. - - - - 5. + + + + .

-->

1. 0, а, b, с; 2. 0, ab, bc, 0; 3. 0, аb²с, 0, 0; 4. 0, 0, 0, 0.

Рассмотрим теперь произведение чисел каждой четвёрки. У первой четвёрки оно равно abcd, у второй (abcd )², у третьей (abcd )⁴. Вообще у n -й четвёрки произведение чисел равно (abcd )^{2^{n - 1}}. Пусть теперь какие-то две различные четвёрки — с номерами k и l — совпадают. Отсюда следует, что (abcd )^{2^{k - 1}} = (abcd )^{2^{l - 1}} и, значит, abcd = 1. Рассмотрим далее любую четвёрку m, n, р, q из нашей последовательности. Произведение её чисел равно, как мы видели, 1: mnрq = 1. Из двух положительных чисел mn > 0 и рq > 0, произведение которых равно 1, одно, очевидно, должно быть не больше 1, а другое — не меньше 1. Пусть, для определённости, mn = $\alpha$ $\ge$ 1, рq = $\displaystyle {\frac{1}{\alpha}}$ $\displaystyle \le$ 1. Точно так же обстоит дело с числами nр и mq. Пусть nр = $\beta$ $\ge$ 1, mq = $\displaystyle {\frac{1}{\beta}}$ $\displaystyle \le$ 1 и пусть, для определённости, $\alpha$ $\ge$ $\beta$ . Рассмотрим следующие три четвёрки:

m n p q

mn = $\alpha$ np = $\beta$ pq = $\displaystyle {\frac{1}{\alpha}}$ mq = $\displaystyle {\frac{1}{\beta}}$

$\alpha$ $\beta$ $\displaystyle {\frac{\beta}{\alpha}}$ $\displaystyle {\frac{1}{\alpha\beta}}$ $\displaystyle {\frac{\alpha}{\beta}}$

$\beta^{2}_{}$ $\displaystyle {\frac{1}{\alpha^{2}}}$ $\displaystyle {\frac{1}{\beta^{2}}}$ $\alpha^{2}_{}$ .

В последней четвёрке наибольшее число равно, очевидно, $\alpha^{2}_{}$ , что не меньше $\alpha$ , так как $\alpha$ $\ge$ 1. В предыдущей четвёрке наибольшее число равно $\alpha$ $\beta$ , что также не меньше $\alpha$ . Мы видим, что наибольшее число в четвёрке с каждым шагом увеличивается, если $\alpha$ $\ne$ 1 и $\beta$ $\ne$ 1. Пусть теперь первая четвёрка совпала с некоторой четвёркой x, y, z, v. Если это — вторая четвёрка, то мы имеем: a = x = ab, b = у - bc, с = z = cd, d = v = ad, откуда b = c = d = a = l. Если же это — любая другая четвёрка, то, как мы видели, начиная со второй, четвёрки, наибольшее число в четвёрке увеличивается, если $\alpha$ $\ne$ 1 и $\beta$ $\ne$ 1. Допустить увеличения этого наибольшего числа мы не можем, так как в итоге у нас должна получиться четвёрка, равная исходной. Следовательно, $\alpha$ = 1, $\beta$ = 1, и, начиная со второй, все четвёрки состоят из единиц, в том числе и та четвёрка, которая совпадает с первой. Тем самым утверждение доказано.

Источники и прецеденты использования


олимпиада
Название	Московская математическая олимпиада
год
Номер	24
Год	1961
вариант
	1
Класс	8
Тур	2
задача
Номер	5