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