2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Задача о сейфе
Сообщение20.09.2010, 18:26 
Аватара пользователя
Решил сформулировать по мотивам темы.

Дана матрица $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$, в которой одна единица и остальные нули. Каково минимальное число элементарных действий для неё?

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

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

 
 
 
 Re: Задача о сейфе
Сообщение20.09.2010, 18:57 
Аватара пользователя
Null в сообщении #354440 писал(а):
вы условие поменяли.

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

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

 
 
 
 Re: Задача о сейфе
Сообщение20.09.2010, 19:00 
Аватара пользователя
 i  Было уже: topic5862.html
Если какие-то вопросы остались неотвеченными - задайте их там.


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

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group