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