Олимпиадная задача по комбинаторике: равные суммы подмножеств для 117 чисел
Задача
Докажите, что в любом множестве, состоящем из 117 попарно различных трёхзначных чисел, можно выбрать четыре попарно непересекающихся подмножества, суммы чисел в которых равны.
Решение
Покажем, что среди произвольных 106 трехзначных чисел существуют даже четыре непересекающиеся пары с равными суммами.
Из 106 чисел можно образовать 106·105 : 2 = 5460 пар, сумма чисел в каждой паре лежит между 200 и 2000. Если пар с каждой суммой не более трёх, то всего пар не более 1800·3 = 5400, что не так.
Следовательно, у каких-то четырёх пар суммы совпадают. Пары, для которых совпадают суммы, не могут пересекаться: если x + y = x + z, то y = z, и пары совпадают.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет