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

Мы хотим отметить на доске 8×8 клетки так, чтобы в каждом квадрате 4×4 (а таких перекрывающихся квадратов всего 25) оказалось не более одной отмеченной. Заметим, что если какой–либо квадрат 4×4 не имеет ни одной отмеченной клетки, то можно добавить любую клетку из него – условие не нарушится. Отсюда следует, что окончательное (максимальное по данным правилам) множество отмеченных клеток должно иметь следующий «перекрывающий» эффект: для любого неотмеченного узла существует хотя бы один квадрат 4×4, в котором уже стоит отметка. Другими словами, окончательное множество должно «пересекать» (бы...