Задача 66587

Темы:    [ Построения (прочее) ] [ Теория алгоритмов (прочее) ]

Сложность: 3+ Классы: 9,10,11

Условие

Автор: Шаповалов А.В.

В узлах сетки клетчатого прямоугольника $4 \times 5$ расположены $30$ лампочек, изначально все они погашены. За ход разрешается провести любую прямую, не задевающую лампочек (размерами лампочек следует пренебречь, считая их точками), такую, что с какой-то одной стороны от нее ни одна лампочка не горит, и зажечь все лампочки по эту сторону от прямой. Каждым ходом нужно зажигать хотя бы одну лампочку. Можно ли зажечь все лампочки ровно за четыре хода?

Решение

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

Теперь проведем первую прямую параллельно вспомогательной, чуть ниже, чтобы эти две лампочки оказались над ней, а все остальные лампочки остались с той же стороны, что и до этого; зажжем все лампочки ниже этой прямой, как на первом рисунке (зажигаемые лампочки обозначены черными точками). Вторую прямую аналогично проведем параллельно вспомогательной, но чуть выше, чтобы две угловые лампочки оказались под ней; зажжем все лампочки выше этой прямой, как на втором рисунке.

Незажженными остались две угловые лампочки. Их можно зажечь за два хода, просто отсекая прямой от остальных.

Ответ

Да.

Замечания

См. задачу 66903

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	84
Год	2021
класс
Класс	9
задача
Номер	3