Решил сформулировать по мотивам
темы.
Дана матрица
, составленная из нулей и единиц.
Элементарное действие заключается в следующем: выбираются
и все элементы матрицы, находящиеся в
-ой строке либо в
-ом столбце, меняются на "противоположные" (т. е.
на
,
на
).
Решением называется последовательность элементарных действий, приводящая исходную матрицу к нулевой.
1) Выяснить, при каких
решение существует для любой исходной матрицы размера
.
2) Пусть дано
и для некоторой матрицы размера
решение существует. Назовём его
минимальным, если оно требует наименьшего количества элементарных действий. Оценить количество действий в минимальном решении (оценка должна зависить только от
), привести пример, показывающий точность достигнутой оценки.
3) Найти критерий существования решения для данной матрицы, описать все возможные решения.
-- Пн сен 20, 2010 22:45:05 --1)для четных
Как насчёт матрицы
?
2)1?
С чего Вы взяли? Рассмотрите матрицу
, в которой одна единица и остальные нули. Каково минимальное число элементарных действий для неё?