Требуется изготовить табло из 2005 лампочек, имеющее систему выключателей. Любой выключатель должен быть присоединен к паре лампочек, и при нажатии на него должно одновременно меняться состояние двух этих лампочек (горящая выключается, негорящая — включается). Какого наименьшего числа выключателей хватит, чтобы из любого начального состояния можно было с их помощью добиться хотя бы одного из двух результатов: чтобы все лампочки горели, либо все лампочки были потушены?
Подсказка
Заметим, что четность числа горящих лампочек в любой момент такая же, как в начальном состоянии. Устроим систему из 2004 выключателей следующим образом: одна лампочка А является выделенной, и каждый выключатель подключен к ней и еще какой-то из других лампочек (разные выключатели — к разным лампочкам).
Решение
Заметим, что четность числа горящих лампочек в любой момент такая же, как в начальном состоянии. Устроим систему из 2004 выключателей следующим образом: одна лампочка А является выделенной, и каждый выключатель подключен к ней и еще какой-то из других лампочек (разные выключатели — к разным лампочкам). Если в начальном состоянии горит четное число лампочек, то погасим их, последовательно выключая их и переключая лампочку А (в итоге все лампочки, включая А, будут погашены). Если же в начальном состоянии горит нечетное число лампочек, то включим все остальные (их четное число, поэтому в итоге лампочка А тоже будет включена). Докажем, что меньшего числа выключателей не хватит. Действительно, при меньшем количестве выключателей граф лампочек несвязен, поэтому есть или хотя бы одна четная компонента связности, или хотя бы три нечетных компоненты. В четной компоненте достаточно рассмотреть такое начальное состояние, в котором горит только одна лампочка (и с ним уже ничего нельзя сделать), а на двух нечетных компонентах достаточно зажечь 0 и 1 лампочек соответственно — тогда одну из компонент можно будет только погасить, а другую — только зажечь.