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

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

Условие

Автор: Любшин Д.

В каждую клетку квадратной таблицы размера  (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 = a1ak = 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, что любая 2n-периодичная перестановка состоит из единиц.
  База  (n = 0)  очевидна:  a = a4,  где a – число в клетке.
  Шаг индукции. Пусть  n ≥ 1.  Рассмотрим фрагмент таблицы, показанный на рисунке справа.
  Имеем:  a23 = a13a22a24a33a32 = a22a31a33a42a34 = a24a33a35a44a43 = a33a42a44a53,  откуда
  то есть то же соотношение верно для "разрежённой" таблицы, состоящей из чисел, находящихся в пересечениях нечётных строк с нечётными столбцами. Эта таблица 2n–1-периодична, поэтому по предположению индукции она состоит из единиц. Аналогично остальные три "разрежённых" подтаблицы состоят из единиц, что и требовалось.


Ответ

Удачная расстановка единственна – все числа равны единице.

.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1998
Этап
Вариант 5
Класс
Класс 10
задача
Номер 98.5.10.8

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

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