РЕШУ ОЛИМП — математика

Задания

По кругу записаны 2ⁿ неотрицательных целых чисел a₁, a₂, ..., a_2ⁿ. Далее все числа a_i одновременно заменяются на числа $|a_i плюс 1 минус a_i|,$ где $a_2 в степени n плюс 1=a_1.$ Докажите, что в результате этого процесса все числа рано или поздно станут нулями.

2ⁿ non-⁠negative integers a₁, a₂, ..., a_2ⁿ are written in a circle. Then all the numbers a_i are simult aneously replaced by the numbers $|a_i плюс 1 минус a_i|,$ where $a_2 в степени n плюс 1=a_1.$ Prove that as a result of this process, all the numbers sooner or later become zeros.

Решение. Заметим, что на каждом шаге максимальное число в наборе не увеличивается, то есть если в некоторый момент времени максимальное число станет равно 0, то и все остальные числа тоже будут равны 0. Предположим, что максимальное число в нашем наборе в результате операций перестало меняться и стало равно $m больше 0.$ Для удобства заменим числа m на числа 1, и будем рассматривать все числа как остатки по модулю 2. Тогда, если мы в какой-⁠то момент получим только нулевые остатки, это будет означать, что все числа обратились в нули.

Докажем индукцией по k, что после k-⁠го шага для всех $i=1, 2, 3, \ldots, 2 в степени n$ будет выполнено

$a_i в степени левая круглая скобка левая круглая скобка k правая круглая скобка правая круглая скобка \equiv \sum_j=0 в степени k C_k в степени j умножить на a_ левая круглая скобка i плюс j правая круглая скобка левая круглая скобка mod 2 в степени n правая круглая скобка левая круглая скобка mod 2 правая круглая скобка .$

База индукции $k=1:$ $a_i в степени левая круглая скобка левая круглая скобка 1 правая круглая скобка правая круглая скобка \equiv |a_i плюс 1 минус a_i| \equiv a_i плюс a_i плюс 1 левая круглая скобка mod 2 правая круглая скобка .$

Индукционная гипотеза: пусть утверждение выполнено для $1, 2, \ldots, k.$ Шаг индукции:

$a_i в степени левая круглая скобка левая круглая скобка k плюс 1 правая круглая скобка правая круглая скобка \equiv |a_i плюс 1 в степени левая круглая скобка левая круглая скобка k правая круглая скобка правая круглая скобка минус a_i в степени левая круглая скобка левая круглая скобка k правая круглая скобка правая круглая скобка | \equiv a_i плюс 1 в степени левая круглая скобка левая круглая скобка k правая круглая скобка правая круглая скобка плюс a_i в степени левая круглая скобка левая круглая скобка k правая круглая скобка правая круглая скобка \equiv \sum_j=0 в степени k C_k в степени j умножить на a_ левая круглая скобка i плюс j правая круглая скобка левая круглая скобка mod 2 в степени n правая круглая скобка плюс \sum_j=0 в степени k C_k в степени j умножить на a_ левая круглая скобка i плюс j плюс 1 правая круглая скобка левая круглая скобка mod 2 в степени n правая круглая скобка \equiv \sum_j=0 в степени k C_k в степени j умножить на a_ левая круглая скобка i плюс j правая круглая скобка левая круглая скобка mod 2 в степени n правая круглая скобка плюс \sum_j=1 в степени левая круглая скобка k плюс 1 правая круглая скобка C_k в степени левая круглая скобка j минус 1 правая круглая скобка умножить на a_ левая круглая скобка i плюс j правая круглая скобка левая круглая скобка mod 2 в степени n правая круглая скобка \equiv \sum_j=0 в степени левая круглая скобка k плюс 1 правая круглая скобка левая круглая скобка C_k в степени j плюс C_k в степени левая круглая скобка j минус 1 правая круглая скобка правая круглая скобка умножить на a_ левая круглая скобка i плюс j правая круглая скобка левая круглая скобка mod 2 в степени n правая круглая скобка \equiv \sum_j=0 в степени левая круглая скобка k плюс 1 правая круглая скобка C_k плюс 1 в степени j умножить на a_ левая круглая скобка i плюс j правая круглая скобка левая круглая скобка mod 2 в степени n правая круглая скобка левая круглая скобка mod 2 правая круглая скобка .$

Мы использовали известное тождество $C_k в степени j плюс C_k в степени левая круглая скобка j минус 1 правая круглая скобка =C_k плюс 1 в степени j .$ Индукция завершена.

