Высшая проба 2026, 7 класс, задача 6
( балла) Некоторые клетки квадрата покрасили в красный цвет, при этом в каждой строке и в каждом столбце покрашено ровно клеток. Известно, что никакие две красные клетки не касаются друг друга сторонами или углами. При каком наименьшем такое могло произойти?
Ответ. При .
Решение. Оценка. Отметим все узлы квадрата (узлы - вершины квадратиков ). Заметим, что если никакие две красные клетки не касаются друг друга сторонами и углами, все уголки красных клеточек являются различными узлами. Посмотрим на первую и вторую строки квадрата. Заметим, что на отрезке, отделяющем первую строку от второй, всего узел. С другой стороны, узлов на этом отрезке будут нижними углами красных квадратиков верхней строки, а - верхними углами квадратиков второй строки. Значит, .
Предположим, что . Тогда для каждого на отрезке, отделяющем строку от строки , все узлы будут углами красных квадратиков. В частности, самый левый узел каждого из этих отрезков будет углом красного квадрата. Но тогда как минимум узлов левой стороны квадрата будут углами красных клеток, а это возможно только если в первом столбце будет хотя бы красных клеток. Значит, .
Пример. Покажем, как покрасить клетки квадрата так, чтобы условие выполнялось.
Разделим квадрат на больших квадрата . Каждый из больших квадратов разрежем на малых квадратов размера . Теперь покрасим в красный цвет некоторые клетки больших квадратов следующим образом:
) В левом верхнем большом квадрате закрасим правую верхнюю клетку каждого малого квадрата.
) В правом верхнем большом квадрате закрасим правую нижнюю клетку каждого малого квадрата.
) В левом нижнем большом квадрате закрасим левую верхнюю клетку каждого малого квадрата.
) В правом нижнем большом квадрате закрасим левую нижнюю клетку каждого малого квадрата.
Ниже - пример для поля и красных клеток в каждой строке и каждом столбце.
Легко видеть, что для данной раскраски все условия выполняются, а значит, искомое равно $4
Приведён верный пример и полностью доказана верная оценка (критерий примера нане суммируется с критерием оценки без примера).
Приведён верный пример и оценка на⩾ 398, случайне разобран или разобран ошибочно.
Полностью доказана оценка на⩾ 400, пример на 400 отсутствует или ошибочен.
Приведён верный пример на, в доказательстве оценки нет продвижений.
Присутствует только доказательство оценки на⩾ 399, случайне разобран или разобран ошибочно, пример отсутствует.
Только пример на.