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