Для $k=2 в степени n$ биномиальные коэффициенты $C_k в степени j$ четны для $j=1, 2, \ldots, k минус 1,$ при этом $C_k в степени 0 =C_k в степени k = 1.$ После $2 в степени n$ шагов имеем

$a_i в степени левая круглая скобка левая круглая скобка 2 в степени n правая круглая скобка правая круглая скобка \equiv a_i в степени левая круглая скобка левая круглая скобка 2 в степени n минус 1 правая круглая скобка правая круглая скобка плюс a_ левая круглая скобка i плюс 2 в степени n правая круглая скобка левая круглая скобка mod 2 в степени n правая круглая скобка в степени левая круглая скобка левая круглая скобка 2 в степени n минус 1 правая круглая скобка правая круглая скобка \equiv 2 умножить на a_i в степени левая круглая скобка левая круглая скобка 2 в степени n минус 1 правая круглая скобка правая круглая скобка \equiv 0 левая круглая скобка mod 2 правая круглая скобка ,$

то есть не более чем через $2 в степени n$ шагов все исходные числа обратятся в нули, что и требовалось доказать.

Note that at each step the maximum number in the set does not increase. By that if at some point the maximum number becomes 0, then all other numbers will also become 0. Let's assume that the maximum number in our set has stopped changing as a result of the operations and is now $m больше 0.$ For convenience, we'll replace the numbers m with the numbers 1 and consider all numbers as remainders modulo 2. Then, if at some point we only have zero remainders, this will mean that all numbers have become zero.

We prove by induction on k that after the k-⁠th step, for all $i=1,2,3 \ldots, 2 в степени n ,$

Base of induction for $k=1:$ $a_i в степени левая круглая скобка левая круглая скобка 1 правая круглая скобка правая круглая скобка \equiv |a_i плюс 1 минус a_i| \equiv a_i плюс a_i плюс 1 левая круглая скобка mod 2 правая круглая скобка .$

Induction hypothesis: let the statement hold for $1,2, \ldots, k.$ Induction step:

$a_i в степени левая круглая скобка левая круглая скобка k плюс 1 правая круглая скобка правая круглая скобка \equiv |a_i плюс 1 в степени левая круглая скобка левая круглая скобка k правая круглая скобка правая круглая скобка минус a_i в степени левая круглая скобка левая круглая скобка k правая круглая скобка правая круглая скобка | \equiv a_i плюс 1 в степени левая круглая скобка левая круглая скобка k правая круглая скобка правая круглая скобка плюс a_i в степени левая круглая скобка левая круглая скобка k правая круглая скобка правая круглая скобка \equiv \sum_j=0 в степени k \binomkj умножить на a_ левая круглая скобка i плюс j правая круглая скобка левая круглая скобка mod 2 в степени n правая круглая скобка плюс \sum_j=0 в степени k \binomkj умножить на a_ левая круглая скобка i плюс j плюс 1 правая круглая скобка левая круглая скобка mod 2 в степени n правая круглая скобка \equiv \sum_j=0 в степени k \binomkj умножить на a_ левая круглая скобка i плюс j правая круглая скобка левая круглая скобка mod 2 в степени n правая круглая скобка плюс \sum_j=1 в степени левая круглая скобка k плюс 1 правая круглая скобка \binomkj минус 1 умножить на a_ левая круглая скобка i плюс j правая круглая скобка левая круглая скобка mod 2 в степени n правая круглая скобка \equiv \sum_j=0 в степени левая круглая скобка k плюс 1 правая круглая скобка левая круглая скобка \binomkj плюс \binomkj минус 1 правая круглая скобка умножить на a_ левая круглая скобка i плюс j правая круглая скобка левая круглая скобка mod 2 в степени n правая круглая скобка \equiv \sum_j=0 в степени левая круглая скобка k плюс 1 правая круглая скобка \binomk плюс 1j умножить на a_ левая круглая скобка i плюс j правая круглая скобка левая круглая скобка mod 2 в степени n правая круглая скобка левая круглая скобка mod 2 правая круглая скобка .$

We've used the well-⁠known identity $\binomkj плюс \binomkj минус 1=\binomk плюс 1j.$ The induction is complete. For $k=2 в степени n ,$ the binomial coefficients $C_k в степени j$ are even for $j=1, 2, \ldots, k минус 1,$ while $C_k в степени 0 =C_k в степени k =1.$ After $2 в степени n$ steps, we have

i. e., after no more than $2 в степени n$ steps, all the original numbers will become zeros, as required.

Ключ