Электрощиток с автоматическими выключателями в вашем новом доме расположен очень неудобно: в подвале. Вы с досадой обнаруживаете, что ни один из 100 автоматических выключателей не подписан. Вас ждет пугающая перспектива определения, какой выключатель за какую лампочку отвечает. (Предположим, что каждый выключатель связан только с одной лампочкой).
Для начала вы включаете все 100 лампочек в доме и спускаетесь в подвал, чтобы приступить к изнурительному процессу разметки. При каждом заходе в подвал вы можете переключать любое число выключателей. После каждого спуска в подвал и переключения выключателей вы поднимаетесь наверх посмотреть, какие лампочки включились, а какие — выключились.
Какое минимальное число заходов в подвал придется совершить, чтобы определить, за какую лампочку отвечает каждый выключатель?
Подсказка: щупать лампочки, оценивая их теплоту, не надо. Также не надо трогать выключатели в комнатах, переключаем только в подвале.
Посмотреть решениеРешение тут потрясающее. Главное — выбрать верную стратегию.
Простейшая стратегия — просто выключать поочередно все выключатели. Но для этого потребуется 99 спусков в подвал (100-й выключатель будет определен путем исключения). К счастью, можно поступить куда лучше.
Вы не поверите, что чтобы разметить все 100 выключателей, понадобится лишь 7 заходов в подвал!
Стратегия следующая.
Для удобства отслеживания происходящего лепим по куску липкой бумажной ленты на каждый выключатель и на каждую лампочку.
При первом спуске в подвал переводим 50 выключателей в положение «Выкл.». Ставим пометку «0» на прилепленных к ним ярлыках. На остальных ставим пометку «1». Поднявшись наверх, помечаем нулями выключенные лампочки, а единицами — включенные.
При втором спуске в подвал оставляем выключенными выключатели, помеченные нулями. Выключаем половину выключателей, помеченных единицами, а на их ярлыках дописываем нули. Остальные выключатели помечаем второй единицей. Поднимаемся наверх и снова помечаем все выключенные лампочки нулями, а включенные — единицами.
К концу этого этапа все наши выключатели и лампочки помечены комбинациями «00», «11», «10» и «01». Фактически, мы разделили все выключатели с лампочками на четыре группы.
На третьем спуске в подвал мы переключаем половину выключателей в каждой группе (фактически по 13 штук, потому что 25 — нечетное число) в положение «Выкл.» и помечаем каждый из них дополнительным нулем. 12 включенных выключателей в каждой группе помечаем единицами. Проходимся по дому и снова помечаем все выключенные лампочки нулями, а включенные — единицами.
Теперь мы создали 8 разных групп из 12 и 13 лампочек и выключателей: «000», «001», «110», «111», «100», «101», «010» и «011». Лампочки также помечены трехциферными кодами.
После четвертого захода в подвал мы получаем 16 групп из 6-7 выключателей и лампочек в каждой. Пятый заход даст нам 32 группы из 3-4 выключателей и лампочек. После шестого захода в каждой группе останется либо по одному, либо по два выключателя с лампочками.
В группах, где осталось по одному выключателю с лампочкой, мы успешно устанавливаем соответствие между выключателем и лампочкой. Чтобы разметить остальные, понадобится еще один — седьмой — спуск в подвал.
Если вы знакомы с двоичной системой счисления, вы видите, что у нас ровно 128 чисел, каждое из которых — комбинация из 7 нулей и единиц. В конечном итоге каждый выключатель и лампочка получили свой собственный уникальный код в виде двоичного числа.
Если применять эту стратегию и дальше, за восемь походов в подвал вы сможете разметить 256 выключателей, за девять — 512, а за 10 — 1024!
