Олимпиадные задачи по математике - сложность 3 с решениями

На пульте имеется несколько кнопок, с помощью которых осуществляется управление световым табло. После нажатия любой кнопки некоторые лампочки на табло переключаются (для каждой кнопки есть свой набор лампочек, причём наборы могут пересекаться). Доказать, что число состояний, в которых может находиться табло, равно некоторой степени числа 2.

Световое табло состоит из нескольких ламп, каждая из которых может находиться в двух состояниях (гореть или не гореть). На пульте несколько кнопок, при нажатии каждой из которых одновременно меняется состояние некоторого набора ламп (для каждой кнопки – своего). Вначале лампы не горят.

  а) Докажите, что число различных узоров, которые можно получить на табло, – степень двойки.

  б) Сколько различных узоров можно получить на табло, состоящем из <i>mn</i> лампочек, расположенных в форме прямоугольника размером <i>m</i>×<i>n</i>, если кнопками можно переключить как любой горизонтальный, так и любой вертикальный ряд ламп?