Районная олимпиада, 2005-2006 учебный год, 9 класс

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

Комментарий/решение

Положим в любых 50 ящиках будет меньше половины всех яблок и апельсинов. Но тогда отбросив любые 50 ящиков можно получить 49 ящиков в которых яблок и апельсинов больше половины, т.е. от прибавления любого ящика к любым 49 ящикам яблок и апельсинов становится меньше - противоречие.

Допустим, что есть ящик A, в котором xA яблок и yA апельсинов, и ящик B, в котором xB < xA яблок и yB < yA апельсинов. Заменим их на ящик A', в котором xA яблок и yB апельсинов, и ящик B', в котором xB яблок и yA апельсинов. Заметим, что если мы можем выбрать 50 ящиков из нового набора, то и из старого тоже можем. В самом деле, если из нового набора мы должны взять только один из ящиков A' и B', то в старом наборе возьмём вместо него ящик A, а если в новом наборе мы должны были взять оба ящика A' и B' – возьмём в старом наборе оба ящика A и B.

Конечным числом таких замен мы можем придти к набору ящиков со следующим свойством: если в ящике X больше яблок, чем в ящике Y, то в нём меньше апельсинов, чем в ящике Y. Действительно, количество "плохих" пар (A, B) при нашей операции уменьшается хотя бы на одну.

Теперь упорядочим ящики по убыванию количества яблок (если в нескольких ящиках яблок поровну, упорядочим эти ящики по возрастанию количества апельсинов). Выберем ящики 1, 3, 5, ..., 99. Мы взяли не меньше яблок, чем осталось, поскольку в первом ящике яблок не меньше, чем во втором, в третьем – не меньше, чем в четвёртом, и т. д. С другой стороны, мы взяли и апельсинов не меньше, чем оставили: в 99-м ящике апельсинов не меньше, чем в 98-м, в 97-м – не меньше, чем в 96-м, и т. д.

б) Как и в пункте а) показываем, что достаточно решить задачу для набора яшиков со следующим свойством: если в ящике X больше яблок, чем в ящике Y, то в нем меньше апельсинов, чем в ящике Y.

Допустим, что есть ящик A, в котором xA яблок и yA апельсинов, и ящик B, в котором xB < xA яблок и yB < yA апельсинов. Заменим их на ящик A', в котором xA яблок и yB апельсинов, и ящик B', в котором xB яблок и yA апельсинов. Заметим, что если мы можем выбрать 50 ящиков из нового набора, то и из старого тоже можем. В самом деле, если из нового набора мы должны взять только один из ящиков A' и B', то в старом наборе возьмём вместо него ящик A, а если в новом наборе мы должны были взять оба ящика A' и B' – возьмём в старом наборе оба ящика A и B.

Конечным числом таких замен мы можем придти к набору ящиков со следующим свойством: если в ящике X больше яблок, чем в ящике Y, то в нём меньше апельсинов, чем в ящике Y. Действительно, количество "плохих" пар (A, B) при нашей операции уменьшается хотя бы на одну.

Теперь упорядочим ящики по убыванию количества яблок (если в нескольких ящиках яблок поровну, упорядочим эти ящики по возрастанию количества апельсинов). Выберем ящики 1, 3, 5, ..., 99. Мы взяли не меньше яблок, чем осталось, поскольку в первом ящике яблок не меньше, чем во втором, в третьем – не меньше, чем в четвёртом, и т. д. С другой стороны, мы взяли и апельсинов не меньше, чем оставили: в 99-м ящике апельсинов не меньше, чем в 98-м, в 97-м – не меньше, чем в 96-м, и т. д.