Задача о переключателях из тинькофф-финтеха

[mark apollo]

Перед вами расположена стена 112×112 с переключателями. Изначально все переключатели смотрят вверх. За одну операцию разрешается поменять состояние всех переключателей в любом кресте (объединение столбца и строки) на противоположное (т.е. если переключатель смотрел вверх, то теперь он смотрит вниз). Какое наименьшее количество операций потребуется, чтобы все переключатели смотрели вниз?

Для малых n можно подобрать ответы - для нечетных n, для четных по всей видимости $n^2$
Для n=3 минимальность числа операций доказать легко. А как обосновать угаданный ответ в общем случае?

[Sonic86]

(Оффтоп)

Я сначала в игре "Следствие ведут колобки" тоже не мог очень долго открыть долбаный холодильник.
А потом я выучил линал

Похоже, что это задача - на линейную алгебру над $\mathbb{Z}_2$. Дана матрица $n\times n$. В ней дан вектор $\bar{0}$ и вектор из одних единиц $x=\bar{1}$. И дан обычный базис $e_{ij}$ и новый базис $g_{ij}=\sum\limits_{k=1}^ne_{ik}+\sum\limits_{k=1}^ne_{kj} + e_{ij}$. Надо выразить вектор $x$ в новом базисе и вычислить сумму коэффициентов. Для начала надо исследовать матрицу перехода на невырожденность... (не знаю, как проще, но теоретически так можно решить )
Для четных $n$ система $g_{ij}$ будет линейно зависима, там надо искать ранг и выражать вектор - но тут проще даже руками.

upd: вычислим $\sum\limits_{i,j=1}^n g_{ij}$. Все понятно. Значит если при четном $n$ ранг матрицы равен $n^2$, то все понятно.
А вычислим-ка $\sum\limits_{k=1}^ng_{ik}+\sum\limits_{k=1}^ng_{kj}+g_{ij}$. Ну теперь вообще все понятно.

(а вот так люди решают эту задачу без линейной алгебры )

https://youtu.be/6LH1u3OuJdo?t=1531

[mark apollo]

Sonic86 в сообщении #1233104 писал(а):

$g_{ij}=\sum\limits_{k=1}^ne_{ik}+\sum\limits_{k=1}^ne_{kj} + e_{ij}$

У Вас в сумме $e_{ij}$ встречается аж три раза? это получается матрица, где на i,j-й позиции стоит три?

[svv]

Да, но в той алгебре, про которую говорил Sonic86, $3\equiv 1$.

[maxal]

Эту вариацию головоломки Lights Out мы уже обсуждали - см. post48972.html#p48972

[DeBill]

Sonic86 в сообщении #1233104 писал(а):

Я сначала в игре "Следствие ведут колобки" тоже не мог очень долго открыть долбаный холодильник.

Ага. А у меня - дочка парилась... И я для нее разработал тот самый алгоритм.
Если нажать все кнопки в кресте, то поменяется ровно один знак - в центре креста.
Потому (для четного $n$) решение есть. Но позиций всего $2^{n^2}$, и способов нажатия - стоко же. Потому решение - единственно. Но, если запустить исходный дурной алгоритм (меняющий каждый минус на плюс с помощью жамкания на всех клетках креста), то после "приведения подобных" (удаления лишних нажатий) и получится "надо жать на те и только те, в чьем кресте - нечетно минусов", ага.
В частности, если все - минусы, то как раз и надо $n^2$ нажатий.
А школьникам я давал (по теме "Инвариант") это для любых таблиц. Там, типа, получается (в нечетно-четном варианте ): четность числа минусов в каждом столбце должна быть одной и той же (и - для нечет-нечет: и в строках, тоже).

[ET]

Древняя задачка
Если кто помнит, в конце 90х была игра "Братья пилоты" или как-то так называлась. Там на одном из уровней предлагалась такая головоломка для $n=4$
Тогда для четных (да и вообще для любого прямоугольника, у которого обе стороны четные) простой алгоритм придумался, типа жмякнуть на любую жмякалку из тех, что число неправильно стоящих на одном кресте с ней нечетно

-- Чт июл 13, 2017 08:37:26 --

Sonic86 в сообщении #1233104 писал(а):

Я сначала в игре "Следствие ведут колобки" тоже не мог очень долго открыть долбаный холодильник.
А потом я выучил линал

