|
|
 |
Условие
В 100 ящиках лежат яблоки, апельсины и бананы. Докажите, что можно так выбрать 51 ящик, что в них окажется не менее половины всех яблок, не менее половины всех апельсинов и не менее половины всех бананов.
Решение
Лемма. Любые 2n пар положительных чисел (ai, bi) можно так разбить на две группы по n пар в каждой, что сумма ai в первой группе отличается от суммы ai во второй группе не более, чем на максимальное ai, и сумма bi в первой группе отличается от суммы bi во второй группе не более, чем на максимальное bi.
Доказательство. Упорядочим пары по убыванию ai. Назовём пары с номерами 2i – 1 и 2i двойкой. Заметим, что если разбить пары на две группы так, что пары каждой двойки попадут в разные группы, то разность сумм ai в группах
(a1 – a2) + (a3 – a4) + ... + (a2n–1 – a2n) ≤ a1.
Распределим пары по группам с соблюдением указанного условия. Пусть еще не получилось требуемого разбиения, причём в первой группе сумма bi больше, чем во второй. Тогда в какой-то из двоек bi, попавшее в первую группу, больше bj, попавшего во вторую. Поменяв пары, принадлежащие этой двойке, местами, мы получим, что разность сумм bi уменьшилась по модулю, поскольку изменилась не более, чем на 2b1. Такой процесс не может продолжаться бесконечно, поэтому когда-нибудь распределение станет требуемым.
Выберем из наших ящиков тот, что содержит наибольшее количество апельсинов, а затем из оставшихся – тот, что содержит наибольшее количество яблок. Оставшиеся ящики согласно лемме можно разбить на две группы по 49 ящиков так, что разность количества апельсинов в первой и второй группах не превосходит числа апельсинов в первом ящике, и разность числа яблок в первой и второй группах не превосходит числа яблок во втором ящике. Добавим эти два ящика в ту группу, где не меньше бананов. Полученный набор из 51 ящика удовлетворяет условиям задачи.
Замечания
Ср. с задачей 110198.
