Головоломка 1. На втором этаже дачи есть лампочка. А на первом — три выключателя, но лампочку включает лишь один из них. Гость как угодно манипулирует выключателями, однако подняться для проверки на второй этаж может только один раз. Как определить, какой именно выключатель связан с лампочкой?

Решение. Если гость сообразительный, он легко определит необходимый выключатель. Сначала он включает первый из трёх, ждёт минуту, потом выключает и включает второй, после чего поднимается наверх. Если лампочка горит, понятно, что с ней связан именно второй выключатель. Если лампочка не горит, он дотрагивается до неё. Лампочка тёплая (она нагрелась, пока горела, и не успела остыть) — значит, искомый выключатель — первый, а если холодная, то третий. Вот и всё.

Эту головоломку можно считать полушуточной (в логических задачах редко приходится щупать лампочки). А в следующей тоже участвуют электрические лампочки, но она значительно сложнее.

Головоломка 2. Можно ли в поезде, состоящем из N замкнутых в кольцо вагонов, определить число N, если разрешается только ходить по вагонам и включать и выключать свет; исходно в каждом вагоне свет либо включён, либо выключен.

Определить число N можно разными способами, приведём два решения.

Решение первое. Зайдём в любой вагон — будем считать его первым — и, если там горит свет, выключим его. Теперь перейдём в соседний вагон слева — во второй, включим в нём свет (или оставим включённым) и вернёмся в первый, чтобы удостовериться, что света по-прежнему там нет. Опять идём влево, в третьем вагоне включим свет, снова вернёмся для проверки в первый и т. д. В какой-то момент, вернувшись в первый вагон, обнаружим, что в нём свет горит. Значит, круг замкнулся: последний вагон, в котором мы включили свет, и есть первый, он же — (N+1) по счёту.

Подсчёт показывает, что число переходов из вагона в вагон в этом случае равно 2×(1+2+…+N)=2×N(N+1)/2=N(N+1).

Решение второе. Зайдём в любой вагон, на сей раз для удобства будем считать его нулевым. В первом вагоне слева выключим свет, пройдём через нулевой и в первом вагоне справа включим свет. Снова пойдём через нулевой налево и выключим свет во втором левом вагоне. Затем отправимся направо и включим свет во втором вагоне справа и т. д. Слева от нулевого будут идти одни тёмные вагоны, справа — одни светлые. В какой-то момент, дойдя до последнего вагона слева, где мы выключили свет, обнаружим, что теперь в нём свет горит. Значит, при движении вправо мы там его включили и два полукруга тёмных и светлых вагонов сомкнулись. Определим, сколько сделано переходов.

Пусть N чётно. Влево будет пройдено 1+2+...+...N/2 вагонов, вправо — столько же. Поскольку каждый раз мы возвращаемся в нулевой вагон, надо умножить на 2. Соединение двух полукругов определится ещё через N/2 переходов. Значит, общее число переходов равно 4×(1+2+...+N/2)+N/2=4((1+N/2)N/2)/2+N/2=((2+N)N+N)/2=(N²+3N)/2=N(N+3)/2. При нечётных N вычисления немного отличаются, но формула совпадает с данной.

Первое решение логически проще, а второе алгоритмически вдвое экономнее (за счёт того, что организовано встречное движение по вагонам) — для определения числа N требуется порядка N²/2 переходов вместо N².

№9, 2011