|
|
 |
Условие
а) В 99 ящиках лежат яблоки и апельсины.
Докажите, что можно так выбрать 50 ящиков, что в них окажется не менее половины всех яблок и не менее половины всех апельсинов.
б) В 100 ящиках лежат яблоки и апельсины.
Докажите, что можно так выбрать 34 ящика, что в них окажется не менее трети всех яблок и не менее трети всех апельсинов.
Решение 1
а) Упорядочим ящики по убыванию количества яблок в них: x1 ≥ x2 ≥ ... ≥ x99. Достаточно разбить ящики со 2-го по 99-й на две группы по 49 ящиков так, чтобы количество яблок в двух группах различалось не больше, чем на x1. Тогда, выбрав ту из двух групп, в ящиках которой в сумме не меньше апельсинов, чем в другой, и добавив к ней первый ящик, мы получим требуемый выбор 50 ящиков.
В одну группу поместим ящики 2, 4, 6, ..., 98, в другую – 3, 5, ..., 99. Тогда в первой группе яблок не меньше, чем во второй, а в первой группе без ящика № 2 – не больше, чем во второй группе. Значит, разность количества яблок не больше, чем x2.
б) В обозначениях решения пункта а) достаточно разбить ящики со 2-го по 100-й на три группы по 33 ящика так, чтобы количество яблок в двух группах различалось не больше, чем на x1. Тогда, выбрав ту из трех групп, в ящиках которой в сумме не меньше апельсинов, чем в любой другой, и добавив к ней первый ящик, мы получим требуемый выбор 34 ящиков.
В одну группу поместим ящики 2, 5, 8, ..., 98, в другую – 3, 6, ..., 99, в третью – 4, 7, ..., 100. Пусть количество яблок в k-й группе равно Ak, тогда
A1 ≥ A2 ≥ A3 ≥ A1 – x2. Значит, разность количеств яблок в группах не превышает x2.
Решение 2
а) Допустим, что есть ящик 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.
Теперь упорядочим ящики по убыванию количества яблок (и возрастанию количества апельсинов) и выберем ящики 1, 4, 7, ..., 100. Мы взяли не меньше трети яблок, поскольку в первом ящике яблок не меньше, чем во втором и в третьем, в четвёртом – не меньше, чем в пятом и в шестом, и т. д. Также мы взяли не меньше трети апельсинов: в 100-м ящике апельсинов не меньше, чем в 98-м и в 97-м, в 96-м – не меньше, чем в 95-м и в 94-м, и т. д.
Замечания
1. Пункт а) предлагался на Всероссийской олимпиаде для 8 классов, пункт б) – для 9 кл.
2. Ср. с задачей 110178.
