Олимпиадная задача на последовательности и шахматную доску (Гервер М.

  Введём следующие обозначения (рис. слева): 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.