Разделы 
Дополнительно
Задача по математике - 1045
2015-02-17 
Докажите, что из любых десяти различных двузначных натуральных чисел можно выбрать две различные непересекающиеся группы чисел так, что сумма чисел в обеих группах будет одинаковой.
Решение:
Прежде всего замечаем, что требование, чтобы группы были непересекающимися, не является существенным, так как если мы найдем две различные пересекающиеся группы чисел с равными суммами входящих в них чисел, то, отбрасывая общие элементы, мы получим непересекающиеся группы с равными суммами.
Подсчитаем теперь общее число всевозможных различных групп чисел, составленных из 10 данных чисел. Поскольку для каждого из 10 чисел есть две возможности: принадлежать или не принадлежать группе, то всего из 10 чисел можно образовать $2^{10}$ различные группы. Однако при этом мы учли и группу, в которую не попало ни одного числа. Исключив ее, получаем, что общее число различных групп равно $2^{10}-1 = 1023$. Но поскольку каждое число в группе не больше 99, а количество чисел в группе не превосходит 10, то сумма чисел любой группы не больше $99 \cdot 10 = 990$, т.е. различных сумм не больше 990. Значит, среди 1023 групп есть группы с совпадающими суммами.
Докажите, что из любых десяти различных двузначных натуральных чисел можно выбрать две различные непересекающиеся группы чисел так, что сумма чисел в обеих группах будет одинаковой.
Решение:
Прежде всего замечаем, что требование, чтобы группы были непересекающимися, не является существенным, так как если мы найдем две различные пересекающиеся группы чисел с равными суммами входящих в них чисел, то, отбрасывая общие элементы, мы получим непересекающиеся группы с равными суммами.
Подсчитаем теперь общее число всевозможных различных групп чисел, составленных из 10 данных чисел. Поскольку для каждого из 10 чисел есть две возможности: принадлежать или не принадлежать группе, то всего из 10 чисел можно образовать $2^{10}$ различные группы. Однако при этом мы учли и группу, в которую не попало ни одного числа. Исключив ее, получаем, что общее число различных групп равно $2^{10}-1 = 1023$. Но поскольку каждое число в группе не больше 99, а количество чисел в группе не превосходит 10, то сумма чисел любой группы не больше $99 \cdot 10 = 990$, т.е. различных сумм не больше 990. Значит, среди 1023 групп есть группы с совпадающими суммами.
