Выбрана 1 задача 
Убрать все задачи
Путешественник прибыл на остров, где живут 50 аборигенов, каждый из которых либо рыцарь, либо лжец. Все аборигены встали в круг, и каждый назвал сначала возраст своего соседа слева, а потом возраст соседа справа. Известно, что каждый рыцарь назвал оба числа верно, а каждый лжец какой-то из возрастов (по своему выбору) увеличил на 1, а другой – уменьшил на 1. Всегда ли путешественник по высказываниям аборигенов сможет определить, кто из них рыцарь, а кто лжец?
Решение
|
|
 |
Условие
В центре каждой клетки клетчатого прямоугольника $M$ расположена точечная лампочка, изначально все они погашены. За ход разрешается провести любую прямую, не задевающую лампочек, и зажечь все лампочки по какую-то одну сторону от этой прямой, если все они погашены. Каждым ходом должна зажигаться хотя бы одна лампочка. Требуется зажечь все лампочки, сделав как можно больше ходов. Какое максимальное число ходов удастся сделать, если
а) $M$ – квадрат $21\times21$;
б) $M$ – прямоугольник $20\times21$?
Решение
Вместо исходного прямоугольника $M$ будем рассматривать прямоугольник $N$ с вершинами в угловых лампочках.
Оценки. Заметим, что каждым ходом зажигается хотя бы одна из четырёх угловых лампочек. Следовательно, ходов не больше 4. В п. а) заметим ещё, что мы должны на каком-то ходу зажечь центральную лампочку. Вместе с ней по одну сторону от проведённой прямой окажется хотя бы две угловых лампочки (поскольку прямая, параллельная проведённой и проходящая через центр, делит квадрат $N$ на две симметричные относительно центра части).
Примеры. а) Сначала зажигаем всё, кроме нижнего ряда лампочек, затем зажигаем все из оставшихся лампочек, кроме угловой, и наконец зажигаем угловую лампочку. (На рисунке изображены два нижних слоя лампочек, стрелки указывают по какую сторону от прямой зажигаются лампочки.)
б) Прямоугольник $N$ имеет размеры $19\times20$. На его диагонали нет других лампочек, поскольку 19 и 20 взаимно просты. Проведём первую прямую параллельно диагонали, чуть ниже, чтобы эти две лампочки оказались над ней, а все остальные лампочки остались с той же стороны, что и до этого; зажжём все лампочки ниже этой прямой. Аналогично проведём вторую прямую параллельно диагонали, но чуть выше, и зажжём все лампочки выше этой прямой, как на рисунке. (Для примера мы взяли $N$ размером $4\times5$ – поменьше, но тоже с взаимно простыми сторонами.) Оставшиеся две угловые лампочки можно зажёчь за два хода, отсекая прямой от остальных.
