Единички в матрице

[Ktina]

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

[Ktina]

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

[hippie]

Ответ: $\bold{8n.}$

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

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

[Ktina]

hippie в сообщении #540215 писал(а):

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

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

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

[hippie]

(Оффтоп)

Ktina в сообщении #540220 писал(а):

Как Вы умудряетесь такие короткие решения формулировать?

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

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