Задача о сейфе

[Профессор Снэйп]

Решил сформулировать по мотивам темы.

Дана матрица $n \times n$, составленная из нулей и единиц. Элементарное действие заключается в следующем: выбираются $i,j \in \{ 1, \ldots, n \}$ и все элементы матрицы, находящиеся в $i$-ой строке либо в $j$-ом столбце, меняются на "противоположные" (т. е. $0$ на $1$, $1$ на $0$). Решением называется последовательность элементарных действий, приводящая исходную матрицу к нулевой.

1) Выяснить, при каких $n$ решение существует для любой исходной матрицы размера $n \times n$.

2) Пусть дано $n$ и для некоторой матрицы размера $n \times n$ решение существует. Назовём его минимальным, если оно требует наименьшего количества элементарных действий. Оценить количество действий в минимальном решении (оценка должна зависить только от $n$), привести пример, показывающий точность достигнутой оценки.

3) Найти критерий существования решения для данной матрицы, описать все возможные решения.

-- Пн сен 20, 2010 22:45:05 --

Null в сообщении #354434 писал(а):

1)для четных

Как насчёт матрицы $1 \times 1$?

Null в сообщении #354434 писал(а):

2)1?

С чего Вы взяли? Рассмотрите матрицу $2 \times 2$, в которой одна единица и остальные нули. Каково минимальное число элементарных действий для неё?

[Null]

1) для четных n(применение к строке и столбцу меняет клетку на их пересечении)
для нечетных: раскрасим доску в шахматном порядке и пусть угол белый, тогда операции не меняют четность количества единиц в черных клетках
ну еще n=1 черных клеток нет

вы условие поменяли.

[Профессор Снэйп]

Null в сообщении #354440 писал(а):

вы условие поменяли.

Не поменял, а уточнил

С первым пунктом согласен.

[maxal]

Было уже: topic5862.html
Если какие-то вопросы остались неотвеченными - задайте их там.

P.S. Недавно задача также всплывала на mathforum.ru.
А совсем давно обсуждалась в фидо.