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