Упорядочивание
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Каждая из 
коробок состоит из яблок, груш и апельсинов. Докажите, что можно так выбрать 
коробку что в них суммарно
окажется не менее половины всех яблок, не менее половины всех груш и не менее половины всех апельсинов.
Подсказка 1
Для начала, для того чтобы обеспечить достаточное количество яблок и апельсинов, давайте выберем по одной коробке, содержащей наибольшее возможное количество тех и других. Теперь было бы здорово оставшиеся разделить на группы по 49 коробок так, чтобы при добавлении двух выбранных в каждую из групп, в них оказывалось больше половины яблок и апельсинов. Тогда при добавлении выбранной пары к одной из групп и груш будет оказываться достаточно много.
Подсказка 2
Давайте тогда наши 98 коробок упорядочим по возрастанию количества яблок в них, пары соседних разобьём на пары с номерами 2i-1 и 2i. Теперь любое разбиение, где коробки из каждой из пар попали в различные группы таково, что разность числа яблок в группах не превосходит максимального числа яблок в коробках.
Подсказка 3
Осталось решить вопрос с апельсинами. Вот пусть при каком-то разбиении (в котором из каждой пары коробок ровно одна в первой группе) разность количеств апельсинов в группах слишком велики, давайте решать проблему. Осталось пояснить, как уменьшить разность и почему возможно её уменьшить настолько, насколько нам необходимо.
Выберем из наших коробок ту, что содержит наибольшее количество апельсинов, а затем из оставшихся ту, что содержит наибольшее количество яблок.
Докажем следующий факт: оставшиеся коробки можно разбить на две группы по 49 ящиков так, что разность количества апельсинов в первой и второй группах не превосходит числа апельсинов в первой коробке, и разность числа яблок в первой и второй группах не превосходит числа яблок во второй коробке.
Произвольно занумеруем коробки. Обозначим за 
количество яблок в коробке с номером 
за 
— количество груш в коробке с
номером 
Упорядочим коробки по убыванию яблок 
(т. е. 
Назовем коробки с номерами 
и 
двойкой. Заметим, что
если разбить коробки на две группы так, что пары любой двойки попадут в разные группы, то разность 
в группах не будет
превосходить
Распределим коробки по группам произвольным образом. Пусть еще не получилось требуемого разбиения, причем в первой группе сумма
больше, чем во второй. Тогда в какой-то из двоек 
попавшее в первую группу, больше 
попавшего во вторую. Поменяв коробки,
принадлежащие этой двойке, местами, мы получим, что разность сумм 
уменьшилась по модулю, поскольку изменилась не
более, чем на 
Тогда такой процесс не может продолжаться бесконечно, поэтому когда-нибудь распределение станет
требуемым.
Добавим теперь первые две выбранные коробки в ту группу, где не меньше груш. Очевидно, полученный набор из 
коробки
удовлетворяет условиям задачи, что и требовалось.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
