Олимпиадная задача по математике: сумма строк с нулями и –1, 1 в таблице (Кондаков, Черноруцкий)

  а) Первый способ. См. б).

  Второй способ. Индукция по n. База  (n = 1)  очевидна.

  Шаг индукции. Рассмотрим исходную таблицу A размера 2ⁿ×n и испорченную таблицу B, полученную из A заменой некоторых чисел нулями. Заметим, что если в какой-то строке таблицы B встречаются как единицы, так и минус единицы, то их число можно уменьшить, заменив одну единицу и одну минус единицу нулями. При этом сумма чисел в строке не изменится, поэтому на справедливость доказываемого утверждения это не повлияет. Поэтому можно считать, что в таблице B нет строк с числами разных знаков.

  Возьмём таблицу A' размера  2^n–1×(n–1)  из всевозможных векторов размерности  n – 1  с координатами ±1. Построим по ней испорченную таблицу B'.

  Каждой строке a таблицы A' соответствуют две строки  (a, 1)  и  (a, –1)  в таблице A. Из них получены две строки  (b, δ)  и  (b', –ε)  в таблице B, где δ, ε равны 0 или 1. В таблицу B' вместо a впишем строку b'', полученную по следующему алгоритму.

  1)  δ = 0.  Тогда  b'' = b.

  2)  δ = 1,  ε = 0.  Тогда  b'' = b'.

  3)  δ = ε = 1.  Тогда  b'' = b + b'.  Мы вправе это сделать, поскольку в строке b нет минус единиц, в строке b' нет единиц, значит, строка

b + b'  может быть получена из a вписыванием нулей. Заметим, что в этом случае  (b, δ) + (b', –ε) = (b'', 0).

  Итак, в любом случае сумма чисел в строке b'' по построению равна сумме чисел в одной или двух соответствующих строках таблицы B.

  По предположению индукции из построенной страницы B' можно выбрать несколько строк, общая сумма чисел в которых равна нулю. Но тогда и общая сумма чисел в соответствующих строках таблицы B равна нулю.   б) См. задачу 207820.

Ответ задачи отсутствует