Разделы 
Дополнительно
Задача по математике - 105
2014-06-07 
Доказать, что для любых чисел $a_{1}, \cdots, a_{m} \in \mathbf{N}$:
а) существует такой набор из $n < 2^{m}$ чисел, в котором все подмножества имеют разные суммы чисел, причем среди этих сумм содержатся все числа
$a_{1}, \cdots , a_{m}$;
б) существует такой набор из $n \leq m$ чисел, в котором все подмножества имеют разные суммы чисел, причем среди этих сумм содержатся все числа $a_{1}, \cdots , a_{m}$.
Решение:
а) Рассмотрим двоичные записи чисел $a_{1}, \cdots , a_{m}$ и дополним некоторые из них спереди цифрами 0 так, чтобы все записи имели равную длину $k$. Образуем прямоугольную таблицу размером $m \times k$ из нулей и единиц, в которой для каждого значения $i = 1, \cdots , m$ i-я строка представляет собой полученную выше запись числа $a_{i}$. Поскольку каждый столбец этой таблицы состоит из $m$ цифр, то число $n$ различных ненулевых столбцов в ней не превосходит $2^{m} – 1$. Каждому из этих $n$ столбцов поставим в соответствие число, двоичная запись которого содержит цифру 1 в тех и только тех разрядах, в которых таблица содержит столбцы, совпадающие с данным. Полученный набор чисел $b_{1}, \cdots , b_{n}$ удовлетворяет условию задачи. Действительно, так как в любом из $k$ разрядов цифру 1 содержит не более чем одно число из набора
$($b_{1}, \cdots , b_{n}$)$,
то любое подмножество чисел из этого набора однозначно определяется двоичной записью их суммы. Следовательно, различные подмножества из полученного набора имеют различные суммы. Наконец, если для какого-либо значения
$i \in {1; \cdots ;m}$
сложить все числа из набора
$(b_{1}; \cdots ;b_{n})$,
содержащие цифры 1 только в тех разрядах, в которых их содержит число $a_{i}$, то сумма совпадает с этим числом (заметим, что во всех разрядах, в которых некоторое число из этого набора содержит цифру 1, число $a_{i}$ содержит либо только цифры 1, либо только цифры 0). Так как $n < 2^{m}$, то утверждение доказано полностью.
б) Докажем утверждение индукцией по сумме данных чисел $N = a_{1} + \cdots a_{m}$. Если $N=1$, то $m = 1, a_{1} = 1$, и можно положить $b_{1}=1$, Пусть утверждение верно для всех наборов, сумма элементов которых меньше $N$, и $(a_{1}; \cdots ; a_{m})$ - произвольный набор такой, что
$a_{1}+ \cdots a_{m}=N$.
Будем называть набор $(b_{1}; \cdots ; b_{n})$ допустимым для набора $(a_{1}; \cdots ; a_{m})$, если $n \leq m$, все подмножества множества
${b_{1}, \cdots , b_{n}}$
имеют разные суммы чисел, причем среди этих сумм содержатся все числа $a_{1}, \cdots , a_{m}$. Нужно доказать существование хотя бы одного допустимого набора. Если все числа $a_{1}, \cdots , a_{m}$ являются четными, то рассмотрим новый набор $a_{1}^{\prime}, \cdots , a_{m}^{\prime}$, где
$a^{\prime}_{i}=a_{i}/2 (i=1, \cdots , m)$.
так как
$a^{\prime}_{1} + \cdots + a^{\prime}_{m} = N/2 < N$,
то по предположению индукции существует допустимый набор
$(b_{1}^{\prime}; \cdots ;b^{\prime}_{n})$,
Допустимый для нобора
$(a_{1}^{\prime}; \cdots ;a^{\prime}_{m})$.
Тогда набор
$(2a_{1}^{\prime}; \cdots ;2a^{\prime}_{n})$.
будет допустимым для набора
$(2a_{1}^{\prime}; \cdots ;2a^{\prime}_{m})$.
Пусть теперь набор $(a_{1}; \cdots ;a_{m})$ содержит хотя бы одно нечетное число. Рассмотрим наименьшее среди нечетных чисел этого набора. Так как набор $(a_{1}; \cdots ;a_{m})$ не изменится при перенумерации его элементов, то можно считать, что это число равно $a_{m}$. Рассмотрим набор, состоящий из всех чисел вида $a_{i}^{\prime} (i = 1, \cdots, m - 1)$, где
$a^{\prime}_{i}=
\begin{cases}
a_{i}/2,&\text{если a_{i} четно}\\
(a_{i}/a_{m})/2,&\text{ если a_{i} нечетно }
\end{cases}
$
Набор ${a_{i}^{\prime}}$ содержит не более $m-1$ элементов (число его элементов может быть меньше $m -1$, если $a_{i}^{\prime} = a_{j}^{\prime}$ при некоторых $i \neq j$). Заметим, что все элементы $a^{\prime}_{i}$ - натуральные числа. Сумма чисел набора ${a_{i}^{\prime}}$ не превосходит
$a^{\prime}_{1}+ \cdots + a^{\prime}_{m-1} \leq \frac{a_{1}}{2} + \cdots + \frac{a_{m-1}}{2} \leq a_{1} + \cdots + a_{m-1} < N$.
Поэтому к нему применимо предположение индукции, согласно которому существует набор $(b^{\prime}_{1}; \cdots ; b^{\prime}_{k})$, допустимый для набора ${a^{\prime}_{i}}$. Докажем, что набор
$(b_{1}; \cdots ;b_{k+1})$,
где $b_{i}=2b_{i}^{\prime}$ при $i = 1, \cdots k$ и $b_{k+1} = a_{m}$ является допустимым для набора
$(a_{1}; \cdots ;a_{n})$,
Количество элементов набора $(b_{1}; \cdots ;b^{k+1})$ не превосходит $k + 1 \leq m-1+1 = m$. Далее, заметим, что $b_{k+1}$ - единственное нечетное число в наборе ($b_{1}; \cdots ; b_{k+})$. Все подмножества набора
$(b_{1}; \cdots; b_{k+1})$
имеют разные суммы чисел. Действительно, пусть суммы чисел каких-либо двух подмножеств одинаковы. Если они равны четному числу, то оба этих подмножества не содержат элемента $b_{k+1}$, и, разделив все элементы этих подмножеств на 2, мы получим два подмножества множества
$(b_{1}^{\prime}; \cdots ;b_{k}^{\prime})$,
имеющих одинаковые суммы чисел, что противоречит допустимости набора
$(b_{1}^{\prime}; \cdots ;b_{k}^{\prime})$.
Если же суммы чисел двух подмножеств набора
$(b_{1}; \cdots; b_{k+1})$
равны нечетному числу, то оба этих подмножества содержат элемент $b_{k+1}$, и, удалив его из этих подмножеств, мы получим два подмножества набора
$(b_{1}; \cdots; b_{k})$
с одинаковой четной суммой чисел, т. е. придем к уже разобранному случаю. Остается проверить, что каждое число $a_{i} (1 \leq i \leq m)$ представимо в виде суммы различных элементов набора
$(b_{1}; \cdots; b_{k})$
Число $a_{m}$ само является элементом этого набора. Если $i < m$ и $a_{i}$ четно, то
$a_{i}/2 = a_{i}^{\prime} = b^{\prime}_{l}+ \cdots + b^{\prime}_{p}$
для некоторых элементов $b^{\prime}_{l}+ \cdots + b^{\prime}_{p}$ из набора
$b^{\prime}_{1}+ \cdots + b^{\prime}_{k}$.
Поэтому
$a_{i}=2b^{\prime}_{l} + \cdots + 2 b^{\prime}_{p} = b_{l} + \cdots + b_{p}$
Если же $i < m$ и $a_{i}$ нечетно, то
$a_{i} = a_{m} + 2a^{\prime}_{i} = b_{k+1} + 2 (b_{l} + \cdots + b_{p}) = b_{k+1} + b_{l} + \cdots + b_{p}$
для некоторых элементов $b_{l}, \cdots b_{p}$ из набора
$(b_{1}; \cdots ; b_{k})$.
Утверждение задачи доказано.
Доказать, что для любых чисел $a_{1}, \cdots, a_{m} \in \mathbf{N}$:
а) существует такой набор из $n < 2^{m}$ чисел, в котором все подмножества имеют разные суммы чисел, причем среди этих сумм содержатся все числа
$a_{1}, \cdots , a_{m}$;
б) существует такой набор из $n \leq m$ чисел, в котором все подмножества имеют разные суммы чисел, причем среди этих сумм содержатся все числа $a_{1}, \cdots , a_{m}$.
Решение:
а) Рассмотрим двоичные записи чисел $a_{1}, \cdots , a_{m}$ и дополним некоторые из них спереди цифрами 0 так, чтобы все записи имели равную длину $k$. Образуем прямоугольную таблицу размером $m \times k$ из нулей и единиц, в которой для каждого значения $i = 1, \cdots , m$ i-я строка представляет собой полученную выше запись числа $a_{i}$. Поскольку каждый столбец этой таблицы состоит из $m$ цифр, то число $n$ различных ненулевых столбцов в ней не превосходит $2^{m} – 1$. Каждому из этих $n$ столбцов поставим в соответствие число, двоичная запись которого содержит цифру 1 в тех и только тех разрядах, в которых таблица содержит столбцы, совпадающие с данным. Полученный набор чисел $b_{1}, \cdots , b_{n}$ удовлетворяет условию задачи. Действительно, так как в любом из $k$ разрядов цифру 1 содержит не более чем одно число из набора
$($b_{1}, \cdots , b_{n}$)$,
то любое подмножество чисел из этого набора однозначно определяется двоичной записью их суммы. Следовательно, различные подмножества из полученного набора имеют различные суммы. Наконец, если для какого-либо значения
$i \in {1; \cdots ;m}$
сложить все числа из набора
$(b_{1}; \cdots ;b_{n})$,
содержащие цифры 1 только в тех разрядах, в которых их содержит число $a_{i}$, то сумма совпадает с этим числом (заметим, что во всех разрядах, в которых некоторое число из этого набора содержит цифру 1, число $a_{i}$ содержит либо только цифры 1, либо только цифры 0). Так как $n < 2^{m}$, то утверждение доказано полностью.
б) Докажем утверждение индукцией по сумме данных чисел $N = a_{1} + \cdots a_{m}$. Если $N=1$, то $m = 1, a_{1} = 1$, и можно положить $b_{1}=1$, Пусть утверждение верно для всех наборов, сумма элементов которых меньше $N$, и $(a_{1}; \cdots ; a_{m})$ - произвольный набор такой, что
$a_{1}+ \cdots a_{m}=N$.
Будем называть набор $(b_{1}; \cdots ; b_{n})$ допустимым для набора $(a_{1}; \cdots ; a_{m})$, если $n \leq m$, все подмножества множества
${b_{1}, \cdots , b_{n}}$
имеют разные суммы чисел, причем среди этих сумм содержатся все числа $a_{1}, \cdots , a_{m}$. Нужно доказать существование хотя бы одного допустимого набора. Если все числа $a_{1}, \cdots , a_{m}$ являются четными, то рассмотрим новый набор $a_{1}^{\prime}, \cdots , a_{m}^{\prime}$, где
$a^{\prime}_{i}=a_{i}/2 (i=1, \cdots , m)$.
так как
$a^{\prime}_{1} + \cdots + a^{\prime}_{m} = N/2 < N$,
то по предположению индукции существует допустимый набор
$(b_{1}^{\prime}; \cdots ;b^{\prime}_{n})$,
Допустимый для нобора
$(a_{1}^{\prime}; \cdots ;a^{\prime}_{m})$.
Тогда набор
$(2a_{1}^{\prime}; \cdots ;2a^{\prime}_{n})$.
будет допустимым для набора
$(2a_{1}^{\prime}; \cdots ;2a^{\prime}_{m})$.
Пусть теперь набор $(a_{1}; \cdots ;a_{m})$ содержит хотя бы одно нечетное число. Рассмотрим наименьшее среди нечетных чисел этого набора. Так как набор $(a_{1}; \cdots ;a_{m})$ не изменится при перенумерации его элементов, то можно считать, что это число равно $a_{m}$. Рассмотрим набор, состоящий из всех чисел вида $a_{i}^{\prime} (i = 1, \cdots, m - 1)$, где
$a^{\prime}_{i}=
\begin{cases}
a_{i}/2,&\text{если a_{i} четно}\\
(a_{i}/a_{m})/2,&\text{ если a_{i} нечетно }
\end{cases}
$
Набор ${a_{i}^{\prime}}$ содержит не более $m-1$ элементов (число его элементов может быть меньше $m -1$, если $a_{i}^{\prime} = a_{j}^{\prime}$ при некоторых $i \neq j$). Заметим, что все элементы $a^{\prime}_{i}$ - натуральные числа. Сумма чисел набора ${a_{i}^{\prime}}$ не превосходит
$a^{\prime}_{1}+ \cdots + a^{\prime}_{m-1} \leq \frac{a_{1}}{2} + \cdots + \frac{a_{m-1}}{2} \leq a_{1} + \cdots + a_{m-1} < N$.
Поэтому к нему применимо предположение индукции, согласно которому существует набор $(b^{\prime}_{1}; \cdots ; b^{\prime}_{k})$, допустимый для набора ${a^{\prime}_{i}}$. Докажем, что набор
$(b_{1}; \cdots ;b_{k+1})$,
где $b_{i}=2b_{i}^{\prime}$ при $i = 1, \cdots k$ и $b_{k+1} = a_{m}$ является допустимым для набора
$(a_{1}; \cdots ;a_{n})$,
Количество элементов набора $(b_{1}; \cdots ;b^{k+1})$ не превосходит $k + 1 \leq m-1+1 = m$. Далее, заметим, что $b_{k+1}$ - единственное нечетное число в наборе ($b_{1}; \cdots ; b_{k+})$. Все подмножества набора
$(b_{1}; \cdots; b_{k+1})$
имеют разные суммы чисел. Действительно, пусть суммы чисел каких-либо двух подмножеств одинаковы. Если они равны четному числу, то оба этих подмножества не содержат элемента $b_{k+1}$, и, разделив все элементы этих подмножеств на 2, мы получим два подмножества множества
$(b_{1}^{\prime}; \cdots ;b_{k}^{\prime})$,
имеющих одинаковые суммы чисел, что противоречит допустимости набора
$(b_{1}^{\prime}; \cdots ;b_{k}^{\prime})$.
Если же суммы чисел двух подмножеств набора
$(b_{1}; \cdots; b_{k+1})$
равны нечетному числу, то оба этих подмножества содержат элемент $b_{k+1}$, и, удалив его из этих подмножеств, мы получим два подмножества набора
$(b_{1}; \cdots; b_{k})$
с одинаковой четной суммой чисел, т. е. придем к уже разобранному случаю. Остается проверить, что каждое число $a_{i} (1 \leq i \leq m)$ представимо в виде суммы различных элементов набора
$(b_{1}; \cdots; b_{k})$
Число $a_{m}$ само является элементом этого набора. Если $i < m$ и $a_{i}$ четно, то
$a_{i}/2 = a_{i}^{\prime} = b^{\prime}_{l}+ \cdots + b^{\prime}_{p}$
для некоторых элементов $b^{\prime}_{l}+ \cdots + b^{\prime}_{p}$ из набора
$b^{\prime}_{1}+ \cdots + b^{\prime}_{k}$.
Поэтому
$a_{i}=2b^{\prime}_{l} + \cdots + 2 b^{\prime}_{p} = b_{l} + \cdots + b_{p}$
Если же $i < m$ и $a_{i}$ нечетно, то
$a_{i} = a_{m} + 2a^{\prime}_{i} = b_{k+1} + 2 (b_{l} + \cdots + b_{p}) = b_{k+1} + b_{l} + \cdots + b_{p}$
для некоторых элементов $b_{l}, \cdots b_{p}$ из набора
$(b_{1}; \cdots ; b_{k})$.
Утверждение задачи доказано.
