|
|
 |
Условие
В каждую клетку квадратной таблицы размера (2n – 1)×(2n – 1) ставится одно из чисел 1 или – 1. Расстановку чисел назовём удачной, если каждое число равно произведению всех соседних с ним (соседними считаются числа, стоящие в клетках с общей стороной). Найдите число удачных расстановок.
Решение 1
Лемма. Пусть в таблице из 2n – 1 столбцов и k строк (k + 1 не кратно 3)
числа ±1 расставлены удачно. Тогда все числа в таблице равны единице.
Доказательство. Индукция по n.
База. При n = 1 имеем один столбец. Пусть в нем стоят числа a1, a2, ..., ak – по порядку сверху вниз. Тогда a1 = a2 (условие для первой клетки),
a2 = a1a3, следовательно, a3 = 1, 1 = a3 = a2a4, следовательно, a4 = a2 = a1. И так далее: все числа, стоящие в клетках с номером, кратным 3, равны 1, а все остальные
равны a1. Поскольку k + 1 не кратно 3, то возможны две ситуации: 1) ak– = a1, ak = 1; 2) ak–1 = 1, ak = a1. Но ak равен произведению своих соседей, то есть ak = ak–1. Следовательно, a1 = 1, и столбец состоит из одних единичек.
Шаг индукции. Введём следующие обозначения. Если A, B – две таблицы одинакового размера, то пусть A·B – таблица, в каждой клетке которой записано произведение чисел из тех же клеток таблиц A и B. A' – таблица, полученная из A зеркальной симметрией: первый столбец меняется с последним, второй – с предпоследним и так далее. Ясно, что если числа в таблицах A и B расставлены удачно, то это же верно для таблиц A·B и A'.
Таблицу, в которой стоят только единицы, будем обозначать 1.
Докажем, что если в таблице A размера k×(2n+1 – 1) числа расставлены удачно, то расстановка симметрична: A = A'. Это равносильно тому, что
A·A' = 1.
В таблице A·A' весь центральный столбец (с номером 2n) состоит из единиц, так как центральные столбцы у A и A' одинаковы. Следовательно, если мы рассмотрим отдельно часть таблицы A·A' слева от центрального столбца, то в этой меньшей таблице
числа расставлены удачно. Размер её – k×(2n – 1), так что по предположению индукции все числа в ней – единицы. То же касается и правой части A·A'. Итак, A·A' = 1.
Значит, для каждого числа из центрального столбца таблицы A числа слева и справа от него одинаковы, поэтому само оно равно произведению своих верхнего и нижнего соседей.
Как показано выше, из этого следует, что центральный столбец заполнен единицами. Теперь снова рассмотрим часть таблицы A слева от центрального столбца. Применяя предположение индукции, убеждаемся, что в ней стоят только единицы. Правая часть симметрична левой, поэтому и она состоит из единиц.
Итак, для всех таблиц размера k×(2n – 1), где k + 1 не кратно 3, единственна. В частности, она единственна при k = 2n – 1, потому что k + 1 = 2n.
Решение 2
Пусть R – удачная расстановка в таблице (2n – 1)×(2n – 1). Расставим числа на клетчатой плоскости, как показано на рисунке слева (симметрия буквы R означает, что там стоит таблица R, отраженная соответствующим образом). Тогда расстановка на всей плоскости удачна (то есть любое число есть произведение его четырёх соседей) и, кроме того, она 2n+1-периодична, то есть при сдвиге на 2n+1 вверх или вправо она переходит в себя.
База (n = 0) очевидна: a = a4, где a – число в клетке.
Шаг индукции. Пусть n ≥ 1. Рассмотрим фрагмент таблицы, показанный на рисунке справа.
Имеем: a23 = a13a22a24a33, a32 = a22a31a33a42, a34 = a24a33a35a44, a43 = a33a42a44a53, откуда
Ответ
Удачная расстановка единственна – все числа равны единице.
.