Разделы 
Дополнительно
Задача по математике - 1895
2019-01-21 
В каждую клетку квадратной таблицы размера $(2^n - 1) \times (2^n - 1)$ ставится одно из чисел +1 или -1. Расстановку чисел назовем удачной, если каждое число равно произведению всех соседних с ним (соседними считаются числа, стоящие в клетках с общей стороной). Найдите число удачных расстановок.
Решение:
Первое решение. Докажем индукцией по $n$ следующее утверждение: если в таблице из $2^n - 1$ столбцов и $k$ строк ($k + 1$ не делится на 3) расставлены числа $\pm 1$ так, что выполняется условие задачи, то все числа таблицы равны $+1$. При $n = 1$ имеем один столбец высоты $k$. Пусть в нем стоят числа $a_1, a_2,\cdots, a_n$ - по порядку сверху вниз. Тогда $a_1 = a_2$ (условие задачи для первой клетки), $a_2 = a_1a_3$, следовательно $a_3 = 1, 1 = a_3 = a_2a_4$, следовательно $a_4 = a_2 = a_1$. И так далее. Получаем, что все числа, стоящие в клетках с номером, кратным трем, равны 1, а все остальные равны $a_1$. Поскольку $k +1$ не делится на 3, то возможны две ситуации:
1) $a_{k-1} = a_1, a_k = 1$;
2) $a_{k-1} = 1, a_k = a_1$.
Но $a_k$ равен произведению своих соседей, т. е. $a_k = a_{k-1}$. Следовательно, $a_1 = 1$, и столбец состоит из одних единичек. Для доказательства индуктивного перехода введем следующие обозначения. Если $A, B$ - две таблицы одинакового размера, то пусть $A \cdot B$ - таблица, в каждой клетке которой записано произведение чисел из тех же клеток таблиц $A$ и $В$. $A$ будет обозначать таблицу, полученную из $A$ зеркальной симметрией: первый столбец меняется с последним, второй - с предпоследним и так далее. Нетрудно видеть, что если таблицы $A$ и $B$ удовлетворяют условию, то это же можно сказать о таблицах $A \cdot В$ и $A$. Таблицу, в которой стоят только единицы, будем обозначать $1$.
Докажем, что если в таблице размера $k \times (2^{n+1} - 1)$ расставлены числа согласно условию, то расстановка симметрична: $A = \overline{A}$. Это равносильно тому, что $A \cdot \overline{A} = 1$. В таблице $A \cdot \overline{A}$ весь центральный столбец (с номером $2^n$) состоит из единиц, так как центральные столбцы у $A$ и $\overline{A}$ одинаковы. Следовательно, если мы рассмотрим отдельно часть таблицы $A \cdot \overline{A}$ слева от центрального столбца, то числа в этой меньшей таблице расставлены согласно условию. Размер ее - $k \times (2^n - 1)$, так что по предположению индукции, все числа в ней - единицы. То же касается и правой части $A \cdot \overline{A}$. Итак, $A \cdot \overline{A} = 1$. Это значит, что для любого числа из центрального столбца таблицы $A$ числа слева и справа от него одинаковы, поэтому само оно равно произведению своих верхнего и нижнего соседей. Как мы доказали в базе индукции, из этого следует, что центральный столбец заполнен единицами. Теперь снова рассмотрим часть таблицы $A$ слева от центрального столбца. Применяя предположение индукции, убеждаемся, что в ней стоят только единицы. Правая часть симметрична левой, поэтому и она состоит из единиц. Переход индукции доказан. Для всех таблиц размера $к \times (2^n - 1)$ (где $k + 1$ не делится на 3) единственность расстановки доказана. Если $k = 2^n - 1$, то $k + 1 = 2^n$, поэтому доказано и утверждение задачи.
Второе решение. Пусть $R$ - удачная расстановка в таблице $(2^n - 1) \times (2^n - 1)$. Расставим числа на клетчатой плоскости, как показано на рис. (симметрия буквы $R$ означает, что там стоит таблица $R$, отраженная соответствующим образом). Тогда расстановка на всей плоскости удовлетворяет нашим условиям (т. е. любое число есть произведение его четырех соседей) и, кроме того, она $2^{n+1}$-периодична, т. е. при сдвиге на $2^{n+1}$ вверх или вправо она переходит в себя. Докажем индукцией по $n$, что любая $2^n$-периодичная перестановка состоит из единиц.
База при $n = 0$ очевидна: $a = a^4,$ где $a$ - число в клетке. Пусть $n \geq 1$. Рассмотрим фрагмент таблицы, показанный на рис. Имеем: $a_{23} = a_{13}a_{22}a_{24}a_{33}, a_{32} = a_{22}a_{31}a_{33}a_{42}, a_{34} = a_{24}a_{33}a_{35}a_{44}, a_{43} = a_{33}a_{42}a_{44}a_{53}$, откуда $a_{33} = a_{23}a_{32}a_{34}a_{43} = a_{13}a_{31}a_{35}a_{53}a_{22}^2a_{24}^2a_{42}^2a_{44}^2a_{33}^4$, т. е. то же соотношение верно для "разреженной" таблицы, состоящей из чисел, находящихся в пересечениях нечетных строк с нечетными столбцами. Эта таблица 2^{n?1}-периодична, поэтому по предположению индукции она состоит из единиц. Абсолютно аналогично, остальные три "разреженных" подтаблицы состоят из единиц, что и требовалось.
Ответ. Удачная расстановка единственна - все числа равны $+1$.
В каждую клетку квадратной таблицы размера $(2^n - 1) \times (2^n - 1)$ ставится одно из чисел +1 или -1. Расстановку чисел назовем удачной, если каждое число равно произведению всех соседних с ним (соседними считаются числа, стоящие в клетках с общей стороной). Найдите число удачных расстановок.
Решение:
Первое решение. Докажем индукцией по $n$ следующее утверждение: если в таблице из $2^n - 1$ столбцов и $k$ строк ($k + 1$ не делится на 3) расставлены числа $\pm 1$ так, что выполняется условие задачи, то все числа таблицы равны $+1$. При $n = 1$ имеем один столбец высоты $k$. Пусть в нем стоят числа $a_1, a_2,\cdots, a_n$ - по порядку сверху вниз. Тогда $a_1 = a_2$ (условие задачи для первой клетки), $a_2 = a_1a_3$, следовательно $a_3 = 1, 1 = a_3 = a_2a_4$, следовательно $a_4 = a_2 = a_1$. И так далее. Получаем, что все числа, стоящие в клетках с номером, кратным трем, равны 1, а все остальные равны $a_1$. Поскольку $k +1$ не делится на 3, то возможны две ситуации:
1) $a_{k-1} = a_1, a_k = 1$;
2) $a_{k-1} = 1, a_k = a_1$.
Но $a_k$ равен произведению своих соседей, т. е. $a_k = a_{k-1}$. Следовательно, $a_1 = 1$, и столбец состоит из одних единичек. Для доказательства индуктивного перехода введем следующие обозначения. Если $A, B$ - две таблицы одинакового размера, то пусть $A \cdot B$ - таблица, в каждой клетке которой записано произведение чисел из тех же клеток таблиц $A$ и $В$. $A$ будет обозначать таблицу, полученную из $A$ зеркальной симметрией: первый столбец меняется с последним, второй - с предпоследним и так далее. Нетрудно видеть, что если таблицы $A$ и $B$ удовлетворяют условию, то это же можно сказать о таблицах $A \cdot В$ и $A$. Таблицу, в которой стоят только единицы, будем обозначать $1$.
Докажем, что если в таблице размера $k \times (2^{n+1} - 1)$ расставлены числа согласно условию, то расстановка симметрична: $A = \overline{A}$. Это равносильно тому, что $A \cdot \overline{A} = 1$. В таблице $A \cdot \overline{A}$ весь центральный столбец (с номером $2^n$) состоит из единиц, так как центральные столбцы у $A$ и $\overline{A}$ одинаковы. Следовательно, если мы рассмотрим отдельно часть таблицы $A \cdot \overline{A}$ слева от центрального столбца, то числа в этой меньшей таблице расставлены согласно условию. Размер ее - $k \times (2^n - 1)$, так что по предположению индукции, все числа в ней - единицы. То же касается и правой части $A \cdot \overline{A}$. Итак, $A \cdot \overline{A} = 1$. Это значит, что для любого числа из центрального столбца таблицы $A$ числа слева и справа от него одинаковы, поэтому само оно равно произведению своих верхнего и нижнего соседей. Как мы доказали в базе индукции, из этого следует, что центральный столбец заполнен единицами. Теперь снова рассмотрим часть таблицы $A$ слева от центрального столбца. Применяя предположение индукции, убеждаемся, что в ней стоят только единицы. Правая часть симметрична левой, поэтому и она состоит из единиц. Переход индукции доказан. Для всех таблиц размера $к \times (2^n - 1)$ (где $k + 1$ не делится на 3) единственность расстановки доказана. Если $k = 2^n - 1$, то $k + 1 = 2^n$, поэтому доказано и утверждение задачи.
Второе решение. Пусть $R$ - удачная расстановка в таблице $(2^n - 1) \times (2^n - 1)$. Расставим числа на клетчатой плоскости, как показано на рис. (симметрия буквы $R$ означает, что там стоит таблица $R$, отраженная соответствующим образом). Тогда расстановка на всей плоскости удовлетворяет нашим условиям (т. е. любое число есть произведение его четырех соседей) и, кроме того, она $2^{n+1}$-периодична, т. е. при сдвиге на $2^{n+1}$ вверх или вправо она переходит в себя. Докажем индукцией по $n$, что любая $2^n$-периодичная перестановка состоит из единиц.
База при $n = 0$ очевидна: $a = a^4,$ где $a$ - число в клетке. Пусть $n \geq 1$. Рассмотрим фрагмент таблицы, показанный на рис. Имеем: $a_{23} = a_{13}a_{22}a_{24}a_{33}, a_{32} = a_{22}a_{31}a_{33}a_{42}, a_{34} = a_{24}a_{33}a_{35}a_{44}, a_{43} = a_{33}a_{42}a_{44}a_{53}$, откуда $a_{33} = a_{23}a_{32}a_{34}a_{43} = a_{13}a_{31}a_{35}a_{53}a_{22}^2a_{24}^2a_{42}^2a_{44}^2a_{33}^4$, т. е. то же соотношение верно для "разреженной" таблицы, состоящей из чисел, находящихся в пересечениях нечетных строк с нечетными столбцами. Эта таблица 2^{n?1}-периодична, поэтому по предположению индукции она состоит из единиц. Абсолютно аналогично, остальные три "разреженных" подтаблицы состоят из единиц, что и требовалось.
Ответ. Удачная расстановка единственна - все числа равны $+1$.
