Задачи и олимпиады по математике

Задача

Дан произвольный набор из +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,

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

Ответ

Ответ задачи отсутствует

Задача

Решение

Ответ

Подтверждение удаления