Разделы 
Дополнительно
Задача по математике - 3209
2019-05-27 
На табло горят несколько лампочек. Имеется несколько кнопок. Нажатие на кнопку меняет состояние лампочек, с которыми она соединена. Известно, что для любого набора лампочек найдется кнопка, соединенная с нечетным числом лампочек из этого набора. Докажите, что, нажимая на кнопки, можно погасить все лампочки.
Решение:
Первый способ. Заметим, что результат нажатия нескольких кнопок не зависит от порядка их нажатия. Проведем индукцию по числу лампочек на табло. При $n=1$ утверждение верно (так как найдется кнопка, соединенная с нечетным число лампочек, т. е. в точности с этой лампочкой).
Пусть утверждение доказано для $n-1$ лампочек. Докажем утверждение для $n$ лампочек. Рассмотрим $i$-ю лампочку. По предположению индукции, мы можем погасить остальные $n-1$ лампочек. Обозначим необходимый для этого набор кнопок через $S_i$. Если погасла и $i$-я, то индуктивный переход доказан. Значит, можно считать, что при любом $i$ нажатие на кнопки набора $S_i$ приводит к следующей ситуации: горит только $i$-я лампочка.
Что произойдет, если при некотором состоянии табло нажать сначала кнопки из набора $S_i$, а потом кнопки из набора $S_j$? При этом изменится состояние ровно двух лампочек: лампочек с номерами $i$ и $j$ (подумайте, почему). Итак, мы научились менять состояние у любой пары лампочек.
По условию найдется кнопка $T$, соединенная с нечетным числом лампочек. Погасим все лампочки, кроме одной, соединенной с кнопкой $T$. Затем нажмем $T$. Тогда будет гореть четное число лампочек. Погасим их парами.
Второй способ (с использованием линейной алгебры). Занумеруем лампочки числами от 1 до $n$. Поставим в соответствие состоянию табло строчку
$x = (x_1, \cdots, x_n)$,
где $x_i = 1$, если $i$-я лампочка горит, и $x_i = 0$ - если не горит. Такие наборы - это векторы $n$-мерного векторного пространства над полем из двух элементов.
Каждой кнопке мы тоже поставим в соответствие вектор $a = (a_1, \cdots, a_n)$, где $a_i=1$, если $i$-я лампочка соединена с кнопкой, и $a_i=0$, если не соединена. Ясно, что нажатие на кнопку переводит табло из состояния $x$ в состояние $a+x$. Таким образом, наша задача состоит в том, чтобы доказать, что векторы, соответствующие кнопкам, порождают все векторное пространство.
Набору лампочек мы поставим в соответствие линейный функционал:
$(x_1, \cdots, x_n) \rightarrow \sum x_i$,
где сумма берется по всем $i$ таким, что $i$-я лампочка входит в набор.
Все линейные функционалы получаются таким образом. Функционал обращается в нуль на векторе, соответствующем кнопке, тогда и только тогда, когда эта кнопка соединена с четным числом лампочек из этого набора. Значит, условие задачи переводится на язык линейной алгебры следующим образом: ни один функционал не обращается в нуль на всех кнопках. Но это равносильно тому, что система векторов, соответствующих кнопкам, полна! Такую равносильность часто называют альтернативой Фредгольма.
На табло горят несколько лампочек. Имеется несколько кнопок. Нажатие на кнопку меняет состояние лампочек, с которыми она соединена. Известно, что для любого набора лампочек найдется кнопка, соединенная с нечетным числом лампочек из этого набора. Докажите, что, нажимая на кнопки, можно погасить все лампочки.
Решение:
Первый способ. Заметим, что результат нажатия нескольких кнопок не зависит от порядка их нажатия. Проведем индукцию по числу лампочек на табло. При $n=1$ утверждение верно (так как найдется кнопка, соединенная с нечетным число лампочек, т. е. в точности с этой лампочкой).
Пусть утверждение доказано для $n-1$ лампочек. Докажем утверждение для $n$ лампочек. Рассмотрим $i$-ю лампочку. По предположению индукции, мы можем погасить остальные $n-1$ лампочек. Обозначим необходимый для этого набор кнопок через $S_i$. Если погасла и $i$-я, то индуктивный переход доказан. Значит, можно считать, что при любом $i$ нажатие на кнопки набора $S_i$ приводит к следующей ситуации: горит только $i$-я лампочка.
Что произойдет, если при некотором состоянии табло нажать сначала кнопки из набора $S_i$, а потом кнопки из набора $S_j$? При этом изменится состояние ровно двух лампочек: лампочек с номерами $i$ и $j$ (подумайте, почему). Итак, мы научились менять состояние у любой пары лампочек.
По условию найдется кнопка $T$, соединенная с нечетным числом лампочек. Погасим все лампочки, кроме одной, соединенной с кнопкой $T$. Затем нажмем $T$. Тогда будет гореть четное число лампочек. Погасим их парами.
Второй способ (с использованием линейной алгебры). Занумеруем лампочки числами от 1 до $n$. Поставим в соответствие состоянию табло строчку
$x = (x_1, \cdots, x_n)$,
где $x_i = 1$, если $i$-я лампочка горит, и $x_i = 0$ - если не горит. Такие наборы - это векторы $n$-мерного векторного пространства над полем из двух элементов.
Каждой кнопке мы тоже поставим в соответствие вектор $a = (a_1, \cdots, a_n)$, где $a_i=1$, если $i$-я лампочка соединена с кнопкой, и $a_i=0$, если не соединена. Ясно, что нажатие на кнопку переводит табло из состояния $x$ в состояние $a+x$. Таким образом, наша задача состоит в том, чтобы доказать, что векторы, соответствующие кнопкам, порождают все векторное пространство.
Набору лампочек мы поставим в соответствие линейный функционал:
$(x_1, \cdots, x_n) \rightarrow \sum x_i$,
где сумма берется по всем $i$ таким, что $i$-я лампочка входит в набор.
Все линейные функционалы получаются таким образом. Функционал обращается в нуль на векторе, соответствующем кнопке, тогда и только тогда, когда эта кнопка соединена с четным числом лампочек из этого набора. Значит, условие задачи переводится на язык линейной алгебры следующим образом: ни один функционал не обращается в нуль на всех кнопках. Но это равносильно тому, что система векторов, соответствующих кнопкам, полна! Такую равносильность часто называют альтернативой Фредгольма.
