Задача 74200

Темы:    [ Правило произведения ] [ Разбиения на пары и группы; биекции ] [ Комбинаторика орбит ] [ Теорема Лагранжа ] [ Числовые таблицы и их свойства ]

Сложность: 4 Классы:

Условие

Автор: Гринберг Н.

Световое табло состоит из нескольких ламп, каждая из которых может находиться в двух состояниях (гореть или не гореть). На пульте несколько кнопок, при нажатии каждой из которых одновременно меняется состояние некоторого набора ламп (для каждой кнопки – своего). Вначале лампы не горят.
  а) Докажите, что число различных узоров, которые можно получить на табло, – степень двойки.
  б) Сколько различных узоров можно получить на табло, состоящем из mn лампочек, расположенных в форме прямоугольника размером m×n, если кнопками можно переключить как любой горизонтальный, так и любой вертикальный ряд ламп?

Решение

  а) См. задачу 79383.

  б) Заменим табло числовой таблицей с элементами x_ij: будем считать, что  x_ij = –1,  если лампочка в i-й строке и j-м столбце горит; в противном случае  x_ij = 1.  Допустимые операции (их  m + n)  – это умножение строки или столбца на –1. Очевидно, что из начального состояния (все  x_ij = 1)  мы можем получить произвольный набор из  m + n – 1  чисел ±1 в первой строке и в первом столбце. Каждый из остальных элементов таблицы этими  m + n – 1  числами определяется однозначно, поскольку (как нетрудно проверить) при любых допустимых операциях будет сохраняться равенство  x_ij = x₁₁x_i1x_1j.
  Поэтому общее число узоров, которые можно получить, равно 2^m+n–1.

Ответ

б) 2^m+n–1 узоров.

Замечания

Другие примеры "разрешимых случаев" см. в решениях Задачника "Кванта".

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

журнал
Название	"Квант"
год
Год	1981
выпуск
Номер	1
Задача
Номер	М665