Задача про единицы

[Fedya]

Доброго времени суток, уважаемые математики. Помогите, пожалуйста, решить такую задачу. В ряд, в произвольном порядке, записаны 1 или -1, (всего 20). Разрешается изменить знак у любых трех соседних чисел. При какой расстановке чисел можно (или нельзя) получить в ряду все единицы?

[kp9r4d]

А в каком виде надо дать ответ? По любому данному ряду можно легко сказать, можно ли получить все единицы или нет, так как, по сути, это система (не очень сложных) линейных уравнений над $\mathbb{F}_2$.

[Fedya]

В любом. Желательно наиболее простом.

[ET]

Откуда задача?
Определить действительно просто, тк доступные операции коммутируют и имеют порядок 2 (из чего можно ванговать, что ровно четверть таких последовательностей решаются). Просто тут ругаются на полное решение, а в олимпиадных задачах ругаются на задачи с действующей олимпиады

[Fedya]

это не задача, это тупиковый момент в размышлениях.

[ET]

Ну вот не знаю, поможет ли это, или это вам и так понятно, но...
Если просто абсолютно тупо слева (или справа) выстраивать единицы, то если последовательность решаема, она обязательно решится таким способом
То есть ищем первую слева неправильную цифру - переворачиваем от нее вправо 3 цифры идт итп. Если последовательность в принципе решаема, то такой алгоритм ее обязательно решит (это следует из коммутативности операции и того, что ее порядок равен 2)

[Fedya]

Это и так понятно. Но хотелось бы узнать какие-то начальные условия.

[kp9r4d]

Последовательность решаема тогда и только тогда, когда удовлетворяет условиям

$$\sum_{t=1}^{17} F_t x_{17-t+1} + \sum_{t=1}^{18} F_t x_{18-t+1} \equiv x_{19} (\operatorname{mod} 2)$$

$$\sum_{t=1}^{18} F_t x_{18-t+1} \equiv x_{20} (\operatorname{mod} 2)$$

Где $F_1 = 1, F_2 = 1, F_k = F_{k-1} + F_{k-2}$, а $x_i = 0$ если на $i$-ом месте стоит $1$ и $x_i = 1$ если на $i$-ом месте стоит $-1$.
Нумерация с единицы.

[Fedya]

kp9r4d

Спасибо большое!!! Буду разбираться.

[Keter]

kp9r4d, возможно ли такой метод обобщить для следующей задачи:

В таблице 20 на 14 произвольно записаны числа 1 или -1. За шаг возможно изменить числа на противоположные в квадрате 2 на 2 или 3 на 3. Можно ли сделать так, чтобы таблица состояла только из 1?

[arseniiv]

Все эти преобразования тоже коммутируют.

[Keter]

arseniiv, просто эта задача эквивалентна этой topic85365.html

Не могу понять, как соотнести эти решения...

[arseniiv]

Там, с первого взгляда, аналогичные суммы по модулю 2.