Республиканская олимпиада по математике, 2007 год, 9 класс

Имеется 300 яблок, любые два из которых различаются по весу не более, чем в три раза. Докажите, что их можно разложить в пакеты по четыре яблока так, чтобы любые два пакета различались по весу не более, чем в полтора раза.

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

Покажем алгоритм как распределить яблоки по группам и объясним почему после такого распределения вес в группах будет отличаться не более чем в $1.5$ раза. Сначала упорядочим все яблок по возрастанию, пусть $a_{i}$ вес {i} яблока и $a_{1} \leq a_{2} \leq ..... \leq a_{300}$. Тогда рассмотрим $150$ групп яблок $b_{1},b_{2},....,b_{150}$, где $b_{i}=a_{i}+a_{301-i}, 1 \leq i \leq 150$. Пусть $c_{1}, c_{2},....,c_{150}$ упорядоченный набор $b_{1},b_{2},....,b_{150}$, тогда $c_{1} \leq c_{2} \leq ..... \leq c_{150}$. Затем получим наборы $d_{1},d_{2},....,d_{75}$, где $d_{i}=c_{i}+c_{151-i}, 1 \leq i \leq 70$ и каждый $d_{j}$ содержит $4$ яблока. Покажем теперь это наборы $d_{1},d_{2},....,d_{75}$ удовлетворяют условию задачи. Сначала покажем что наборы $b$ отличаются не более чем в два раза. Пусть $1 \leq n < m \leq 150$, и пусть $b_{m} > b_{n}$. Тогда $b_{m}-b_{n}=a_{m}+a_{301-m}-a_{n}-a_{301-n}=(a_{m}-a_{n})+(a_{301-m}-a_{301-n}) \leq 2a_{1}$ так как $a_{301-m} \leq a_{301-n}, a_{1} \leq a_{n} \leq a_{m} \leq 3a_{1}$. Также $b_{n}=a_{n}+a_{301-n} \geq 2a_{1}$, тогда $2b_{n} \geq b_{m}$, то есть наборы $b$ различаются не более чем в два раза. Случай если $b_{m} < b_{n}$ полностью аналогичен. Теперь применяя аналогичные рассуждения для наборов $d$ получаем что наборы различаются по весу не более чем в два раза. Значит существует разложение всех яблок в пакеты по $4$ так, чтобы два пакета различались по весу не более чем в полтора раза.

всерос окружной этап 97 год 9 класс 3 задача

Возьмем первый пакет с яблоками весом $a_1,a_2,a_3,a_4$ и второй пакет с яблоками весом $b_1,b_2,b_3,b_4$

Возьмем их такими что $a_4\geq b_4\geq b_3\geq b_2\geq a_3\geq b_1\geq a_2\geq a_1$

Значит:

(1) $2b_4+2b_3\geq 4a_1\geq a_4+a_1$

(2)$2a_3+2a_2\geq 3a_2+a_3\geq b_2+b_1$

Отсюда:

(1)

$1,5b_1+1,5b_2+1,5b_3+1,5b_4\geq 2b_4+2b_3+b_2+b_1\geq a_1+a_2+a_3+a_4$

(2) $1,5a_1+1,5a_2+1,5a_3+1,5a_4\geq a_4+2b_3+2a_2+a_1\geq b_1+b_2+b_3+b_4$