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
1677
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 ] 

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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