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

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

Условие

На белых клетках бесконечной шахматной доски, заполняющей верхнюю полуплоскость, записаны какие-то числа так, что для каждой чёрной клетки сумма чисел, стоящих в двух соседних с ней клетках – справа и слева, – равна сумме двух других чисел, стоящих в соседних с ней клетках – сверху и снизу. Известно число, стоящее в одной клетке n-й строки (крестик на рисунке), а требуется узнать число, стоящее над ним в (n+2)-й строке (знак вопроса на рисунке). Сколько ещё чисел, стоящих в двух нижних строках (точки на рисунке), нужно для этого знать?


Решение

  Введём следующие обозначения (рис. слева): x – неизвестное число в (n+2)-й строке, dn – данное число в n-й строке. Числа a и b нам не даны, но известно что  x + dn = a + b,  откуда  x = dn + (a – dn) + (b – dn).  Так как  b + dn–1 = dn + bn,  то b – dn = bn – dn–1.  Аналогично
bn – dn–1bn–1dn–2 = bn–2dn–3 = ... = b1dn.
  Тем самым,  b – dn = b1d0.  Точно так же  a – dn = an – cn–1 = an–1cn–2 = ... = a1c0.
  Значит,  x = dn + (a1c0) + (b1d0).
  Итак, чтобы определить x, нужно, кроме dn, знать всего 4 числа a1, b1, c0 и d0 в первой и нулевой строках.

  Нельзя ли обойтись меньше, чем четырьмя числами?
  В вырожденном случае (при  n = 0)  – можно: тогда  x = a1 + b1d0  (рис. справа), и, кроме d0, достаточно знать только два числа (a1 и b1).
  При  n ≥ 1  обойтись меньше, чем четырьмя числами, нельзя, причём, кроме dn, нужно знать именно числа a1, b1, c0 и d0: если хотя бы одно из этих чисел неизвестно, то знание даже всех остальных чисел в первой и нулевой строках не дает возможности определить x. Докажем это.
  Пусть, например, число a1 неизвестно. Тогда ничто не мешает задать его произвольно. Это было бы совершенно очевидно, если бы число dn не было известно. В этом случае числа первой и нулевой строк не связаны никакими соотношениями, – их можно задать все совершенно произвольно, а по ним определить все остальные числа (сначала во второй строке, затем в третьей, и т.д.). При этом  dn = P – N,  где P – сумма чисел первой строки, стоящих между a1 и b1 (исключая сами a1 и b1), а N – сумма чисел нулевой строки, стоящих между c0 и d0 (исключая сами c0 и d0); равенство  dn = P – N  легко доказывается индукцией по n; при этом нужно воспользоваться выведенной ранее формулой
x = dn + (a1c0) + (b1d0).
  Таким образом,  dn = P – N  – единственное соотношение, связывающее dn и числа нулевой и первой строк; a1 в него не входит. Значит, даже зная dn и все числа нулевой и первой строк, кроме a1, мы можем задать a1 произвольно. Но, зафиксировав b1, c0, d0 и dn и придавая a1 различные значения, мы будем получать разные значения и для x.
  Итак, знание a1, b1, c0 и d0 необходимо и достаточно для определения x при данном dn.


Ответ

4 числа.

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

журнал
Название "Квант"
год
Год 1972
выпуск
Номер 9
Задача
Номер М164

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

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