Олимпиадная задача: принцип крайнего и инварианты в задаче про ящики с фруктами для 9-11 классов

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

  Доказательство. Упорядочим пары по убыванию a_i. Назовём пары с номерами  2i – 1  и 2i двойкой. Заметим, что если разбить пары на две группы так, что пары каждой двойки попадут в разные группы, то разность сумм a_i  в группах   (a₁ – a₂) + (a₃ – a₄) + ... + (a_2n–1 – a_2n) ≤ a₁.

  Распределим пары по группам с соблюдением указанного условия. Пусть еще не получилось требуемого разбиения, причём в первой группе сумма b_i  больше, чем во второй. Тогда в какой-то из двоек b_i,  попавшее в первую группу, больше b_j,  попавшего во вторую. Поменяв пары, принадлежащие этой двойке, местами, мы получим, что разность сумм b_i  уменьшилась по модулю, поскольку изменилась не более, чем на 2b₁. Такой процесс не может продолжаться бесконечно, поэтому когда-нибудь распределение станет требуемым.   Выберем из наших ящиков тот, что содержит наибольшее количество апельсинов, а затем из оставшихся – тот, что содержит наибольшее количество яблок. Оставшиеся ящики согласно лемме можно разбить на две группы по 49 ящиков так, что разность количества апельсинов в первой и второй группах не превосходит числа апельсинов в первом ящике, и разность числа яблок в первой и второй группах не превосходит числа яблок во втором ящике. Добавим эти два ящика в ту группу, где не меньше бананов. Полученный набор из 51 ящика удовлетворяет условиям задачи.

Ответ задачи отсутствует