В различных задачах анализа и прикладной математики возникают вопросы такого типа:
Пусть даны два числа $v$ и $p$: $0\lt v\lt p$. Рассматриваются всевозможные (конечные) наборы чисел $x_1$, $x_2$, $\ldots$, $x_k$ такие, что $0\lt x_i\le v$ для любого $i=1$, $2$, $\ldots$, $k$ и сумма $\sum\limits_{i=1}^kx_i$ всех чисел набора больше $p$.
Для каждого такого набора существует такое число $D$, что
- сумма $S$ некоторых чисел набора (может быть, в частности, всех) отличается от $p$ на $D$: $|S-p|=D$ и
- любая другая сумма некоторых чисел набора отличается от $p$ больше, чем на $D$.
Для какого набора это число $D$ («погрешность приближения») будет наибольшим?
Как мы увидим, искомым будет набор из одинаковых чисел: «лучше — поровну».
Здесь мы рассмотрим несколько конкретных задач (в том числе — трудную задачу М583 из Задачника «Кванта») указанного типа.
1. Рассматриваются наборы камней, масса каждого из которых не больше 2 кг, а общая масса набора — больше 10 кг. Из такого набора выбирается несколько камней, суммарная масса которых отличается от 10 кг на наименьшее возможное для данного набора число $D$. Какое наибольшее значение может принимать число $D$ для всевозможных наборов камней?
(Эта задача предлагалась на Московской городской математической олимпиаде в 1979 году.)
Понятно, что число $D$ для любого такого набора камней не превосходит 2 кг, так как масса любого камня не больше 2 кг. Кроме того, очевидно, что $D$ не может быть равным 2 кг. Поэкспериментировав с наборами, все камни в которых одинаковы, замечаем, что наибольшее $D$ получается в том случае, когда камни всё же достаточно тяжёлы, а до 10 кг недостаёт ровно полкамня. Четыре камня отличаются от 10 кг больше, чем на 2 кг, а для пяти камней из уравнения $5x=10-\dfrac x2$ находим $x=\dfrac{20}{11}$, т. е. $D=\dfrac{10}{11}$.
Докажем теперь, что для любого набора $D$ не превышает $\dfrac{10}{11}$, т. е. покажем, что из произвольного набора камней можно выбрать несколько, суммарная масса которых отличается от 10 кг не больше, чем на $\dfrac{10}{11}$.
Будем отбирать камни по очереди: сначала возьмём самый тяжёлый, затем самый тяжёлый из оставшихся, и так до тех пор, пока масса выбранных камней не превзойдёт 10 кг. Если среди выбранных есть камень, весящий меньше $\dfrac{20}{11}$ кг, то либо их общая масса меньше $\left(10+\dfrac{10}{11}\right)$ кг, либо на предыдущем шаге (перед тем, как был взят последний камень) мы имели набор с массой, большей $\left(10-\dfrac{10}{11}\right)$ кг $\left(=10+\dfrac{10}{11}-\dfrac{20}{11}\right)$, но меньшей или равной 10 кг.
Итак, наибольшее значение $D$ равно $\dfrac{10}{11}$, причём это значение достигается на наборе из одинаковых камней.
Упражнение 1. Покажите, что и в общем случае наибольшее значение $D$ достигается на наборе из одинаковых камней, причём это значение равно $\dfrac{p}{1-2\cdot\left[\dfrac12-\dfrac pv\right]}$ ($[x]$ — это целая часть числа $x$).
2. Решим теперь задачу М583 из Задачника «Кванта». Она отличается от задачи 1 одним дополнительным ограничением, значительно усложняющим решение: известно, что общая масса набора — 50 кг.
Мы уже знаем, что $D$ не превосходит $\dfrac{10}{11}$. Однако в данном случае эта оценка не является точной, так как число 50 не делится нацело на $\dfrac{20}{11}$ (если бы суммарная масса набора равнялась не 50, а, скажем, 100 кг, то ответ остался бы прежним).
Рассматривая всевозможные разбиения 50 кг на камни с равными массами, убеждаемся в том, что наибольшее значение $D$ для таких наборов равно $D_0=\dfrac{20}{27}$ кг. (Оно достигается на наборе из 27 камней массы $\dfrac{50}{27}$.) Наша цель — доказать, что $D_0$ — это и есть искомое наибольшее значение $D$. Для этого достаточно показать, что произвольный набор можно заменить набором из камней одинаковой массы, не уменьшив при этом $D$ (ведь $D$ для наборов одинаковых камней не превосходит $D_0$).
Рассмотрим произвольный набор. Выберем из него те камни, суммарная масса которых отличается от 10 кг на наименьшее возможное число (т. е. на $D$). Разобьём камни с массой, большей $2D_0$, на две группы. К первой группе отнесём те из них, которые входят в число выбранных (пусть $a_1$, $a_2$, $\ldots$, $a_m$ — их массы). Ко второй группе отнесём камни с массами $b_1$, $b_2$, $\ldots$, $b_n$ (большими $2D_0$), не входящие в число выбранных. Для краткости мы будем иногда писать «камень $a_i$» (соответственно «камень $b_j$»), имея в виду «камень, масса которого равна $a_i$» (соответственно $b_j$). Пусть $A$ — это сумма масс камней $a_i$ (иногда $A$ будет обозначать и множество, состоящее из камней $a_1$, $a_2$, $\ldots$, $a_m$; определяемые далее суммы масс $B$ и $C$ тоже могут быть использованы для обозначения соответствующих множеств), $B$ — сумма масс камней $b_i$, а $C$ — сумма масс оставшихся камней (т. е. тех, масса которых не превосходит $2D_0$).
Покажем теперь, что существует набор, для которого $a_1=a_2=\ldots=a_m=b_1=\ldots=b_n$, $C=0$, а значение $D$ не меньше, чем у исходного. Это и будет означать, что $D\le D_0$, так как для наборов, состоящих из одинаковых камней, $D$ не превосходит $D_0$. При этом возможны два случая:
I. Суммарная масса выбранных камней равна $10-D$.
Для построения нужного набора нам придётся доказать несколько вспомогательных утверждений.
Лемма 1. Все камни, входящие в $C$, принадлежат к числу выбранных (т. е. $10-D=A+C$).
Действительно, если хотя бы один из камней, входящих в $C$, не выбран, то, добавив его к выбранным, мы получим несколько камней, масса которых отличается от 10 кг не более чем на $2D_0-D\lt D$. А это противоречит выбору рассматриваемого набора.
Лемма 2. $a_i\ge b_j$ при любых $i$ и $j$ ($1\le i\le m$, $1\le j\le n$).
Действительно, если бы для каких-то $i$ и $j$ выполнялось неравенство $a_i\lt b_j$, то, добавив к выбранным камнём камень $b_j$ и выбросив оттуда камень $a_i$, мы получили бы набор, суммарная масса которого лучше приближается к 10, чем для выбранного (так как из неравенств $b_j\le2$, $a_i\gt2D_0$, $4D_0\ge2$ следует, что $b_j-a_i\lt2D_0$), что противоречит оптимальности выбранного набора.
Лемма 3. $b_j\gt C+2D_0$ при любом $j$ ($1\le j\le n$).
Удалим из выбранного набора все камни, входящие в $C$, и добавим туда камень $b_j$. Если $A+b_j\le10-D$, то, добавляя по одному камни из $C$, мы в какой-то момент получим набор, масса которого больше $10-D$ (так как $A+b_j+C\gt A+C=10-D$), но меньше $10+D$ (так как каждый раз добавляется камень с массой, не превосходящей $2D_0\lt2D$). Значит, $A+b_j\gt10-D$, а потому (в силу минимальности $D$) $A+b_j\gt10+D=A+C+2D\gt A+C+2D_0$, откуда $b_j\gt C+2D_0$.
Из леммы 2 следует, что и $a_i\gt C+2D_0$ при всех $i$.
Лемма 4. Если сумма масс $k$ камней из $A$ и $l$ камней из $B$ меньше $10+D$, то $k+l\le m$.
Если эта сумма меньше $10+D$, то она в силу минимальности $D$ меньше или равна $10-D$. Пусть $k+l\gt m$. Заменяя по очереди камни $b_j$ в этой сумме не входящими в неё камнями $a_i$, мы в конце концов положим последний из камней $a_i$ и доведём таким образом сумму до величины $A+b_j+\ldots\gt A+C+2D_0\gt10+D_0$ (см. леммы 1 и 3). Поскольку каждый раз мы добавляли камень с массой не больше чем $2D_0$ ($a_i-b_j\lt2D_0$), в какой-то момент эта сумма будет находиться строго между $10-D$ и $10+D$. Противоречие.
Докажем, наконец, что можно построить набор, состоящий из камней одинаковой массы, не уменьшив $D$.
Заменим каждый из камней $a_i$ ($i=1$, $\ldots$, $m$) камнем с массой $a=\dfrac Am$, каждый из камней $b_j$ ($j=1$, $\ldots$, $n$) — камнем с массой $b=\dfrac Bn$, а камни из $C$ оставим без изменения. Покажем, что для такого набора число $D$ не уменьшилось.
Допустим, что $D$ уменьшилось. Тогда при некоторых $k$, $l$ и $C'\lt C$ сумма $ka+lb+C'$ лежит строго между $10-D$ и $10+D$. Возьмём $k$ самых лёгких камней из $A$. Сумма их масс не превосходит $ka$ (почему?). Аналогично сумма масс $l$ самых лёгких камней из $B$ не превосходит $lb$. Но $ka+lb\lt10+D$, поэтому $k+l\le m$ (см. лемму 4). В таком случае
$$10-D=A+C=ma+C\gt ka+la+C'\gt ka+lb+C'\gt10-D.$$ Противоречие.
Если $a\gt b$, то $b$ не может входить ни в одну сумму, дающую $10-D$ (заменив $b$ на $a$, получим противоречие). Поэтому мы можем чуть-чуть уменьшить все камни массы $a$, чуть-чуть увеличив при этом камни массы $b$, так чтобы $C$ осталось неизменным. В результате этого у нас получится набор, имеющий большее значение $D$, чем исходный. Проделав так несколько раз, мы получим набор, у которого $a=b$.
Если в этом наборе $C\gt0$, увеличим $a$ (число камней с массой $a$ равно $m+n$) на $\eps$, где $\eps\lt\dfrac C{m+n}$; при этом $C$ уменьшится на $(m+n)\eps$. Но тогда $D$ увеличится на $n\eps$, что и требуется. После нескольких шагов мы получим набор, у которого $a=b$ и $C=0$.
Случай I разобран полностью.
II. Суммарная масса выбранных камней равна $10+D$.
Этот случай можно рассматривать примерно так же. Но проще заметить, что если выбранные камни дают наилучшее приближение (для данного набора) к 10 с избытком, то остальные камни набора дают наилучшее приближение с недостатком к $50-10$ (т. е. к 40 кг в нашей задаче). Так как $D_0$ по-прежнему не меньше $\dfrac24$ кг (это единственное дополнительное условие, которое было использовано при рассмотрении случая I), все доказанные утверждения останутся в силе после замены 10 на 40.
Итак, задача решена. Наибольшее возможное значение $D$ оказалось равным $D_0=\dfrac{20}{27}$ кг.
Заметим, что наши рассуждения позволяют решить следующую общую задачу: найти максимум наименьших отклонений от $p$ по всевозможным наборам камней с массой, не превосходящей $v$, и суммарной массой $P$. Мы доказали, что если существует набор, для которого $D\gt\dfrac v4$, то максимальное значение $D$ надо искать среди наборов одинаковых камней.
Упражнение 2. Докажите, что при $v=2$ кг, $p=10$ кг, $P\gt24$ кг существует набор, для которого $D\gt\dfrac v4$.
Упражнение 3. Доведите до конца решение задачи в общем случае.
Вот ещё одна задача на эту тему: имеется несколько ящиков, масса каждого из которых не больше 1 т, а их общая масса равна 10 т; на каком наименьшем количестве трёхтонок наверняка можно увезти эти ящики?
Решить эту задачу (и её обобщение) вам помогут следующие упражнения (первые два из них напоминают уже рассмотренные задачи):
Упражнение 4. Пусть единственным ограничением на суммарную массу ящиков является условие $P\gt3$ т. Какой наибольший груз $\textit{Г}$ можно наверняка увезти на одной трёхтонке?
Упражнение 5. Каким будет ответ в предыдущей задаче, если известно, что $P=10$ т?
Упражнение 6. Пусть теперь масса каждого ящика не превосходит $v$, суммарная масса равна $P$ и в нашем распоряжении есть машина грузоподъёмностью $p$. Пусть $\textit{Г}$ — масса максимального груза, который нам удастся погрузить на машину. Докажите, что наименьшее значение $\textit{Г}$ достигается в случае, когда все ящики имеют одинаковую массу.
Упражнение 7. Каким наименьшим запасом $p$-тонок надо располагать, чтобы наверняка перевезти все ящики из упражнения 6?
Попытайтесь найти возможно более общие формулировки теорем, подтверждающих принцип «лучше — поровну».
