Лучше — поровну

23

Лучше — поровну

В различных задачах анализа и прикладной математики возникают вопросы такого типа:

Пусть данные два числа v и p: 0 < v < p. Расматривают всевозможные (конечные) наборы чисел $x_1, x_2, ..., x_k$ такие, что 0 < x_i ≤ v для любого i = 1, 2, …, k и сумма $\sum_{i=1}^{k} x_i$ всех чисел набора больше p.

Для каждого такого набора существует такое число D, что 1) сумма S неокторы чисел набора (может быть, в частности, всех) отличается от p на D: |S−p| = D и 2) любая другие сумма неокторы чисел набора отличается от p больше, чем на D.

Для каждого набора этого число D («порешность приближения») будет наиболее?

Как мы увидим, искомым будет набор из одинаковых чисел: «лучше — поровну».

Здесь мы рассмотрим несколько конкретных задач (в том числе — трудную задачу M583 из Задачника «Кванта») указаанного типа.

1. Расматривают наборы камней, масса каждого из которых не больше 2 кг, а общая масса набора — больше 10 кг. Из такого набора выбирается несколько камней, суммарная масса которых отличается от 10 кг на нашемшее возможное для данного набора число D. Какое наиболее значение может принимать число D для всего возможных наборов камней?

(Эта задача predлагалась на Московской городской математической оптимизации в 1979 году.)

Понятоно, что число D для любого набора камней не превысит 2 кг, так как масса любого камня не больше 2 кг. Кроме того, очень много D не может быть равным 2 кг. Поэтому, чтобы использовать с наборами, все камни в которых одинаковы, заменаем, что наиболее D получается в том случае, когда камни все же достаточно тяжелы, а до 10 кг недостатетровно полкамня. Четыре камня отличаются от 10 кг больше, чем на 2 кг, а для пятки камней из уравнения 5x = 10−x/2 находится x = 20/11, то есть D = 10/11.

Докажем теперь, что для любого набора D не превышает 10/11, то есть показем, что из произвольного набора камней можно выбрать несколько, суммарная масса которых отличается от 10 кг не больше, чем на 10/11.

Будем отбирать камни по очереди: сначала возьмем самый тяжелый, затем самый тяжелый из остальных, и так до тех пор, пока масса выбранных камней не превышает 10 кг. Если среди выбранных есть камень, весящей меньше 20/11 кг, то либо их общая масса меньше (10+10/11) кг, либо на предыдущем шаге (перед тем, как был взят последний камень) мы имеем набор с массой, больше (10−10/11) кг (=10+10/11−20/11), но меньше или равной 10 кг.

Итак, наиболее значение D равно 10/11, причем это значение достигается на наборе из одинаковых камней.

Уражение 1. Покажите, что и в общем случае наиболее значение D достигается на наборе из одинаковых камней, причем это значение равно p/(1−2·[1/2−p/v]) ([x] — это целая часть числа x).

2. Решим теперь задачу M583 из Задачника «Кванта». Она отличается от задачи 1 одним дополнительным ограничением, значительное увеличение: известно, что общая масса набора — 50 кг.

Мы уже знаем, что D не превышает 10/11. Однако в данной случае

24

эта оценка не является точной, так как число 50 не делится на 20/11 (если бы суммарная масса набора равная не 50, а скажем, 100 кг, то ответ остался бы прежим).

Рассматривая всевозможные разбиения 50 кг на камни с равными массами, убеждаемся в том, что набольшее значение $D$ для таких наборов равно $D_0 = 20/27$ кг. (Оно достигается на наборе из 27 камней массы 50/27.) Наша цель — докаазать, что $D_0$ — это и есть исключное набольшее значение $D$. Для этого достаточно показать, что произвольный набор можно заменить набором из камней одинаковой массы, не уменьшив при этом $D$ (введ $D$ для наборов одинаковых камней не превыходит $D_0$).

