Отзывы пользователей

В 100 ящиках лежат яблоки, апельсины и бананы. Докажите, что можно так выбрать 51 ящик, что в них окажется не менее половины всех яблок, не менее половины всех апельсинов и не менее половины всех бананов

В 100 ящиках лежат яблоки, апельсины и бананы. Докажите, что можно так выбрать 51 ящик, что в них окажется не менее половины всех яблок, не менее половины всех апельсинов и не менее половины всех бананов.

Решение

Лемма. Любые 2n пар положительных чисел (ai,bi) можно так разбить на две группы по n пар в каждой, что сумма ai в первой группе отличается от суммы ai во второй группе не более, чем на максимальное ai , и сумма bi в первой группе отличается от суммы bi во второй группе не более, чем на максимальное bi.

  1. Докажем утверждение по индукции. База n=0 очевидна. Теперь докажем переход.

    Возьмем из 2n+2 пар две, в которых максимальны ai . Пусть это (a1,b1) и (a2,b2) ( a1 a2 ). Тогда оставшиеся пары можно разбить на две группы по n пар так, что выполняются условия леммы. Обозначим через a и a' суммы чисел ai в группах, а через b и b' – суммы bi . Тогда |a-a'| a2 (так как максимальное ai из оставшихся не превосходит a2 ) и |b-b'| bi .

    Без ограничения общности можно считать, что b b' . Пусть b1 b2 . Тогда добавим первую пару во вторую группу, а вторую пару в первую группу.
    Тогда суммы ai в группах стали равны a+a2 и a'+a1 , причем |(a+a2)-(a'+a1)| |a-a'|+|a2-a1| a2+a1-a2= ai ; суммы же bi в группах стали равны b+b2 и b'+b1 , причем |(b+b2)-(b'+b1)| (b'-b,b2-b1) bi , так как b2-b1 и b-b' разных знаков. Поэтому данное разбиение разбиение удовлетворяет условиям леммы.

    Если же b1 b2, то, добавив первую пару к первой группе, а вторую – ко второй, аналогично будем иметь |(b+b2)-(b'+b1)| bi и |(a+a2)-(a'+a1)| a1 . Лемма доказана.

  2. Упорядочим пары по убыванию ai (т.е. a1 ... a2n ). Назовем пары с номерами 2i-1 и 2i двойкой. Заметим, что если разбить пары на две группы так, что пары любой двойки попадут в разные группы, то разность ai в группах не будет превосходить (a1-a2)+(a3-a4)+...+(a2n-1-a2n) a1.

    Распределим двойки по группам произвольным образом. Пусть еще не получилось требуемого разбиения, причем в первой группе сумма bi больше, чем во второй. Тогда в какой-то из двоек bi , попавшее в первую группу, больше bj , попавшего во вторую. Поменяв пары, принадлежащие этой двойке, местами, мы получим, что разность сумм bi уменьшилась по модулю, поскольку изменилась не более, чем на 2b1 . Тогда такой процесс не может продолжаться бесконечно, поэтому когда-нибудь распределение станет требуемым.
Перейдем к решению задачи.
Выберем из наших коробок ту, что содержит наибольшее количество апельсинов, а затем из оставшихся ту, что содержит наибольшее количество яблок. Тогда оставшиеся коробки согласно лемме можно разбить на две группы по 49 ящиков так, что разность количества апельсинов в первой и второй группах не превосходит числа апельсинов в первой коробке, и разность числа яблок в первой и второй группах не превосходит числа яблок во второй коробке.

Но тогда добавим эти две коробки в ту группу, где не меньше бананов.
Очевидно, полученный набор из 51 коробки удовлетворяет условиям задачи, что и требовалось.
 
Поделиться: