|
|
 |
Условие
В каждой клетке таблицы размером 4×4 стоит знак "+" или "–". Разрешено одновременно менять знаки на противоположные в любой клетке и во всех клетках, имеющих с ней общую сторону. Сколько разных таблиц можно получить, многократно применяя такие операции?
Решение
Будем считать, что в каждой клетке находится кнопка, нажимая на которую мы меняем знак в этой клетке и во всех соседних.
Оценка снизу. Заметим, что, нажимая кнопки во второй строке, можно привести в произвольное состояние первую строку (каждая кнопка меняет знак в клетке над ней и не меняет состояние остальных клеток первой строки). После этого, нажимая кнопки в третьей строке, можно получить произвольный набор знаков во второй строке, и наконец, нажимая кнопки четвёртой строки, получить произвольную третью строку. Итак, из любой таблицы можно получить не менее 212 различных таблиц (отличающихся уже в первых трёх строках).
Оценка сверху.
Первый способ. Изначально у нас есть 16 кнопок. Назовём 12 кнопок в белых клетках белыми, а 4 в серых – серыми (см. рис.). Результата от нажатия серой кнопки можно достичь, нажав вместо этого несколько белых (для верхней серой кнопки – это белые кнопки, помеченные точками; для остальных трёх серых кнопок нужный набор белых получается поворотами рисунка на 90°, 180° и 270°).
Итак, если таблицу можно получить, то достаточно последовательности нажатий белых кнопок. Ясно, что результат не зависит от порядка нажатий, поэтому пару нажатий на одну и ту же кнопку можно выкинуть. В итоге оставшиеся в последовательности кнопки будут нажаты по разу. Итак, каждой искомой таблице соответствует набор белых кнопок, нажатием которых она получается. Но таких наборов (а, значит, и таблиц) не более 212.
Поворачивая рисунок на 90°, 180° и 270° убеждаемся в том, что знаки в четырёх серых клетках полученной после операций таблицы полностью определяются остальными 12 знаками (расположенных в белых клетках) этой таблицы (и исходной таблицей A). Это означает, что из A можно получить не более 212 различных таблиц.
Замечания
1. Для знатоков. С точки зрения линейной алгебры задача тривиальна. Каждой разрешённой операции можно поставить в соответствие вектор в 16-мерном пространстве над Z2. Требуется найти размерность линейной оболочки этих 16 векторов. Это можно проделать, например, вычислив по методу Гаусса ранг соответствующей матрицы 16×16 (он равен 12). Требуется примерно 10 минут и полстранички клетчатой бумаги. Впрочем, приведённые решения тоже использовали методы линейной алгебры: в первом мы фактически построили базис линейной оболочки, во втором – базис системы линейных инвариантов.
2. 7 баллов.
