ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 107789
Темы:    [ Индукция (прочее) ]
[ Линейная и полилинейная алгебра ]
Сложность: 5-
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

На табло горят несколько лампочек. Имеется несколько кнопок. Нажатие на кнопку меняет состояние лампочек, с которыми она соединена. Известно, что для любого набора лампочек найдется кнопка, соединенная с нечетным числом лампочек из этого набора. Докажите, что, нажимая на кнопки, можно погасить все лампочки.

Решение

  Первый способ. Заметим, что результат нажатия нескольких кнопок не зависит от порядка их нажатия. Проведем индукцию по числу лампочек на табло. При n = 1 утверждение верно (так как найдется кнопка, соединенная с нечетным число лампочек, т. е. в точности с этой лампочкой).

Пусть утверждение доказано для n - 1 лампочек. Докажем утверждение для n лампочек. Рассмотрим i-ю лампочку. По предположению индукции, мы можем погасить остальные n - 1 лампочек. Обозначим необходимый для этого набор кнопок через Si. Если погасла и i-я, то индуктивный переход доказан. Значит, можно считать, что при любом i нажатие на кнопки набора Si приводит к следующей ситуации: горит только i-я лампочка.

Что произойдет, если при некотором состоянии табло нажать сначала кнопки из набора Si, а потом кнопки из набора Sj? При этом изменится состояние ровно двух лампочек: лампочек с номерами i и j (подумайте, почему). Итак, мы научились менять состояние у любой пары лампочек.

По условию найдется кнопка T, соединенная с нечетным числом лампочек. Погасим все лампочки, кроме одной, соединенной с кнопкой T. Затем нажмем T. Тогда будет гореть четное число лампочек. Погасим их парами.

Второй способ. [с использованием линейной алгебры] Занумеруем лампочки числами от 1 до n. Поставим в соответствие состоянию табло строчку

x = (x1,..., xn),

где xi = 1, если i-я лампочка горит, и xi = 0 — если не горит. Такие наборы — это векторы n-мерного векторного пространства над полем из двух элементов.

Каждой кнопке мы тоже поставим в соответствие вектор a = (a1,..., an), где ai = 1, если i-я лампочка соединена с кнопкой, и ai = 0, если не соединена. Ясно, что нажатие на кнопку переводит табло из состояния x в состояние a + x. Таким образом, наша задача состоит в том, чтобы доказать, что векторы, соответствующие кнопкам, порождают все векторное пространство.

Набору лампочек мы поставим в соответствие линейный функционал:

(x1,..., xn) $\displaystyle \mapsto$ $\displaystyle \sum$xi,

где сумма берется по всем i таким, что i-я лампочка входит в набор.

Все линейные функционалы получаются таким образом. Функционал обращается в нуль на векторе, соответствующем кнопке, тогда и только тогда, когда эта кнопка соединена с четным числом лампочек из этого набора. Значит, условие задачи переводится на язык линейной алгебры следующим образом: ни один функционал не обращается в нуль на всех кнопках. Но это равносильно тому, что система векторов, соответствующих кнопкам, полна! Такую равносильность часто называют альтернативой Фредгольма.

Комментарий. Назовем инвариантом такой набор лампочек, что любая кнопка меняет состояние только четного числа лампочек из этого набора. В условии задачи сказано, что таких инвариантов нет. Рассмотрим более общую ситуацию: пусть инварианты есть. Тогда, если множество первоначально горевших лампочек пересекается с некоторым инвариантом по нечетному числу лампочек, то все лампочки, очевидно, погасить не удастся.

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

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 58
Год 1995
вариант
Класс 10
задача
Номер 6
web-сайт
задача

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .