Упорядочивание

Сперва докажем следующую лемму.

Лемма. В ряд лежат апельсинов, массы любых двух соседних отличаются не более, чем на г. Тогда если упорядочить апельсины по убыванию массы, то массы любых двух соседних снова будут отличаться не более, чем на г.

Доказательство. Действительно, предположим обратное, пусть нашлись два соседних апельсина весами разница весов которых больше г. Это значит, что для любого апельсина весом хотя бы в изначальном ряду возле него апельсины весами хотя бы и для любого апельсина весом не более в изначальном ряду возле него апельсины весами не более Но ряд непрерывен, потому где-то должны лежать рядом апельсины двух видов, противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Тогда разложим апельсины по возрастанию весов. Выложим пакетов в ряд и положим в них сначала по апельсина: в первый пакет — первый и последний апельсин, во второй — второй и предпоследний апельсин и т. д. На каждом шаге добавляются два изменения весов разных знаков, что в сумме делает разность весов соседних пакетов по модулю не больше максимума разностей весов соседних апельсинов, т. е. не более г. Разложим пакеты по возрастанию веса — по-прежнему веса соседних отличаются не более чем на г. Осталось ещё апельсинов в ряду по возрастанию (с -го по -й). Положим самый лёгкий апельсин в самый тяжёлый пакет, следующий — во второй по тяжести и т. д. Как и ранее, веса соседних пакетов будут отличаться не более чем на г.