Замена элементов послед. -1, 1 на произведение соседних

[mathematician123]

Пусть $n$ - натуральное число. Последовательность $a_1, a_2, \ldots, a_n$ состоит только из чисел $-1, 1$. Данная последовательность преобразуется по следующим правилам: $a_i$ заменяется на $a_{i-1}a_{i+1}$, $2 \le i \le n - 1$; $a_1$, $a_n$ заменяются на соответственно $a_2$, $a_{n-1}$. То есть, число заменяется на произведение соседних членов. Будем применять это преобразование до тех пор, пока последовательность не зациклится. Для каких $n$ можно гарантировать, что после некоторого количества преобразований получим последовательность $1, 1, \ldots, 1$?

Я думаю, ответ $n = 2^m - 1$. Для $1 \le m \le 4$ проверил с помощью компьютера. Пытаюсь доказать по индукции. $2^m - 1 = 2(2^{m - 1} - 1) + 1$. Поэтому, если утверждение верно для $n = 2^{m - 1} - 1$, то все симметричные последовательности длины $2^m - 1$ преобразуются к последовательности единиц. Но остаются ещё не симметричные. Может быть, можно доказать, что любая последовательность после некоторого количества преобразований станет симметричной?

[gris]

вопрос для прояснения:
в последовательности последовательно заменяются все члены от первого до последнего, либо от второго до предпоследнего, а потом первый и последний, либо формируется новая последовательность?
[-1,-1,1,-1,1] переходит в [-1,-1,1-1,-1]
или
[-1,-1,1,-1,1] переходит в [-1,-1,1,1,1]
или
[-1,-1,1,-1,1] переходит в [-1,-1,1,-1,-1]

[mathematician123]

Формируется новая последовательность.

gris в сообщении #1604949 писал(а):

[1,-1,-1,-1,1] переходит в [-1,-1,1,-1,-1]

[gris]

я совсем запутался с этими единицыми.
Мне бы было привычнее писать
(-++-++-) — (+--+--+)
правильно?

[mathematician123]

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

[gris]

Вот это зацикливание без достижения плюсов.
- - + + -
- - - - +
- + + - -
+ - - - -
- - + + -
Интересно.

А это для $n=15$
+ + + - + - + - - - - - - + -
+ + - + + + + - + + + + - + +
+ - + - + + - + - + + - + - +
- + + + - - + + + - - + + + -
+ - + - - - - + - - - - + - +
- + + - + + - + - + + - + + -
+ - - + - - + + + - - + - - +
- - - + - - - + - - - + - - -
- + - + - + - + - + - + - + -
+ + + + + + + + + + + + + + +
Плюсы на 9-том шаге.

[Null]

1. Можно рассматривать последовательности по кругу:$A+\overline{A}+$ где $\overline{A}$ - отраженная последовательность. Для нее наша операция - это просто замена элемента на сумму соседних в $\mathbb{Z}_2$(Где + это 0 и - это 1). Получили Линейное пространство $L$ круговых последовательностей длинны $2n+2$ и его подпространство $L_1$ круговых последовательностей вида $X0\overline{X}0$
2. Возьмем элемент $L$ с одной 1. Несложно показать что через $2^k$ операций будут две 1 на расстоянии $2^{k+1}-1$(количество 0 между ними). Значит при $n=2^m-1$ через $2^m$ операций эти две $1$ взаимоуничтожатся. Значит и любой элемент из $L$ и $L_1$ обнулится.

[mathematician123]

Null
В решении разобрался. Красиво! А возможно ли доказать, что последовательность из одних минусов нельзя преобразовать к последовательности из плюсов, если $n \ne 2^m - 1$?

[gris]

красиво смотрится преобразование 63-х жёлтых минусов в красные плюсики


а если минусов 64...

[mathematician123]

mathematician123 в сообщении #1604975 писал(а):

А возможно ли доказать, что последовательность из одних минусов нельзя преобразовать к последовательности из плюсов, если $n \ne 2^m - 1$?

Если $n$ чётно, то никакую последовательность, содержащую минусы, нельзя преобразовать к последовательности из одних плюсов. Действительно, предположим мы получили строку из плюсов и посмотрим на последнее преобразование. Преобразование каких строк приводит к строке с плюсами? Ответ: только строки $-+-\ldots-+-$, количество элементов в которой нечётное.

[Null]

Ага анализ с конца.
Пусть $2n+2=2^sd$, где $d$ -нечетное. Рассмотрим элемент из $L$ и возьмем суммы элементов с периодом $2^s$ - получим новый круговой вектор длинны $d$ - обозначим это пространство $L_2$. Выполнение операции над элементом из $L$ ведет к выполнению операции над соответствующим элементом из $L_2$.
В $L_2$ перед последовательностью из одних $0$ могут быть только последовательности из одних $0$ или последовательности из одних $1$(эта последовательность может быть только на первом шаге). Дальше понятно: берем $X$, получаем $X0\overline{X}0$, сжимаем в $2^s$ раз. Если в результате есть и 0, и 1 тогда в нули мы никогда не уйдем.

[Null]

Последовательность из одних единиц после сжатия $X0\overline{X}0$ получиться не может(сумма четная)