Разделы 
Дополнительно
Задача по математике - 3239
2019-05-29 
В таблице $2^n \times n$ были выписаны всевозможные строки длины $n$ из чисел 1 и -1. Затем часть чисел заменили нулями. Докажите, что можно выбрать несколько строк, сумма которых есть строка из нулей. (Суммой строк называется строка, элементы которой являются суммами соответствующих элементов слагаемых.)
Решение:
Первый способ. Будем выбирать строки «испорченной» нулями таблицы по очереди и следить за суммой $S=S(m)$ выбранных строк. Первой возьмем «испорченную» строку, которая получилась из $(1, 1, \cdots, 1)$. Строка $S(1)$ будет состоять из 0 и 1 (если в ней только нули, то уже одна эта строка дает нужное множество). Второй строкой возьмем «испорченную» строку, полученную из той, в которой стояли -1 на тех местах, где в $S(1)$ стоят 1. Тогда $S(2)$ будет стоять из 0 и 1. Пусть $k$ строк уже выбраны. Если сумма $S(k)$ совпадает с некоторой из предыдущих сумм $S(m)$, где $m
Если на некотором шаге получится сумма, которая уже встречалась раньше, то задача решена (см. выше), если нет, - то, в конце концов, все строки будут выбраны. При этом мы получим $2^n$ различных сумм $S(k)$. Так как различных наборов из 0 и 1 длины $n$ тоже $2^n$, то все строки из 0 и 1 встретятся в качестве сумм $S(k)$. Значит, на каком-то шаге, $S(k)=0$, и нужное множество - первые $k$ выбранных строк.
Второй способ. Обозначим строки исходной таблицы $a_i$, а строки таблицы, «испорченной» нулями, $b_i (i=1, 2, \cdots, 2^n)$. Построим также таблицу со строками $c_i=a_i-2b_i$. Иными словами, строка $c_i$ совпадает с ai в тех местах, которые заменялись нулями, и противоположна ей в остальных. В частности, построенная таблица состоит из $ \pm1$. Поэтому для любого $i$ найдется $j(i)$ такое, что $c_i = a_{j(i)}$. Рассмотрим теперь последовательность $i_k$, заданную рекуррентным соотношением $i_{k+1} = j(i_k)$. (Первый член последовательности выбирается произвольно.) Поскольку последовательность может принимать лишь конечное число значений, какие-то ее члены равны между собой. Пусть $i_k=i_l$ для некоторых $k
$b_{i_{k}} + b_{i_{k+1}} + \cdots + b_{i_{l-1}} = \frac{1}{2}(a_{i_{k}} - c_{i_{k}}) + \frac{1}{2}(a_{i_{k+1}} - c_{i_{k+1}}) + \cdots + \frac{1}{2}(a_{i_{l-1}} - c_{i_{l-1}}) = \frac{1}{2}(a_{i_{k}} - a_{i_{k+1}} + a_{i_{k+1}} - a_{i_{k+2}} + \cdots + a_{i_{l-1}} - a_{i_{l}}) = \frac{1}{2}(a_{i_{k}} - a_{i_{l}}) = 0$.
Что и требовалось доказать.
В таблице $2^n \times n$ были выписаны всевозможные строки длины $n$ из чисел 1 и -1. Затем часть чисел заменили нулями. Докажите, что можно выбрать несколько строк, сумма которых есть строка из нулей. (Суммой строк называется строка, элементы которой являются суммами соответствующих элементов слагаемых.)
Решение:
Первый способ. Будем выбирать строки «испорченной» нулями таблицы по очереди и следить за суммой $S=S(m)$ выбранных строк. Первой возьмем «испорченную» строку, которая получилась из $(1, 1, \cdots, 1)$. Строка $S(1)$ будет состоять из 0 и 1 (если в ней только нули, то уже одна эта строка дает нужное множество). Второй строкой возьмем «испорченную» строку, полученную из той, в которой стояли -1 на тех местах, где в $S(1)$ стоят 1. Тогда $S(2)$ будет стоять из 0 и 1. Пусть $k$ строк уже выбраны. Если сумма $S(k)$ совпадает с некоторой из предыдущих сумм $S(m)$, где $m
Если на некотором шаге получится сумма, которая уже встречалась раньше, то задача решена (см. выше), если нет, - то, в конце концов, все строки будут выбраны. При этом мы получим $2^n$ различных сумм $S(k)$. Так как различных наборов из 0 и 1 длины $n$ тоже $2^n$, то все строки из 0 и 1 встретятся в качестве сумм $S(k)$. Значит, на каком-то шаге, $S(k)=0$, и нужное множество - первые $k$ выбранных строк.
Второй способ. Обозначим строки исходной таблицы $a_i$, а строки таблицы, «испорченной» нулями, $b_i (i=1, 2, \cdots, 2^n)$. Построим также таблицу со строками $c_i=a_i-2b_i$. Иными словами, строка $c_i$ совпадает с ai в тех местах, которые заменялись нулями, и противоположна ей в остальных. В частности, построенная таблица состоит из $ \pm1$. Поэтому для любого $i$ найдется $j(i)$ такое, что $c_i = a_{j(i)}$. Рассмотрим теперь последовательность $i_k$, заданную рекуррентным соотношением $i_{k+1} = j(i_k)$. (Первый член последовательности выбирается произвольно.) Поскольку последовательность может принимать лишь конечное число значений, какие-то ее члены равны между собой. Пусть $i_k=i_l$ для некоторых $k
$b_{i_{k}} + b_{i_{k+1}} + \cdots + b_{i_{l-1}} = \frac{1}{2}(a_{i_{k}} - c_{i_{k}}) + \frac{1}{2}(a_{i_{k+1}} - c_{i_{k+1}}) + \cdots + \frac{1}{2}(a_{i_{l-1}} - c_{i_{l-1}}) = \frac{1}{2}(a_{i_{k}} - a_{i_{k+1}} + a_{i_{k+1}} - a_{i_{k+2}} + \cdots + a_{i_{l-1}} - a_{i_{l}}) = \frac{1}{2}(a_{i_{k}} - a_{i_{l}}) = 0$.
Что и требовалось доказать.
