Доказательство для активации битов

[kthxbye]

Имеем бинарный массив длины $2n$. Мы можем активировать любые биты. При активации бита соседние биты меняют свои значения $0\to1$, $1\to0$. Наша цель - превратить исходный бинарный массив в массив из одних только единиц через активацию битов. Доказать, что при любом значении бинарного массива это возможно максимум за $2n$ активаций.

Имеем бинарный массив длины $4n+1$. Можем активировать любые биты и т.д. Доказать, что массив можно привести к массиву из одних только единиц если значение массива принадлежит последовательности A158705 (положительные целые с нечетным количеством нечетных степеней $2$-ки в двоичной записи $n$) максимум за $4n+1$ активаций. Доказать также, что это невозможно, если значение массива принадлежит последовательности A158704 (положительные целые с четным количеством нечетных степеней $2$-ки в двоичной записи $n$).

Имеем бинарный массив длины $4n+3$. Можем активировать любые биты и т.д. Доказать, что массив можно привести к массиву из одних только единиц если значение массива принадлежит последовательности A158704 максимум за $4n+1$ активаций. Доказать также, что это невозможно, если значение массива принадлежит последовательности A158705.

[worm2]

Не совсем понятно, что значит "активировать бит".
Можно на примере показать? Вот у нас массив из четырёх элементов: 0101.
Что будет, если мы "активируем" первый элемент? А если второй? третий? четвёртый?

Т.е. понятно, что происходит с соседними элементами (но тоже не до конца: вдруг элементы "циклически заворачиваются" и соседом справа для самого правого будет самый левый?).
А сам активируемый бит, он не меняется? устанавливается в 1? или меняется на противоположный?

[kthxbye]

Массив из 4-х элементов, 0101. При активации

1-го бита 0001
2-го бита 1111
3-го бита 0000
4-го бита 0111

Элементы циклически не заворачиваются. Сам активируемый бит не меняется.

[mihaild]

То есть мы можем инвертировать второй бит, предпоследний, и два, отстоящих друг от друга на один?
Это получается вопрос о разрешимости в $\mathbb Z_2$ системы уравнений с явно выписываемой матрицей. Ну и при нечетной длине письма у четные и нечетные разряды меняются независимо.

[kthxbye]

Если элементы циклически заворачиваются, т.е. у первого элемента соседи это второй и последний, а у последнего - предпоследний и первый, то для бинарного массива длины $2n+1$ массив можно привести к массиву из одних только единиц если значение массива принадлежит последовательности A000069 (числа с нечетным числом единиц в их $2$-ном разложении). Для $4n$ и $4n+2$ в энциклопедии последовательностей не нашлось.

[kthxbye]

mihaild в сообщении #1493287 писал(а):

Это получается вопрос о разрешимости в $\mathbb Z_2$ системы уравнений с явно выписываемой матрицей. Ну и при нечетной длине письма у четные и нечетные разряды меняются независимо.

Можно чуть подробнее?

Мой метод нахождения результата состоит в следующем:
1) генерирую в Excel все перестановки длины $n$
2) под каждую перестановку создаю массив длины $n$ из единиц
3) с помощью нехитрых формул активирую бит, номер которого - первый элемент перестановки
4) сохраняю значения всех получившихся бинарных массивов, удаляю дубликаты
5) аналогично активирую бит, номер которого - второй элемент перестановки, далее аналогично п.4
6) продолжаю активировать биты, по итогам все сохраненные значения помещаю в один столбец, удаляю дубликаты, имею:
а) все числа для массивов длины $2n$
б) A158705 для массивов длины $4n+1$
в) A158704 для массивов длины $4n+3$
г) A000069 для массивов длины $2n+1$ (с небольшой корректировкой нехитрых формул)

Идеей для этой конструкции послужил 21-ый уровень логической игры yellow от разработчика Bart Bonte. Между делом, всем рекомендую. Игра примечательна тем, что в ней сперва необходимо разобраться что от нас требуется, а уже потом как это, собственно, сделать. У этого разработчика целая серия игр с названиями цветов из которых можно красть идеи черпать вдохновение. Так, 49-ый уровень игры red, с которой я познакомился весной 2018 года, сподвигнул меня на экспериментальные исследования, опубликованные в темах Описание подхода получения результата и восполнение пробела, Подкрепление опытных результатов логикой, Доказательство рекуррентной формулы.

[mihaild]

kthxbye в сообщении #1493379 писал(а):

1) генерирую в Excel все перестановки длины $n$

Причем тут перестановки?

kthxbye в сообщении #1493379 писал(а):

Можно чуть подробнее?

Вы знаете, что такое система линейных уравнений?
Очевидно, что порядок активации битов неважен (активация сначала $a$, потом $b$ или сначала $b$ потом $a$ дает один и тот же результат), и что активировать один бит больше одного раза не надо. Давайте заведем $n$ бинарных переменных $a_i$, где $a_i = 1$ если мы будем активировать $i$-й бит, и $a_i = 0$ иначе. Как выглядит условие "мы в итоге получаем вот такое число"?