2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Единички в матрице
Сообщение18.02.2012, 14:54 
Аватара пользователя


01/12/11

8634
Какое наименьшее число единичек может содержать битовая матрица $5n\times 5n$, в которой ни одна строка и ни один столбец не содержат "блок" из $3n$ идущих подряд нулей?
Ответ дать как функцию от $n\in\mathbb N$.

 Профиль  
                  
 
 Re: Единички в матрице
Сообщение18.02.2012, 16:39 
Аватара пользователя


01/12/11

8634
Разумеется, я имела в виду двоичную матрицу, по глупости назвав её "битовой".
Прошу прощения Изображение

 Профиль  
                  
 
 Re: Единички в матрице
Сообщение18.02.2012, 18:24 
Заслуженный участник


18/01/12
933
Ответ: $\bold{8n.}$

В матрице есть $8n$ попарно не пересекающихся фрагментов строк и столбцов длины $3n.$
В то же время, если единице равняются $a_{jk}$ при $j+k\equiv 1 (\mod 3n),$ то количество единиц равно $8n$ и ни одного блока длины $3n,$ состоящего только из нулей, в матрице нет.

Спасибо за интересную задачу!

 Профиль  
                  
 
 Re: Единички в матрице
Сообщение18.02.2012, 18:33 
Аватара пользователя


01/12/11

8634
hippie в сообщении #540215 писал(а):
Спасибо за интересную задачу!

Не за что!
Как говорят англичане, это было мне в удовольствие.

Как Вы умудряетесь такие короткие решения формулировать?
Я пока решала, четыре листа бумаги исписала (и исчетрила), да и потратила почти час (хотя на олимпиаде отводилось 70 минут). Сперва разобрала три частных случая $n\in\{1, 2, 3\}$, затем нашла закономерность.

 Профиль  
                  
 
 Re: Единички в матрице
Сообщение19.02.2012, 05:01 
Заслуженный участник


18/01/12
933

(Оффтоп)

Ktina в сообщении #540220 писал(а):
Как Вы умудряетесь такие короткие решения формулировать?

Один из законов Паркинсона гласит:
"Самую ответственную работу нужно поручить лентяю. Он всегда сделает её самым простым способом, причём так, что потом не придётся переделывать."
А я — тот самый лентяй, о котором говорится в этом законе :-) .

В этой задаче:
Понятно, что если в матрице $5\times 5$ удалось расставить $k$ единиц, то в матрице $5n\times 5n$ можно расставить $kn$ единиц. (А именно, рассматриваем матрицу $5n\times 5n$ как блочную, состоящую из $5\times 5$ блоков размером $n\times n;$ и в каждом блоке расставляем единицы, по одной и той же диагонали.)
Очевидно, что в матрице $5\times 5$ должно быть не меньше 7 единиц. И я минут 10 пытался (в уме) подобрать решение с семью единицами :oops: :oops: :oops: . Наконец, решив, что иногда можно и не быть лентяем :-) , взял ручку и бумажку, и увидел, что квадрат $5\times 5$ режется на 8 прямоугольников $1\times 3.$ (Наверно, я, всё-таки, не настоящий лентяй, иначе заметил бы это и без бумажки :-) .) Отсюда сразу получается нижняя оценка в исходной задаче — $8n.$ Осталось найти расстановку восьми единичек в матрице $5\times 5,$ что совсем не сложно.
Наконец, записывая ответ, пришлось снова "включить лентяя" :-) .

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

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



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

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


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

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