Разделы 
Дополнительно
Задача по математике - 1726
2019-01-20 
В 99 ящиках лежат яблоки и апельсины. Докажите, что можно так выбрать 50 ящиков, что в них окажется не менее половины всех яблок и не менее половины всех апельсинов.
Решение:
Первое решение. Пусть $x_i$ - количество яблок в $i$-м ящике. Упорядочим ящики по убыванию количества яблок в них (т. е. $x_1 \geq x_2 \geq \cdots \geq x_{99}$). Достаточно разбить ящики со 2-го по 99-й на две группы по 49 ящиков так, чтобы количество яблок в двух группах различалось не больше, чем на $x_1$. Тогда, выбрав ту из двух групп, в ящиках которой в сумме не меньше апельсинов, чем в другой, и добавив к ней первый ящик, мы получим требуемый выбор 50 ящиков. Приведем два способа разбить 98 ящиков на две группы требуемым образом.
Первый способ. В одну группу поместим ящики $2,4,6,\cdots, 98$, в другую - $3, 5, \cdots, 99$. Тогда в первой группе яблок не меньше, чем во второй, а в первой группе без ящика номер 2 - не больше, чем во второй группе. Значит, разность количества яблок не больше, чем $x_2 \leq x_1$.
Второй способ. Разобьем ящики как угодно. Если количество яблок различается больше, чем на $x^2$, то возьмем в группе, где яблок больше, ящик, где больше всего яблок, и поменяем его местами с ящиком из другой группы, в котором меньше всего яблок (ясно, что в первом яблок больше, чем во втором). При этом количество яблок в группах изменилось на разность каких-то двух ящиков, т. е. не могло случиться, что уже в другой группе яблок больше хотя бы на $x^2$. При этом разность количества яблок в группах уменьшается. Кроме того, возможных разбиений на две группы конечное число. Поэтому, повторяя эту операцию, мы придем к требуемой ситуации.
Второе решение. Допустим, что есть ящик $A$, в котором $x_A$ яблок и $y_A$ апельсинов, и ящик $B$, в котором $x_B < x_A$ яблок и $y_B < y_A$ апельсинов. Тогда заменим их на ящик $A^{\prime}$, в котором $x_A$ яблок, и $y_B$ апельсинов, и ящик $B^{\prime}$, в котором $x_B$ яблок и $y_B$ апельсинов. Заметим, что если мы можем выбрать 50 ящиков из нового набора, то и из старого тоже можем. В самом деле, если из нового набора мы должны взять только один из ящиков $A^{\prime}$ и $B^{\prime}$, то в старом наборе возьмем вместо него ящик $A$, а если в новом наборе мы должны были взять оба ящика $A^{\prime}$ и $B$ - возьмем в старом наборе оба ящика $A$ и $B$.
Легко показать, что конечным числом таких замен мы можем прийти к набору ящиков со следующим свойством: если в ящике $X$ больше яблок, чем в ящике $Y$, то в нем меньше апельсинов, чем в ящике $Y$. Действительно, нетрудно понять, что количество таких пар ($A, B$) при нашей операции уменьшается хотя бы на одну.
Теперь упорядочим ящики по убыванию количества яблок в них. Выберем ящики 1, 3, 5,\cdots, 99. Мы взяли не меньше яблок, чем осталось, поскольку в первом ящике яблок не меньше, чем во втором, в третьем - не меньше, чем в четвертом, и т. д. Аналогично, мы взяли не меньше апельсинов, чем оставили, поскольку в 99-м ящике апельсинов не меньше, чем в 98-м, в 97-м - не меньше, чем в 96-м и т. д.
В 99 ящиках лежат яблоки и апельсины. Докажите, что можно так выбрать 50 ящиков, что в них окажется не менее половины всех яблок и не менее половины всех апельсинов.
Решение:
Первое решение. Пусть $x_i$ - количество яблок в $i$-м ящике. Упорядочим ящики по убыванию количества яблок в них (т. е. $x_1 \geq x_2 \geq \cdots \geq x_{99}$). Достаточно разбить ящики со 2-го по 99-й на две группы по 49 ящиков так, чтобы количество яблок в двух группах различалось не больше, чем на $x_1$. Тогда, выбрав ту из двух групп, в ящиках которой в сумме не меньше апельсинов, чем в другой, и добавив к ней первый ящик, мы получим требуемый выбор 50 ящиков. Приведем два способа разбить 98 ящиков на две группы требуемым образом.
Первый способ. В одну группу поместим ящики $2,4,6,\cdots, 98$, в другую - $3, 5, \cdots, 99$. Тогда в первой группе яблок не меньше, чем во второй, а в первой группе без ящика номер 2 - не больше, чем во второй группе. Значит, разность количества яблок не больше, чем $x_2 \leq x_1$.
Второй способ. Разобьем ящики как угодно. Если количество яблок различается больше, чем на $x^2$, то возьмем в группе, где яблок больше, ящик, где больше всего яблок, и поменяем его местами с ящиком из другой группы, в котором меньше всего яблок (ясно, что в первом яблок больше, чем во втором). При этом количество яблок в группах изменилось на разность каких-то двух ящиков, т. е. не могло случиться, что уже в другой группе яблок больше хотя бы на $x^2$. При этом разность количества яблок в группах уменьшается. Кроме того, возможных разбиений на две группы конечное число. Поэтому, повторяя эту операцию, мы придем к требуемой ситуации.
Второе решение. Допустим, что есть ящик $A$, в котором $x_A$ яблок и $y_A$ апельсинов, и ящик $B$, в котором $x_B < x_A$ яблок и $y_B < y_A$ апельсинов. Тогда заменим их на ящик $A^{\prime}$, в котором $x_A$ яблок, и $y_B$ апельсинов, и ящик $B^{\prime}$, в котором $x_B$ яблок и $y_B$ апельсинов. Заметим, что если мы можем выбрать 50 ящиков из нового набора, то и из старого тоже можем. В самом деле, если из нового набора мы должны взять только один из ящиков $A^{\prime}$ и $B^{\prime}$, то в старом наборе возьмем вместо него ящик $A$, а если в новом наборе мы должны были взять оба ящика $A^{\prime}$ и $B$ - возьмем в старом наборе оба ящика $A$ и $B$.
Легко показать, что конечным числом таких замен мы можем прийти к набору ящиков со следующим свойством: если в ящике $X$ больше яблок, чем в ящике $Y$, то в нем меньше апельсинов, чем в ящике $Y$. Действительно, нетрудно понять, что количество таких пар ($A, B$) при нашей операции уменьшается хотя бы на одну.
Теперь упорядочим ящики по убыванию количества яблок в них. Выберем ящики 1, 3, 5,\cdots, 99. Мы взяли не меньше яблок, чем осталось, поскольку в первом ящике яблок не меньше, чем во втором, в третьем - не меньше, чем в четвертом, и т. д. Аналогично, мы взяли не меньше апельсинов, чем оставили, поскольку в 99-м ящике апельсинов не меньше, чем в 98-м, в 97-м - не меньше, чем в 96-м и т. д.
