Задача 73699

Темы:    [ Линейные рекуррентные соотношения ] [ Числовые таблицы и их свойства ]

Сложность: 5- Классы: 8,9,10

Условие

Автор: Гервер М.Л.

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

Решение

  Введём следующие обозначения (рис. слева): x – неизвестное число в (n+2)-й строке, d_n – данное число в n-й строке. Числа a и b нам не даны, но известно что  x + d_n = a + b,  откуда  x = d_n + (a – d_n) + (b – d_n).  Так как  b + d_n–1 = d_n + b_n,  то b – d_n = b_n – d_n–1.  Аналогично
b_n – d_n–1 – b_n–1 – d_n–2 = b_n–2 – d_n–3 = ... = b₁ – d_n.
  Тем самым,  b – d_n = b₁ – d₀.  Точно так же  a – d_n = a_n – c_n–1 = a_n–1 – c_n–2 = ... = a₁ – c₀.
  Значит,  x = d_n + (a₁ – c₀) + (b₁ – d₀).
  Итак, чтобы определить x, нужно, кроме d_n, знать всего 4 числа a₁, b₁, c₀ и d₀ в первой и нулевой строках.

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

Ответ

4 числа.

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

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