Решил сформулировать по мотивам
темы.
Дана матрица
![$n \times n$ $n \times n$](https://dxdy-04.korotkov.co.uk/f/3/a/d/3add1221abfa79cb14021bc2dacd572582.png)
, составленная из нулей и единиц.
Элементарное действие заключается в следующем: выбираются
![$i,j \in \{ 1, \ldots, n \}$ $i,j \in \{ 1, \ldots, n \}$](https://dxdy-02.korotkov.co.uk/f/5/a/c/5aca7bd168a5ff5cfb9329b0b05363da82.png)
и все элементы матрицы, находящиеся в
![$i$ $i$](https://dxdy-04.korotkov.co.uk/f/7/7/a/77a3b857d53fb44e33b53e4c8b68351a82.png)
-ой строке либо в
![$j$ $j$](https://dxdy-04.korotkov.co.uk/f/3/6/b/36b5afebdba34564d884d347484ac0c782.png)
-ом столбце, меняются на "противоположные" (т. е.
![$0$ $0$](https://dxdy-03.korotkov.co.uk/f/2/9/6/29632a9bf827ce0200454dd32fc3be8282.png)
на
![$1$ $1$](https://dxdy-01.korotkov.co.uk/f/0/3/4/034d0a6be0424bffe9a6e7ac9236c0f582.png)
,
![$1$ $1$](https://dxdy-01.korotkov.co.uk/f/0/3/4/034d0a6be0424bffe9a6e7ac9236c0f582.png)
на
![$0$ $0$](https://dxdy-03.korotkov.co.uk/f/2/9/6/29632a9bf827ce0200454dd32fc3be8282.png)
).
Решением называется последовательность элементарных действий, приводящая исходную матрицу к нулевой.
1) Выяснить, при каких
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
решение существует для любой исходной матрицы размера
![$n \times n$ $n \times n$](https://dxdy-04.korotkov.co.uk/f/3/a/d/3add1221abfa79cb14021bc2dacd572582.png)
.
2) Пусть дано
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
и для некоторой матрицы размера
![$n \times n$ $n \times n$](https://dxdy-04.korotkov.co.uk/f/3/a/d/3add1221abfa79cb14021bc2dacd572582.png)
решение существует. Назовём его
минимальным, если оно требует наименьшего количества элементарных действий. Оценить количество действий в минимальном решении (оценка должна зависить только от
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
), привести пример, показывающий точность достигнутой оценки.
3) Найти критерий существования решения для данной матрицы, описать все возможные решения.
-- Пн сен 20, 2010 22:45:05 --1)для четных
Как насчёт матрицы
![$1 \times 1$ $1 \times 1$](https://dxdy-02.korotkov.co.uk/f/d/1/2/d12ef2fd91d2a991710509cae722913482.png)
?
2)1?
С чего Вы взяли? Рассмотрите матрицу
![$2 \times 2$ $2 \times 2$](https://dxdy-03.korotkov.co.uk/f/a/b/2/ab2d2968f149e290d718f3d1135e40ac82.png)
, в которой одна единица и остальные нули. Каково минимальное число элементарных действий для неё?