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

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

Условие

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


Решение

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

  б) Заменим табло числовой таблицей с элементами 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 узоров.

Замечания

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

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

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

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

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