Задача 78272

Темы:    [ Рекуррентные соотношения ] [ Индукция (прочее) ]

Сложность: 4 Классы: 10,11

Условие

Дан произвольный набор из +1 и -1 длиной 2^k. Из него получается новый по следующему правилу: каждое число умножается на следующее за ним; последнее 2^k-тое число умножается на первое. С новым набором из 1 и -1 проделывается то же самое и т.д. Доказать, что в конце концов получается набор, состоящий из одних единиц.

Решение

Рассмотрим несколько первых шагов исследуемого процесса. Исходный набор:

a₁, a₂, a₃, a₄,..., a_2^k.

Набор, полученный после первого шага:

a₁a₂,  a₂a₃,  a₃a₄,  ...,  a_2^ka₁.

Набор, получившийся после второго шага:

a₁a₃,  a₂a₄,  ...,  a_2^ka₂

(так как а²_i = 1). Итак, после двух шагов мы приходим к набору, числа которого получаются из чисел исходного набора умножением через одно. Ещё через два шага с этим набором произойдёт то же самое, т. е. мы получим набор:

a₁a²₃a₅,  a₂a²₄a₆,  ...,

или, иначе говоря, набор:

a₁a₅,  a₂a₄,  a₃a₇,  ...,  a_2^ka₄.

Итак, в результате четырёх шагов мы приходим к набору, числа которого получаются из чисел исходного набора умножением через 3. Ещё через 4 шага с этим последним набором произойдет то же самое, т. е. мы получим набор

a₁a²₅a₉,  a₂a²₆a₁₀,  ...,

или, иначе говоря, набор

a₁a₉,  a₂a₁₀,  a₃a₁₁,  ...,  a_2^ka₈.

Вообще, после 2^p шагов мы получим набор

a₁a_{2^{p + 1}},  a₂a_{2^{p + 2}},  ...,  a_2^ka_2^p,

что легко доказывается по индукции. В частности, после 2^{k - l} шагов мы получим набор:

a₁a_{2^{k - 1} + 1},  a₂a_{2^{k - 1} + 2},  ...,  a_2^ka_{2^{k - 1}},

а ещё после 2^{k - 1} шагов (т. е. всего после 2^k шагов) — набор,

a²₁,  a²₂,  ...,  a²_2^k,

состоящий из одних единиц.

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

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