Рассмотрим произвольный набор. Выберем из него те камни, суммарная масса которых отличается от 10 кг на наименьшее возможное число (то есть на $D$). Разобем камни с массой, большей $2D_0$, на две группы. К первой группе относят те из них, которые входит в число выбранных (пуст $a_1$, $a_2$, …, $a_m$ их массы). Ко второй группе относят камни с массами $b_1$, $b_2$, …, $b_n$ (большими $2D_0$), не входящее в число выбранных. Для краткости мы будем иногда писать «камень $a_i$» (соответствие $b_j$), имея в виду «камень, масса которого равна $a_i$» (соответствие $b_j$). Пусть $A$ — это сумма масс камней $a_i$ (иногда $A$ будет обозначать множество, состоящее из камней $a_1$, $a_2$, …, $a_m$; определяемые далее суммы масс $B$ и $C$ тоже могут быть использованы для обозначения соответствующих множества), $B$ — сумма масс камней $b_i$, а $C$ — сумма масс оставшихся камней (то есть тех, масса которых не превыходит $2D_0$).

Показем теперь, что существует набор, для которого $a_1 = a_2 = ... = a_m = b_1 = ... = b_n$, $C = 0$, а значение $D$ не меньше, чем у исходного. Это и будет означает, что $D \leq D_0$, так как для наборов, состоящих из одинаковых камней, $D$ не превыходит $D_0$. При этом возможно два случая:

1. Суммарная масса выбранных камней равна 10—D.

Для построения нужного набора нам придется доказать несколько вспомогательных утверждений.

Лемма 1. Все камни, входящие в $C$, принадлежат к числу выбранных (то есть $10—D = A+C$).

Действительно, если хотя бы один из камней, входящих в $C$, не выбран, то, добавив его к выбранным, мы получим несколько камней, масса которых отличается от 10 кг не более чем на $2D_0—D<D$. А это противоречит выбору рассматриемого набора.

Лемма 2. $a_i \geq b_j$ при любых $i$ и $j$ ($1 \leq i \leq m$, $1 \leq j \leq n$).

Действительно, если бы каких-то $i$ и $j$ выполнялись неравенство $a_i < b_j$, то, добавив его к выбранным, мы получим несколько камней, масса которых отличается от 10 кг не более чем на $2D_0—D<D$. А это противоречит оптимальности выбранного набора.

Лемма 3. $b_j > C+2D_0$ при любом $j$ ($1 \leq j \leq n$).

Удалим из выбранного набора все камни, входящие в $C$, и добавим туда камень $b_j$. Если $A+b_j \leq 10—D$, то, добавляя по одному камни из $C$, мы в какой-то момент получим набор, масса которого больше 10—D (так как $A+b_j+C > A+C=10—D$), но меньше 10+D (так как каждый раз добавляется камень с массой, не превышает $2D_0<2D$). Значит, $A+b_j>10—D$, а потому (в силу минимности $D$) $A+b_j>10+D=A+C+2D>A+C+2D_0$, откуда $b_j>C+2D_0$.

Из леммы 2 следует, что и $a_i>C+2D_0$ при всех $i$.

Лемма 4. Если сумма масс $k$ камней из $A$ и $l$ камней из $B$ меньше 10+D, то $k+l \leq m$.

Если эта сумма меньше 10+D, то она в силу минимности $D$ меньше или равна 10—D. Пусть $k+l > m$. Заменяя по очереди камни $b_j$ в этой сумме не входящими в нее камнями $a_i$, мы в конце концов положим последний из камней $a_i$ и доведем таким образом сумму до величины $A+b_j+...>A+C+2D_0>10+D_0$ (см. леммы 1 и 3). Поскольку каждый

25

раз мы добавляли камень с массой не больше чем $2D_0$ ($a_i - b_j < 2D_0$), в какой-то момент эта сумма будет находиться строго между $10 - D$ и $10 + D$. Противоречие.

Докажем, наконец, что можно построить набор, состоящий из камней одинаковой массы, не уменьшив $D$.

Заменим каждый из камней $a_i$ ($i = 1, \dots, m$) камнем с массой $a = A/m$, каждый из камней $b_j$ ($j = 1, \dots, n$) камнем с массой $b = B/n$, а камни из $C$ оставим без изменения. Покажем, что для такого набора число $D$ не уменьшилось.

