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

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

Условие

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


Решение

  Будем считать, что в каждой клетке находится кнопка, нажимая на которую мы меняем знак в этой клетке и во всех соседних. Заметим, что нажимая кнопки во второй строке мы можем привести в произвольное состояние первую строку (каждая кнопка меняет знак в клетке над ней и не меняет состояние остальных клеток первой строки). После этого, нажимая кнопки в третьей строке, мы можем получить произвольный набор знаков во второй строке, и наконец, нажимая кнопки четвёртой строки, получить произвольную третью строку. Итак, из любой таблицы можно получить не менее 212 различных таблиц (отличающихся уже в первых трёх строках).
  Приведём два способа получить оценку сверху.

  Первый способ. Изначально у нас есть 16 кнопок. Назовем 12 кнопок в белых клетках основными, а 4 в закрашенных – вспомогательными (см. рис.). Результата от нажатия вспомогательной кнопки можно достичь, нажав вместо этого несколько основных (для верхней вспомогательной кнопки – это основные кнопки, помеченные точками; для остальных трёх вспомогательных кнопок нужный набор основных получается поворотами рисунка на 90°, 180° и 270°).
  Итак, если таблицу можно получить, то достаточно последовательности нажатий основных кнопок. Ясно, что результат не зависит от порядка нажатий кнопок. Поэтому пару нажатий на одну и ту же кнопку можно выкинуть. В итоге оставшиеся в последовательности кнопки будут нажаты по разу. Итак, каждой искомой таблице соответствует набор основных кнопок, нажатием которых она получается. Но таких наборов (а, значит, и таблиц) не более 212.

  Второй способ. Легко проверить, что каждая операция меняет состояние чётного числа из помеченных точками клеток. Поэтому чётность количества плюсов на помеченных клетках остается той же, что и в исходной таблице A. Тем самым знак в закрашенной помеченной клетке определяется чётностью количества плюсов в помеченных незакрашенных клетках.
  Поворачивая рисунок на 90°, 180° и 270° убеждаемся в том, что знаки в четырёх закрашенных клетках полученной после операций таблицы полностью определяются остальными 12 знаками (расположенных в незакрашенных клетках) этой таблицы (и исходной таблицей A). Это означает, что из A можно получить не более 212 различных таблиц.

Замечания

1. Для знатоков. С точки зрения линейной алгебры задача тривиальна. Каждой разрешенной операции можно поставить в соответствие вектор в 16-мерном пространстве над Z2. Требуется найти размерность линейной оболочки этих 16 векторов. Это можно проделать, например, вычислив по методу Гаусса ранг соответствующей матрицы 16×16 (он равен 12). Требуется примерно 10 минут и полстранички клетчатой бумаги. Впрочем, приведённые решения тоже использовали методы линейной алгебры: в первом мы фактически построили базис линейной оболочки, во втором – базис системы линейных инвариантов.

2. 7 баллов.

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

олимпиада
Название Турнир городов
Турнир
Дата 2002/2003
Номер 24
вариант
Вариант весенний тур, основной вариант, 10-11 класс
Задача
Номер 6

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

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