Разделы 
Дополнительно
Задача по математике - 1745
2019-01-20 
В 100 ящиках лежат яблоки, апельсины и бананы. Докажите, что можно так выбрать 51 ящик, что в них окажется не менее половины всех яблок, не менее половины всех апельсинов и не менее половины всех бананов.
Решение:
Лемма. Любые $2n$ пар положительных чисел $(a_i,b_i)$ можно так разбить на две группы по $n$ пар в каждой, что сумма $a_i$ в первой группе отличается от суммы $a_i$ во второй группе не более, чем на максимальное $a_i$, и сумма $b_i$ в первой группе отличается от суммы $b_i$ во второй группе не более, чем на максимальное $b_i$.
Доказательство. * 1. Докажем утверждение по индукции. База $n = 0$ очевидна. Теперь докажем переход.
Возьмем из $2n + 2$ пар две, в которых максимальны $a_i$. Пусть это $(a_1,b_1)$ и $(a_2,b_2) (a_1 \geq a_2)$. Тогда оставшиеся пары можно разбить на две группы по $n$ пар так, что выполняются условия леммы. Обозначим через $a$ и $a^{ \prime}$ суммы чисел $a_i$ в группах, а через $b$ и $b^{ \prime}$ - суммы $b_i$. Тогда $|a - a^{ \prime}| \leq a_2$ (так как максимальное $a_i$ из оставшихся не превосходит $a_2$) и $|b - b^{ \prime}| \leq max b_i$. Без ограничения общности можно считать, что $b_1 \leq b^{ \prime}$. Пусть $b_1 \leq b_2$. Тогда добавим первую пару во вторую группу, а вторую пару в первую группу. Тогда суммы $a_i$ в группах стали равны $a + a_2$ и $a^{ \prime} + a_1$, причем $|(a + a_2) - (a^{ \prime} + a_1)| \leq |a - a^{ \prime}| + |a_2 - a_1| \leq a_2 + a_1 - a_2 = max a_i$; суммы же $b_i$ в группах стали равны $b + b_2$ и $b^{ \prime} + b_1$, причем $|(b_1 + b_2) - (b^{ \prime} + b_1)| \leq max(b^{ \prime} - b, b_2 - b_1) \leq max b_i$, так как $b_2 - b_1$ и $b - b^{ \prime}$ разных знаков. Поэтому данное разбиение разбиение удовлетворяет условиям леммы. Если же $b_1 \geq b_2$, то, добавив первую пару к первой группе, а вторую - ко второй, аналогично будем иметь $|(b + b_2) - (b^{ \prime} + b_1)| \leq max b_i и |(a + a_2) - (a^{ \prime} + a_1)| \leq a_1$. Лемма доказана.
Доказательство. * 2. Упорядочим пары по убыванию $a_i (т. е. a_1 \geq \cdots \geq a_{2_n})$. Назовем пары с номерами $2i - 1$ и $2i$ двойкой. Заметим, что если разбить пары на две группы так, что пары любой двойки попадут в разные группы, то разность $a_i$ в группах не будет превосходить $(a_1 - a_2) + (a_3 - a_4) + \cdots + (a_{2n-1} - a_{2n}) \leq a_1$.
Распределим двойки по группам произвольным образом. Пусть еще не получилось требуемого разбиения, причем в первой группе сумма $b_i$ больше, чем во второй. Тогда в какой-то из двоек $b_i$, попавшее в первую группу, больше $b_j$, попавшего во вторую. Поменяв пары, принадлежащие этой двойке, местами, мы получим, что разность сумм $b_i$ уменьшилась по модулю, поскольку изменилась не более, чем на $2b_1$. Тогда такой процесс не может продолжаться бесконечно, поэтому когда-нибудь распределение станет требуемым.
Перейдем к решению задачи. Выберем из наших коробок ту, что содержит наибольшее количество апельсинов, а затем из оставшихся ту, что содержит наибольшее количество яблок. Тогда оставшиеся коробки согласно лемме можно разбить на две группы по 49 ящиков так, что разность количества апельсинов в первой и второй группах не превосходит числа апельсинов в первой коробке, и разность числа яблок в первой и второй группах не превосходит числа яблок во второй коробке. Но тогда добавим эти две коробки в ту группу, где не меньше бананов. Очевидно, полученный набор из 51 коробки удовлетворяет условиям задачи, что и требовалось.
В 100 ящиках лежат яблоки, апельсины и бананы. Докажите, что можно так выбрать 51 ящик, что в них окажется не менее половины всех яблок, не менее половины всех апельсинов и не менее половины всех бананов.
Решение:
Лемма. Любые $2n$ пар положительных чисел $(a_i,b_i)$ можно так разбить на две группы по $n$ пар в каждой, что сумма $a_i$ в первой группе отличается от суммы $a_i$ во второй группе не более, чем на максимальное $a_i$, и сумма $b_i$ в первой группе отличается от суммы $b_i$ во второй группе не более, чем на максимальное $b_i$.
Доказательство. * 1. Докажем утверждение по индукции. База $n = 0$ очевидна. Теперь докажем переход.
Возьмем из $2n + 2$ пар две, в которых максимальны $a_i$. Пусть это $(a_1,b_1)$ и $(a_2,b_2) (a_1 \geq a_2)$. Тогда оставшиеся пары можно разбить на две группы по $n$ пар так, что выполняются условия леммы. Обозначим через $a$ и $a^{ \prime}$ суммы чисел $a_i$ в группах, а через $b$ и $b^{ \prime}$ - суммы $b_i$. Тогда $|a - a^{ \prime}| \leq a_2$ (так как максимальное $a_i$ из оставшихся не превосходит $a_2$) и $|b - b^{ \prime}| \leq max b_i$. Без ограничения общности можно считать, что $b_1 \leq b^{ \prime}$. Пусть $b_1 \leq b_2$. Тогда добавим первую пару во вторую группу, а вторую пару в первую группу. Тогда суммы $a_i$ в группах стали равны $a + a_2$ и $a^{ \prime} + a_1$, причем $|(a + a_2) - (a^{ \prime} + a_1)| \leq |a - a^{ \prime}| + |a_2 - a_1| \leq a_2 + a_1 - a_2 = max a_i$; суммы же $b_i$ в группах стали равны $b + b_2$ и $b^{ \prime} + b_1$, причем $|(b_1 + b_2) - (b^{ \prime} + b_1)| \leq max(b^{ \prime} - b, b_2 - b_1) \leq max b_i$, так как $b_2 - b_1$ и $b - b^{ \prime}$ разных знаков. Поэтому данное разбиение разбиение удовлетворяет условиям леммы. Если же $b_1 \geq b_2$, то, добавив первую пару к первой группе, а вторую - ко второй, аналогично будем иметь $|(b + b_2) - (b^{ \prime} + b_1)| \leq max b_i и |(a + a_2) - (a^{ \prime} + a_1)| \leq a_1$. Лемма доказана.
Доказательство. * 2. Упорядочим пары по убыванию $a_i (т. е. a_1 \geq \cdots \geq a_{2_n})$. Назовем пары с номерами $2i - 1$ и $2i$ двойкой. Заметим, что если разбить пары на две группы так, что пары любой двойки попадут в разные группы, то разность $a_i$ в группах не будет превосходить $(a_1 - a_2) + (a_3 - a_4) + \cdots + (a_{2n-1} - a_{2n}) \leq a_1$.
Распределим двойки по группам произвольным образом. Пусть еще не получилось требуемого разбиения, причем в первой группе сумма $b_i$ больше, чем во второй. Тогда в какой-то из двоек $b_i$, попавшее в первую группу, больше $b_j$, попавшего во вторую. Поменяв пары, принадлежащие этой двойке, местами, мы получим, что разность сумм $b_i$ уменьшилась по модулю, поскольку изменилась не более, чем на $2b_1$. Тогда такой процесс не может продолжаться бесконечно, поэтому когда-нибудь распределение станет требуемым.
Перейдем к решению задачи. Выберем из наших коробок ту, что содержит наибольшее количество апельсинов, а затем из оставшихся ту, что содержит наибольшее количество яблок. Тогда оставшиеся коробки согласно лемме можно разбить на две группы по 49 ящиков так, что разность количества апельсинов в первой и второй группах не превосходит числа апельсинов в первой коробке, и разность числа яблок в первой и второй группах не превосходит числа яблок во второй коробке. Но тогда добавим эти две коробки в ту группу, где не меньше бананов. Очевидно, полученный набор из 51 коробки удовлетворяет условиям задачи, что и требовалось.