Допустим, что $D$ уменьшилось. Тогда при некоторых $k$, $l$ и $C' < C$ сумма $ka + lb + C'$ лежит строго между $10 - D$ и $10 + D$. Возьмем $k$ самых легких камней из $A$. Сумма их масс не превыходит $ka$ (почему?). Аналогично сумма масс $l$ самых легких камней из $B$ не превыходит $lb$. Но $ka + lb < 10 + D$, поэтому $k + l \leq m$ (см. лемму 4). В таком случае $10 - D = A + C = ma + C \geq ka + la + C' \geq ka + lb + C' > 10 - D$. Противоречие.

Если $a > b$, то $b$ не может входить ни в одну сумму, даошую $10 - D$ (заменив $b$ на $a$, получим противоречие). Поэтому мы можем читать (придайте точный смысл этим словам!) уменьшить все камни массы $a$, читучить уведомить при этом камни массы $b$, так чтобы $C$ оставалось неизменным. В результате этого у нас получится набор, имеющий больше значения $D$, чем исходный. Проделав так несколько раз, мы получим набор, у которого $a = b$.

Если в этом наборе $C > 0$, увеличим $a$ (число камней с массой $a$ равно $m + n$) на $\varepsilon$, где $\varepsilon < C/(m + n)$; при этом $C$ уменьшится на $(m + n)\varepsilon$. Но тогда $D$ увеличится на $n \cdot \varepsilon$, что и требуется. После нескольких шагов мы получим набор, у которого $a = b$ и $C = 0$.

Случай I разобран полностью.

II. Суммарная масса выбранных камней равна $10 + D$.

Этот случай можно рассматривать примерно так же. Но проще заметить, что если выбранные камни докот налучшее приближение (для данного набора) к 10 с и збыть коМ, то остальные камни набора дают налучшее приближение с недостатком к 50—10 (то есть к 40 кг в нашей задаче). Так как $D_0$ по-прежнему не меньше 2/4 кг (это единственное дополнительное условие, которое было использовано при рассмотрении случая I), все доказанные утверждения остаются в силу после замены 10 на 40.

Итак, задача решения. Найбольшее возможное значение $D$ оказывается $D_0 = 20/27$ кг.

Заметим, что наш рассужждение позволяет решить следующую общую задачу: найти максимум наименьших отклонений от $p$ по всезозможным наборам камней с массой, не превыходящей $v$, и суммарной массой $P$. Мы доказали, что если существует набор, для которого $D > v/4$, то максимальное значение $D$ надо искать среди наборов одинаковых камней.

Упражнения

2. Докажите, что при $v = 2$ кг, $p = 10$ кг, $P \geq 24$ кг существует набор, для которого $D \geq v/4$.

3. Доведите до конца решения задачи в общем случае.

Вот еще одна задача на эту тему: имеется несколько которых не больше 1 т, а их общая масса равна 10 т; на каком наименьшем количество трехтонок наверняка можно увеличти эти ящики?

Решить эту задачу (и ее обобщение) вам помогут следующие упражнения (первые два из них напоминают уже рассмотренные задачи):

4. Пусть единственный ограничением на суммарную массу ящиков является условие $P > 3$ т. Какой наиболее груз $\Gamma$ можно наверняка увеличти на одной трехтонике?

5. Каким будет ответ в предыдущей задаче, если известно, что $P = 10$ т?

6. Пусть теперь масса каждого ящика не превышает $v$, суммарная масса равна $P$ и в нашем распоряжении есть машина грузоподъемностью $p$. Пусть $\Gamma$ — масса максимального груза, который нам удался погрузить на машину. Докажите, что наименьшее значение $\Gamma$ достигается в случае, когда все ящики имеют одинаковую массу.

7. Каким наименьшим запасом $p$-тонок надо располагать, чтобы наверняка перевести все ящики из упражнения 6?

Попытайте найти возможность теорем, подтверждаюших принцип «лучше — поровну».