ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 109675
УсловиеВ каждую клетку квадратной таблицы размера (2n – 1)×(2n – 1) ставится одно из чисел 1 или – 1. Расстановку чисел назовём удачной, если каждое число равно произведению всех соседних с ним (соседними считаются числа, стоящие в клетках с общей стороной). Найдите число удачных расстановок. Решение 1 Лемма. Пусть в таблице из 2n – 1 столбцов и k строк (k + 1 не кратно 3)
числа ±1 расставлены удачно. Тогда все числа в таблице равны единице. Итак, для всех таблиц размера 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, откуда то есть то же соотношение верно для "разрежённой" таблицы, состоящей из чисел, находящихся в пересечениях нечётных строк с нечётными столбцами. Эта таблица 2n–1-периодична, поэтому по предположению индукции она состоит из единиц. Аналогично остальные три "разрежённых" подтаблицы состоят из единиц, что и требовалось. ОтветУдачная расстановка единственна – все числа равны единице. .Источники и прецеденты использования |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|