Закраска

[Leeb]

Можно ли закрасить некоторые клетки квадрата $100\times 100$ таким образом, чтобы в любом квадрате $7\times7$ было ровно 25 закрашенный клеток, а в любом прямоугольнике $6\times8$ было ровно 24 закрашенные клетки?

[Gagarin1968]

Leeb
А прямоугольник $ 6\times 8$ вертикальный или горизонтальный? Или можно рассматривать и тот, и другой?

[Leeb]

Gagarin1968
Да, оба, и вертикальный, и горизонтальный.

[svv]

(Решение)

Возьмём квадрат $14\times 14$. Его можно разбить на $4$ квадрата $7\times 7$, значит, в нём $100$ закрашенных клеток. Его также можно разбить на $4$ прямоугольника $8\times 6$ (в совокупности имеют $96$ закрашенных клеток) и центральный «глазок» $2\times 2$, как на картинке. Значит, все клетки «глазка» закрашены.

Двигая эту конструкцию и всё время закрашивая глазок, легко получим полностью закрашенный квадрат $7\times 7$, противоречащий условию.

[Leeb]

svv в сообщении #1624131 писал(а):

(Решение)

Возьмём квадрат $14\times 14$. Его можно разбить на $4$ квадрата $7\times 7$, значит, в нём $100$ закрашенных клеток. Его также можно разбить на $4$ прямоугольника $8\times 6$ (в совокупности имеют $96$ закрашенных клеток) и центральный «глазок» $2\times 2$, как на картинке. Значит, все клетки «глазка» закрашены.

Двигая эту конструкцию и всё время закрашивая глазок, легко получим полностью закрашенный квадрат $7\times 7$, противоречащий условию.

Должен признать, задача вышла так себе, а у вас очень хорошее решение. У меня хуже и вообще на строгое не тянет:
Предположим, закраска существует. Рассмотрим квадрат $49\times 49$ и в нем подквадрат $48\times48$. В большем должно быть ровно $1225$ заражённых клеток, в меньшем - $1152$. Значит, в уголке 73 закрашенные клетки. Поскольку это верно для любого квадрата $49\times49$, то в любой полоске $1\times 49$ должно быть не менее 36 закрашенных клеток. Но тогда квадрат $98\times 98$ с одной стороны, имеет $4900$ клеток, а с другой - не менее $98\times98/49 \times 36 = 7056$ клеток, откуда противоречие.

[svv]

Leeb, задача приятная, спасибо.

[TOTAL]

Можно ли закрасить некоторые клетки прямоугольника $42\times 56$ таким образом, чтобы в любом квадрате $7\times7$ было ровно 25 закрашенный клеток, а в любом прямоугольнике $6\times8$ было ровно 24 закрашенные клетки?

[Dendr]

Но разве svv не доказал только что, что в таком прямоугольнике неизбежно должна быть полностью закрашенная область размера 30 на 44?

[TOTAL]

Dendr в сообщении #1624552 писал(а):

Но разве svv не доказал только что, что в таком прямоугольнике неизбежно должна быть полностью закрашенная область размера 30 на 44?

То было моё решение, а не вопрос.
(Число закрашенных в $42 \times 56$ можно найти разными способами.)

[Dendr]

TOTAL в сообщении #1624578 писал(а):

То было моё решение, а не вопрос.

О. Вот теперь дошло. Так еще изящнее.

И это натолкнуло меня на другой вопрос - а существуют ли вообще доски, которые можно раскрасить согласно условию? Разумеется, должна присутствовать хотя бы одна квадратная область и одна прямоугольная. И если они есть, то сколько?

Ответ на первый вопрос - конечно, да. Наименьшую сетку, $7\times8$, можно раскрасить, например, так: все краевые клетки, и еще шесть (неважно какие) в середине доски.