2014 dxdy logo

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

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




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


18/12/07
8774
Новосибирск
Решил сформулировать по мотивам темы.

Дана матрица $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 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Задача о сейфе
Сообщение20.09.2010, 18:57 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Null в сообщении #354440 писал(а):
вы условие поменяли.

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

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

 Профиль  
                  
 
 Re: Задача о сейфе
Сообщение20.09.2010, 19:00 
Модератор
Аватара пользователя


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


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Bing [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group