|
|
 |
Условие
На табло горят несколько лампочек. Имеется несколько кнопок. Нажатие на кнопку меняет состояние лампочек, с которыми она соединена. Известно, что для любого набора лампочек найдется кнопка, соединенная с нечетным числом лампочек из этого набора. Докажите, что, нажимая на кнопки, можно погасить все лампочки.Решение
Первый способ. Заметим, что результат нажатия нескольких кнопок не зависит от порядка их нажатия. Проведем индукцию по числу лампочек на табло. При n = 1 утверждение верно (так как найдется кнопка, соединенная с нечетным число лампочек, т. е. в точности с этой лампочкой).Пусть утверждение доказано для n - 1 лампочек. Докажем утверждение для n лампочек. Рассмотрим i-ю лампочку. По предположению индукции, мы можем погасить остальные n - 1 лампочек. Обозначим необходимый для этого набор кнопок через Si. Если погасла и i-я, то индуктивный переход доказан. Значит, можно считать, что при любом i нажатие на кнопки набора Si приводит к следующей ситуации: горит только i-я лампочка.
Что произойдет, если при некотором состоянии табло нажать сначала кнопки из набора Si, а потом кнопки из набора Sj? При этом изменится состояние ровно двух лампочек: лампочек с номерами i и j (подумайте, почему). Итак, мы научились менять состояние у любой пары лампочек.
По условию найдется кнопка T, соединенная с нечетным числом лампочек. Погасим все лампочки, кроме одной, соединенной с кнопкой T. Затем нажмем T. Тогда будет гореть четное число лампочек. Погасим их парами.
Второй способ. [с использованием линейной алгебры] Занумеруем лампочки числами от 1 до n. Поставим в соответствие состоянию табло строчку
Каждой кнопке мы тоже поставим в соответствие вектор a = (a1,..., an), где ai = 1, если i-я лампочка соединена с кнопкой, и ai = 0, если не соединена. Ясно, что нажатие на кнопку переводит табло из состояния x в состояние a + x. Таким образом, наша задача состоит в том, чтобы доказать, что векторы, соответствующие кнопкам, порождают все векторное пространство.
Набору лампочек мы поставим в соответствие линейный функционал:
Все линейные функционалы получаются таким образом. Функционал обращается в нуль на векторе, соответствующем кнопке, тогда и только тогда, когда эта кнопка соединена с четным числом лампочек из этого набора. Значит, условие задачи переводится на язык линейной алгебры следующим образом: ни один функционал не обращается в нуль на всех кнопках. Но это равносильно тому, что система векторов, соответствующих кнопкам, полна! Такую равносильность часто называют альтернативой Фредгольма.
Комментарий. Назовем инвариантом такой набор лампочек, что любая кнопка меняет состояние только четного числа лампочек из этого набора. В условии задачи сказано, что таких инвариантов нет. Рассмотрим более общую ситуацию: пусть инварианты есть. Тогда, если множество первоначально горевших лампочек пересекается с некоторым инвариантом по нечетному числу лампочек, то все лампочки, очевидно, погасить не удастся.
Оказывается, что если множество первоначально горевших лампочек пересекается с любым инвариантом по четному числу лампочек, то все лампочки можно погасить. Данная задача является частным случаем этого утверждения. Это утверждение тоже можно доказать по индукции или при помощи линейной алгебры (попробуйте сделать это сами).
