Замечательная задача от П. Е. Пушкаря и К. Л. Шейнерман

[Xenia1996]

На ММО-2003 предлагалась следующая задача:

Можно ли покрасить некоторые клетки доски 8×8 так, чтобы в любом квадрате 3×3 было ровно 5 закрашенных клеток, а в каждом прямоугольнике 2×4 (вертикальном или горизонтальном) – ровно 4 закрашенные клетки?

В предлагаемом автором решении доказывается, что нельзя раскрасить требуемым образом даже доску $6\times 6$ (а, следовательно, $8\times 8$ и подавно).

Я пошла дальше и доказала невозможность такой раскраски для доски $5\times 5$ и да возможность для доски $4\times 4$.

Предлагаю уважаемым форумчанам попытаться повторить мой успех.

[Xenia1996]

Ну, если тяжело $5\times 5$, попробуйте хотя бы $4\times 4$, это на порядок легче, всего лишь пример раскраски привести (в отличие от $5\times 5$, где нужно доказать, что такая раскраска невозможна).

[VAL]

Xenia1996 в сообщении #458084 писал(а):

Ну, если тяжело $5\times 5$, попробуйте хотя бы $4\times 4$, это на порядок легче, всего лишь пример раскраски привести (в отличие от $5\times 5$, где нужно доказать, что такая раскраска невозможна).

Ну, $4\times4$ - делать нечего. 4 центральных и 4 угловых.

[Xenia1996]

VAL в сообщении #458091 писал(а):

Ну, $4\times4$ - делать нечего. 4 центральных и 4 угловых.

А у меня обе диагонали, что то же самое

Вот мне интересно, сможет ли кто-нибудь $5\times 5$?

[Lunatik]

Xenia1996 в сообщении #458092 писал(а):

Вот мне интересно, сможет ли кто-нибудь $5\times 5$?

Есть беспереборный вариант? А то фактически получается чуть-чуть улучшенный тупой перебор)... хотя я ещё подумаю...

[Lunatik]

В общем есть доказательство, смысл такой:
1) Доказывается, что закрашенных клеток либо 12, либо 13.
2) И вводя ещё одну фигуру - уголок (в которой содержится 3 закр. клетки) доказываем, что ни то, ни то невозможно... Итого перебрать пять вариантов, два из которых тривиальны, а три требуют несложного рассуждения, которое описывается в пару строчек...
Доказательство приводить наверное не буду, ибо там почти только рисунки, а в Tex'e рисовать не умею

[Xenia1996]

Lunatik в сообщении #458510 писал(а):

В общем есть доказательство, смысл такой:
1) Доказывается, что закрашенных клеток либо 12, либо 13.
2) И вводя ещё одну фигуру - уголок (в которой содержится 3 закр. клетки) доказываем, что ни то, ни то невозможно... Итого перебрать пять вариантов, два из которых тривиальны, а три требуют несложного рассуждения, которое описывается в пару строчек...
Доказательство приводить наверное не буду, ибо там почти только рисунки, а в Tex'e рисовать не умею

Вот я тоже не умею рисовать, а словами было лень. Но мир - не без добрых людей: http://e-science.ru/forum/index.php?showtopic=31928