|
|
 |
Условие
В таблице из n столбцов и 2n строк, в которых выписаны все возможные различные наборы из n чисел 1 и –1, некоторые числа заменены нулями. Докажите, что можно выбрать некоторое непустое подмножество строк так, что:
а) сумма всех чисел в выбранных строках равна 0;
б) сумма всех выбранных строк есть нулевая строка.
(Строки складываются покоординатно как векторы.)
Решение
а) Первый способ. См. б).
Второй способ. Индукция по n. База (n = 1) очевидна.
Шаг индукции. Рассмотрим исходную таблицу A размера 2n×n и испорченную таблицу B, полученную из A заменой некоторых чисел нулями. Заметим, что если в какой-то строке таблицы B встречаются как единицы, так и минус единицы, то их число можно уменьшить, заменив одну единицу и одну минус единицу нулями. При этом сумма чисел в строке не изменится, поэтому на справедливость доказываемого утверждения это не повлияет. Поэтому можно считать, что в таблице B нет строк с числами разных знаков.
Возьмём таблицу A' размера 2n–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 равна нулю.
б) См. задачу 107820.
Замечания
баллы: 4 + 5
