Задача
Световое табло состоит из нескольких ламп, каждая из которых может находиться в двух состояниях (гореть или не гореть). На пульте несколько кнопок, при нажатии каждой из которых одновременно меняется состояние некоторого набора ламп (для каждой кнопки – своего). Вначале лампы не горят.
а) Докажите, что число различных узоров, которые можно получить на табло, – степень двойки.
б) Сколько различных узоров можно получить на табло, состоящем из mn лампочек, расположенных в форме прямоугольника размером m×n, если кнопками можно переключить как любой горизонтальный, так и любой вертикальный ряд ламп?
Решение
а) См. задачу 179383. б) Заменим табло числовой таблицей с элементами xij: будем считать, что xij = –1, если лампочка в i-й строке и j-м столбце горит; в противном случае xij = 1. Допустимые операции (их m + n) – это умножение строки или столбца на –1. Очевидно, что из начального состояния (все xij = 1) мы можем получить произвольный набор из m + n – 1 чисел ±1 в первой строке и в первом столбце. Каждый из остальных элементов таблицы этими m + n – 1 числами определяется однозначно, поскольку (как нетрудно проверить) при любых допустимых операциях будет сохраняться равенство xij = x11xi1x1j.
Поэтому общее число узоров, которые можно получить, равно 2m+n–1.
Ответ
б) 2m+n–1 узоров.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь