В каждой клетке таблицы 4 на 4 расположена лампочка. Изначально все лампочки выключены. За один ход разрешается поменять состояние на противоположное (вкл на выкл и выкл на вкл) у любых трех лампочек, идущих подряд в строке или столбце. Сколько разных конфигураций может получиться после применения нескольких таких операций? (под конфигурацией понимается табличка, в которой какие-то лампочки горят, а какие-то --- нет)

задан 23 Фев '14 13:42

10|600 символов нужно символов осталось
1

У меня получилось $%2^{12}$% конфигураций.

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

Из приведённого рассуждения следует, что различных конфигураций имеется не меньше $%2^{12}$%. Докажем, что их не больше, рассматривая несколько инвариантов описанной в условии системы преобразований. Для каждой не граничной клетки (которых имеется 4) рассмотрим строку и столбец, её содержащие. Возьмём те 9 клеток, которые не вошли ни в строку, ни в столбец. Легко видеть, что для любых трёх лампочек, идущих подряд, в указанное множество из 9 лампочек входят либо две, либо ни одной. Это значит, что количество горящих лампочек среди указанных девяти всегда имеет одну и ту же чётность (можно утверждать, что оно чётно, так как в самом начале всё было выключено). Из описания следует, что в наше множество из 9 лампочек входит ровно одна не граничная. Тем самым, её состояние однозначно определяется состоянием граничных лампочек. Это верно для любой из четырёх не граничных клеток, так как строку и столбец всегда можно выбрать так, чтобы они её не содержали, и тем самым она попала в нужное нам множество из 9 клеток.

ссылка

отвечен 23 Фев '14 20:57

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,449

задан
23 Фев '14 13:42

показан
578 раз

обновлен
23 Фев '14 20:57

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru