Задача 79383
|
|
 |
Условие
На пульте имеется несколько кнопок, с помощью которых осуществляется управление световым табло. После нажатия любой кнопки некоторые лампочки на табло переключаются (для каждой кнопки есть свой набор лампочек, причём наборы могут пересекаться). Доказать, что число состояний, в которых может находиться табло, равно некоторой степени числа 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 нельзя получить комбинацией предыдущих, а каждый из остальных k − s узоров 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 будет степенью двойки.