Я без линала ее решал. Краткий ход мыслей был такой:
1. Операция очевидно коммутативна и имеет порядок 2. Следовательно, в случае возможности решить, существет решения, жмякающее на каждую жмякалку не более одного раза
2. Подумаем можно ли и если можно, то как перевернуть ровно одну жмякалку. (как выше сказано со жмяканием на каждую не более раза, то есть выделить множество жмякалок, на которые жмякнуть) По сути все жмякалки разбиваются на 3 подмножества таких, что если две из них из одного подмножества, то они равноправны. при этом каждое жмякание изменяет четность неправильных жмякалок, то есть вариантов даже не 8, а 4. Подобрал.
3. Отсюда первый алгоритм понятен - выпишем все такие, у которых число неправильных в одном кресте с ней нечетно. после выписывания жмякаем ан них
4. Потом задался вопросом - а нужно ли их выписывать? И нашел инвариантик. Все. Пришел на след день на работу все сразу решилось.

[mark apollo]

svv в сообщении #1233111 писал(а):

Да, но в той алгебре, про которую говорил Sonic86, $3\equiv 1$.

Ох, да, невнимательность.. Извините.

DeBill в сообщении #1233147 писал(а):

Если нажать все кнопки в кресте, то поменяется ровно один знак - в центре креста.

Центр будет менять знак семь раз, каждая другая кнопка в кресте - четыре раза, а вне креста - два раза (для 4x4).

DeBill в сообщении #1233147 писал(а):

Потому (для четного $n$) решение есть.

Мы можем изменить знак любой кнопки (клетки), не меняя знаков остальных, видимо, поэтому в конечном итоге можем поменять все знаки.

DeBill в сообщении #1233147 писал(а):

Но позиций всего $2^{n^2}$

Это ясно.

DeBill в сообщении #1233147 писал(а):

и способов нажатия - стоко же.

Это - нет.. Не вижу двоечки, тут выбор для каждой кнопки "нажимать" или "не нажимать"? И при этом предполагается, что каждая будет нажата только один раз?
Видимо, поэтому

ET в сообщении #1233179 писал(а):

Операция очевидно коммутативна и имеет порядок 2. Следовательно, в случае возможности решить, существет решения, жмякающее на каждую жмякалку не более одного раза

DeBill в сообщении #1233147 писал(а):

после "приведения подобных" (удаления лишних нажатий) и получится "надо жать на те и только те, в чем кресте - нечетно минусов", ага.

Пока тоже не вижу, как все приходит к тому, что жать надо именно эти

[mark apollo]

Так, и вообще, правильно ли я понимаю, что вначале хотели так - берем крест, жмем на все кнопки в нем, потом берем следующий и т.д., это получается каждую кнопку жмем много раз в итоге (а именно, для 4x4 - 7 раз, т.к. каждая кнопка входит в 7 крестов).
А потом приходим к тому, что "нужно жать только на те кнопки, у которых в кресте нечетное число минусов" - это имеется в виду в начальной расстановке было нечетное число (в случае всех минусов это так для всех кнопок), или вот мы на каждом шаге смотрим на возникшую позицию, и выбираем в ней такой крест (любой)? Предполагаю последнее, конечно, просто оно не гарантирует, что каждая кнопка будет нажата один раз.

[ET]

mark apollo в сообщении #1233271 писал(а):

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

ET в сообщении #1233179 писал(а):

3. Отсюда первый алгоритм понятен - выпишем все такие, у которых число неправильных в одном кресте с ней нечетно. после выписывания жмякаем ан них
4. Потом задался вопросом - а нужно ли их выписывать? И нашел инвариантик. Все. .

Перевожу со своего на русский: каждое жмякание меняет четность неправильных в кресте только у той жмякалки, на которую жмякаешь. И не меняет четность числа неправильных жмякалок для всех остальных крестов

[DeBill]

mark apollo в сообщении #1233247 писал(а):

Не вижу двоечки, тут выбор для каждой кнопки "нажимать" или "не нажимать"? И при этом предполагается, что каждая будет нажата только один раз?

Ну да. Не боле одного (т.е., нажата-ненажата)

mark apollo в сообщении #1233247 писал(а):

Пока тоже не вижу, как все приходит к тому, что жать надо именно эти

Дык, получилось: в каждом кресте с центром в "минусе", нажали все. Т.е., каждую конкретную кнопку нажали стоко раз, скоко минусов в ее кресте. Т.е., нажимать ее следует лишь тогда, когда в ее кресте минусов - нечетно.

-- 13.07.2017, 21:42 --

ET в сообщении #1233179 писал(а):

а нужно ли их выписывать?

И - да, выписывать их не надо, надо тупо жмякать...