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

Проект МЦНМО
при участии
школы 57
Задача 79383
Темы:    [ Правило произведения ]
[ Разбиения на пары и группы; биекции ]
[ Комбинаторика орбит ]
[ Теорема Лагранжа ]
Сложность: 4
Классы: 9,10
В корзину
Прислать комментарий

Условие

На пульте имеется несколько кнопок, с помощью которых осуществляется управление световым табло. После нажатия любой кнопки некоторые лампочки на табло переключаются (для каждой кнопки есть свой набор лампочек, причём наборы могут пересекаться). Доказать, что число состояний, в которых может находиться табло, равно некоторой степени числа 2.


Решение

   Пусть число лампочек равно N, количество кнопок — n. Обозначим через Ai подмножество лампочек, которое переключает i-я кнопка, то есть узор, который получается из начального состояния B0 — "все лампочки не горят" — при нажатии i-й кнопки; мы будем также говорить об "операции Ai", понимая под этим нажатие i-й кнопки. Приведем несколько способов доказательства утверждения задачи.

   Первый способ. Всего существует 2N различных узоров светового табло, потому что каждая из N лампочек может находиться в двух состояниях — гореть или не гореть. Пусть нажатием кнопок из начального узора B0 можно получить m разных узоров  B0, B1,..., Bm–1.
Тогда из любого начального узора X можно получить такое же количество узоров — это те узоры, которые отличаются от X на множествах
B0, ..., Bm–1.  Разобьем все 2N узоров на несколько классов: отнесем к одному классу те узоры, которые можно получить друг из друга нажатием кнопок. В каждом классе будет по m узоров. Поэтому 2N делится на m; следовательно, m — степень двойки.

   Второй способ. Пусть кнопки занумерованы так, что ни один из s узоров  A1, A2, ..., As  нельзя получить комбинацией предыдущих, а каждый из остальных  ks  узоров  As+1, ..., Ak  можно получить комбинацией некоторых из операций  A1, A2, ..., As.  Тогда общее число узоров m, которое можно получить из начального состояния B0, равно 2s. В самом деле, все комбинации операций  A1, ..., As,  соответствующие 2s различным подмножествам множества  {1, 2,..., s},  дают различные узоры: если бы какие-то два из них совпадали:
Ai1Ai2...Aim = Aj1Aj2...Ajl,

то узор с наибольшим из входящих в это равенство номеров можно было бы получить комбинацией предыдущих. Например, если  AB = CD,  то   CAB = CCD = D   (двойное нажатие на кнопку не меняет состояния табло).

   Третий способ. Посмотрим вначале не на все N лампочек, а на первые L из них. Пусть на этих лампочках из начального состояния B0 можно получить mL различных узоров. Затем посмотрим на (L+1)-ю лампочку. Если состояние (L+1)-й лампочки вполне определяется набором состояний первых L лампочек, то  mL+1 = mL.  Если же хотя бы два узора совпадают на первых L лампочках, но отличаются на (L+1)-й, то можно получить узор, в котором первые L лампочек не горят, а (L+1)-я горит. Тогда из каждого узора наших L лампочек можно получить два различных узора из первых  L + 1  лампочек, то  mL+1 = 2mL.  Поскольку одна (первая) лампочка может находиться в двух состояниях, ясно, что интересующее нас  m = mN  будет степенью двойки.

Замечания

См. также задачу 74200.

Для знатоков. Фактически все решения основаны на следующей общей идее. На множестве P всех подмножеств N-элементного множества M зададим операцию  A Δ B = (A U B) \ (AB)  (симметрическая разность), превращающую P в группу. Это следующим образом соответствует нашей задаче: если горят лампочки из B, и мы меняем состояние всех лампочек из A, то получится узор  A Δ B.  Состояния, в которых может находиться табло, — это элементы подгруппы, порожденной множествами  A1, ..., An.  По теореме Лагранжа порядок группы (а он равен 2N) делится на порядок подгруппы.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 43
Год 1980
вариант
Класс 9
задача
Номер 2
олимпиада
Название Московская математическая олимпиада
год
Номер 43
Год 1980
вариант
Класс 10
задача
Номер 2

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

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