О наполнении и закупоривании бутылок

20

О наполнения и закупировании бутылок

М. Л. Гервер

Все устел: обед разогрел,
Выстро сел — за уроки сел,
«Квант» почитал — в футбол попирал…
Милл. «Мисти-фисти, или сказки про пострела»

Человек каждый день много дел развых делает. Идет утром в школе (если он школьник), домой вернется — обед разогрет и т. д. (см. эпиграф). Дела обично менять местами можно: сначала в футбол попрать — потом за уроки сеть, сперва обед съеть — потом его разогреть…

Стоп! С обедом что-то не вышло — не все на свете переставлять разрешается.

Это относится и к совсем сервисным вещим: высотному крану нечего делать на стройке, пока фундамент дома не заложен; нельзя «для сокращения сроков» пахать, сеть и молотить одновременно…

С тем, что задержка в одном дел может помешать начать другие, приходится считаться при планировании — например, когда оценивают, сколько времени потребует большеской комплекты взаимосвязанных работ. В заменке на шутливом примере показано, какого рода математические задачи могут встретиться при этом.

1. Постановка задачи

Приведли на автоматическую линию бутылки, очень много: N штук. А на линии работают 2 автомата: I и II. I бутылки наполняет, II — закупо-

21

ривает. Бутыли разные: с широким горлыщком и с узким, высоким, пузаные — нестандартиные. Про каждую бутыли известно, сколько времени уходит на ее наполнение и сколько — на ее закупоривание.

Сколько проработает автоматическая линия с момента, когда начинает наполняться первая бутылака, до момента, когда будет закупорена последняя? Это зависит от того, в каком порядке бутыли будут в автоматы попадать (например, для 6 бутылок есть $P_6=720$ таких порядков). Возникают, таким образом, два впроса:

Как быстро определить том порядок, при котором время работы линия будет наименьшим? И как бы числом это наименьшее время?

2. Численный пример

Начнем с примера: путь партия из 6 бутылок характеризуется таблицей 1.

Попробуем подавать бутыли в автоматы именно в том порядке, в котором они указаны в таблице: сначала 1-ю, потом 2-ю и так до 6-й. Тогда автоматы будут работать так.

Через 7 секунд наливающий автомат наполнит 1-ю бутыли (рис. 1), через 7 + 9 = 16 с. — 2-ю, через 16 + 3 = 19 с. — 3-ю, через 19 + 2 = 21 с. — 4-ю, через 21 + 11 = 32 с. — 5-ю, через 32 + 5 = 37 с. — 6-ю*).

Закупоривающий автомат покончит с 1-й бутыликой через 7 + 10 = 17 с. и лишь тогда сможет занять 2-й бутыликой (которая, тем самым, простит наполненная целую секунду). Со 2-й бутыликой он покончит через 17 + 8 = 25 с. (так что 3-й бутылака простит в ожидании пробки уже 6 с.). Через 25 + 1 = 26 с. будет закупорена 3-й бутылака, через 26 + 4 = 30 с. — 4-я. Теперь закупоривающий автомат мог бы занять 5-й бутыликой, но та, как мы знаем, еще не наполненна, поэтому автомат 2 с. простит без дела. Через 32 + 6 = 38 с. будет закупорена 5-й бутылака, а через 38 + 12 = 50 с., наконец, и 6-я.

Построим вспомогательную таблицу 2.

*) Считается, что, наполив бутыли, автомат может, не теряя ни секунды, начать наполнять следующее время.

22

Числа, стоящие в ее первом столбце, уже знакомы нам: здесь записано, через сколько секунд автомат I наполнит первую бутылку, первые две бутылки, первые три бутылки и т. д. Этот столбец получается последовательным сложением (сверху вниз) чисел, стоящих во втором столбце таблицы 1. Второй столбец таблицы 2 удобнее сначала читать сизу вверх: в таком порядке, чтобы получился этот столбец, складывали числа из третього столбца таблицы 1. Третьий столбец 2 — сумма первых двух ее столбцов.

Второй столбец таблицы 2 имеет следующий смысл: если бы автомат II работал без просмотр, то он закупорил бы все бутылки за 41 с.; если бы он закупоривал без просмотр все бутылки начиная со 2-й, то потребил бы на это 31 с.; на закупоривание без просмотр всех бутылок, начиная с 3-й, нужно 23 с. и т. д.

В нашем примере автомат II работал без просмотр лишь после того, как в него попала 5-я бутылка. Она была тогда подана (см. 5-ю строку таблицы 2) через 32 с. после начала работ автоматической линии; после этого автомат II работал 18 с., так что вся работа линии длилась 50 с. (см. третьий столбец таблицы 2).

В п. 5 мы вернемся к этому примеру, а теперь покажем, как вычислить время работы автоматической линии в общем случае — при условии, что порядок подачи бутылок на линии задаан.

3. Время работы автоматической линии

В нашем примере 50 с. — это наиболее число в третьем столбце таблицы 2. Это не случайно: справедливо следующее.

Утверждение 1. Пусть время наполнения и закупоривания бутылок задаются таблицей 3, и пусть бутылки попадают в автоматию в том порядке, в котором они указаны в этой таблице. Построим по таблице 3 вспомогательную таблицу 4 (подобно тому, как выше, no таблице 1 была построена таблица 2).

Тогда время работы автоматической линии равно набольшему числу в третьем столбце таблицы 4.

Доказательство. Проведем две горизонтальные прямые: I и II (рис. 2.) На прямой I отложим (сле-

23

ва направо) отрезки $P_0P_1, P_1P_2, \dots, P_{N-1}P_N$ (с длинами $a_1, a_2, \dots, a_N$). На прямой $II$ отложим (тоже слева направо) отрезки $H_1K_1, H_2K_2, \dots, H_NK_N$ (с длинами $b_1, b_2, \dots, b_N$). Точку $H_1$ расположим при этом на одной вертикали с $P_1$, и далее — при любом $i$, $1 < i \leq N$, — точку $H_i$ будем располагаать на одной вертикали с более правой из точки $P_i$ и $K_{i-1}$ (это соответствует тому, что автомат $II$ начинает закупоривать очередную бутылку, когда она наполнена и когда закупорена предыдущая бутылка). Ортогонально спроектируем на горизонтальном ось времен $t$ точки $P_0, P_1, \dots, P_N$ в точки $O, A_1, \dots, A_N$ и точку $K_N$ в точку $T_N$. Ясно, что $T_N$ – время работы автоматической линии в рассматриваемом нами случае.

Длину отрезка $A_iT_N$ на оси $t$ обозначим через $C_i$ $i=1, \dots, N$; тогда $T_N = A_i + C_i$.

Между отрезками $H_1K_1, H_2K_2, \dots, H_NK_N$ на прямой $II$ могут быть просветы, и точка $H_i$ располагается либо на одной вертикали с $P_i$, либо правее; поэтому $C_i \geqslant B_i = b_i + b_{i+1} + \dots + b_N$. Следовательно, $T_N \geqslant A_i + B_i$ ($i=1, \dots, N$).

Возьем самый правый из просветов между отрезками $H_iK_i$. Правае его идут отрезки $H_nK_n, H_{n+1}K_{n+1}, \dots, H_NK_N$, образующие один «сплошной» (без просветов) отрезок *) длины $B_n$. Так как $H_n$ не совпадает с $K_{n-1}$ (их разделяет просвет), то $H_n$ лежит на одной вертикали с $P_n$ и $A_n$. Итак, $T_N = A_n + B_n$.

Таким образом, $T_N$ равно максимному из чисел $A_i + B_i$ ($i=1, \dots, N$). Утверждение 1 доказано.

Таблица 4 строится по заданной таблице 3 чрезвычайно быстро: первые два столбца

$$\begin{array}{c c c} a_1 = A_1 & B_2 + b_1 = B_1 & A_1 + B_1 \\ A_1 + a_2 = A_2 & B_3 + b_2 = B_2 & A_2 + B_2 \\ A_2 + a_3 = A_3 & B_4 + b_3 = B_3 & A_3 + B_3 \\ \dots & \dots & \dots \\ A_{N-3} + a_{N-2} = A_{N-2} & B_{N-1} + b_{N-2} = B_{N-2} & A_{N-2} + B_{N-2} \\ A_{N-2} + a_{N-1} = A_{N-1} & B_N + b_{N-1} = B_{N-1} & A_{N-1} + B_{N-1} \\ A_{N-1} + a_N = A_N & b_N = B_N & A_N + B_N \end{array}$$

24

4. Наилучший порядок

Сначала рассмотрим случай, когда бутылок есть две.

Пусть для одной из них времена наполнения и закупирования равны $a$ и $b$, а для другой соответственно $c$ и $d$. Какой тогда порядок лучше — указаный в таблице 5 или указаный в таблице 5'?

Время работы линии в первом варианте (табл. 5) созначит через $t$. В обозначениях таблицы 4 для $N = 2$

$$A_1 = a, \quad B_1 = b + d$$
$$A_2 = a + c, \quad B_2 = d.$$

Согласно утверждению 1 время $t$ равно большему из чисел $A_1 + B_1$ и $A_2 + B_2$:

$$t = \max(A_1 + B_1, A_2 + B_2) = \max(a + b + d, a + c + d).$$

Обозначим сумму $a + b + c + d$ через $S$. Тогда формулу для $t$ можно переписать так:

$$t = \max(S - c, S - b) = S - \min(b, c)$$

(если от $S$ отличается из чисел $b$ и $c$, то получится больше из чисел $S - b$ и $S - c$).

Аналогичная формула, разумеется, справедлива и для $t'$, где $t'$ — время работы линии во втором варианте (табл. 5’):

$$t' = S - \min(a, d).$$

Итак, если $\min(a, d) \geq \min(b, c)$, то $t \geq t'$.

Другими словами, при $N = 2$ лучший порядок определяется по следующему правилу: выберем наиболее из чисел $a, b, c$ и $d$; если это $a$ или $d$, то лучше первый вариант (табл. 5), если же это $b$ или $c$, то — второй (табл. 5’). To есть при $N = 2$ в таблице, указавшей лучший порядок, наиболее из чисел должно быть в левом верхнем, либо в правом нижнем уелу.

На случай произвольного $N$ последнее предложение обобщается так.

Утверждение 2. «Наилучший» порядок можно определить по следующим правилам. Выберем в таблице 3 наиболее из чисел $a_1, b_1, \dots, a_N, b_N^*$. Если это число равно $a_k$, то $k$-ю бутылку нужно подавать на линии самого первого; если это число равно $b_k$, то $k$-ю бутылку нужно подавать на линии последней. Выяснить максим образом судьбу $k$-й бутылки, вычеркием $k$-ю строку из таблицы 3. Среди оставшихся чисел $a_i, b_i$ ($1 \leq i \leq N, i \neq k$) снова выберем наиболее из чисел $*$. Если оно равно $a_l$, то $l$-ю бутылку отправим в начало очереди, а если оно равно $b_l$, то $l$-ю бутылку отправим в конец очереди (коморую образуем все бутылки, кроме $k$-й). Итак до последней бутылки.

Мы доказем утверждение 2 в п. 6, а сейчас применим утверждение 1 и 2 к нашему примеру.

*) Если таких наиболее чисел несколько, можно взять любое из них.

25

5. Численный пример (окончание)

Наименование из чисел, обозначающих времена в таблице 1, равно 1. Это время закупоривания 3-й бутылки. Поэтому отправим 3-ю бутылку в самый конец очереди. Вычеркнем 3-ю строку из таблицы 1 и снова найдем наименование число. На этот раз оно равно 2 — это время наполнения 4-й бутылки. По нашим правилам отправляем 4-ю бутылку в начало очереди. Продолжая действовать так же, получим таблицу 1′.

Сколько будет работать линяя при новом порядке? Составим, как обычно, таблицу 2′.

Максимальное число в ее 3-м столбце равно 44. Это и есть время работлиния. По сравнению со старым порядком мы выиграли 6 секунд.

Замечание: Переставим в таблице 1′ последние две строки (то есть помещаем 3-ю и 5-ю бутылки). Первые четыре строки в таблицах 1′ и 2′ при этом не изменятся, а последние две станут таким, как в таблицах 1″ и 2″ на странице 26.

Согласно утверждению 1 время работы линейки будет по-прежнему равно 44 с. Таким образом, может служиться, что несколько различных порядков — «наилучшие». Утверждение 2 позволяет быстро найти один из них.

6. Доказательство утверждения 2

Выберем в таблице 3 какие-нибудь две строки, стоящие друг за другом, и поменяем их местами (см. табл. 6 и 6′).

Посмотрим, как изменится при этом таблица 4. Если мы переставим строки с номерами i и (i+1), то при k < i и при k > i + 1 числа $A_k$ и

Таблица 2′

26

Таблица 1"

| 3 | 3 | 1 |
| :— | :— | :— |
| 5 | 11 | 6 |

Таблица 2"

| 23+3=26 | 6+1=7 | 26+7=33 |
| :— | :— | :— |
| 26+11=37 | 6 | 37+6=43 |

Таблица 3'

| $i$ | $a$ | $b$ |
| :— | :— | :— |
| $i+1$ | $c$ | $d$ |

$B_k$ не изменяется. Изменения произойдет только в строках с номерами $i$ и $i+1$ (см. табл. 7 и 7’).

Тем самым
$$A_i + B_i = (A_{i-1} + B_{i+2}) + a + b + d,$$
$$A'_i + B'_i = (A_{i-1} + B_{i+2}) + b + c + d,$$
$$A_{i+1} + B_{i+1} = (A_{i-1} + B_{i+2}) + a + c + d,$$
$$A'_{i+1} + B'_{i+2} = (A_{i-1} + B_{i+2}) + a + b + c.$$

Обозначая $A_{i-1} + B_{i+2}$ через $H$ и используя формулы для $t$ и $t'$ из п. 4, находим
$$\max(A_i + B_i, A_{i+1} + B_{i+1}) = H + t,$$
$$\max(A'_i + B'_i, A'_{i+1} + B'_{i+1}) = H + t'.$$

Найбольшие из чисел $A_k + B_k$ (при $k \neq i$ и $k \neq i+1$) обозначим через $K$. Время работы линии в двух сравни-

ваемых между собой вариантах обозначим через $T$ и через $T'$. Тогда, согласно утверждению 1,
$$T = \max(K, H + t),$$
$$T' = \max(K, H + t').$$

Ясно, что если $t \geq t'$, то $T \geq T'^*$.
В п. 4 мы доказали, что $t \geq t'$, если $\min(a, d) \geq \min(b, c)$.

Поэтому только что полученный результат можно сформулировать так:
Лемма. Выберем в таблице 3 две произвольные сеседные строки (см.

*) Отметим, что если $t > t'$, то не обязаτεльно $T > T'$. Можно слушаться, что $\max(K, H + t, H + t') = K$ и тогда $T = T'$ независимо от того, какое из чисел $t$ и $t'$ больше.

Таблица 4**

| $A_i - 1 + a = A_i$ | $B_{i+1} + b = B_i$ | $A_i + B_i$ |
| :— | :— | :— |
| $A_i + c = A_{i+1}$ | $B_{i+2} + d = B_{i+1}$ | $A_{i+1} + B_{i+1}$ |

Таблица 5'

| $A'_i - 1 + c = A'_i$ | $B'_i + 1 + d = B'_i$ | $A'_i + B'_i$ |
| :— | :— | :— |
| $A'_i + a = A'_i + 1$ | $B'_i + 2 + b = B'_i + 1$ | $A'_i + 1 + B'_i + 1$ |

26

27

6). Если для них
min (a, d) ≥ min (b, c),
то эти строки можно переставить (см. табл. 6’), и время работы линии при этом не увеличится.

Отсюда уже следует утверждение 2 из п. 4. Доказем его.
Начем с двух простых замечаний.

1. Порядок, к которым мы приедем, применяем правила п. 4, не зависит от того, в каком порядке будут были рассставлены первоначально. Поэтому достаточно доказать утверждение 2 в том случае, когда порядок, указанный в таблице 3, уже был «наплачшим» (точнее, одним из «наплачших» *).
2. Допустим, что, последовательно применяем правила п. 4, мы решили (на некоторых шаге) перевинить какую-то бутылку ближе к концу очереди: с i-го места на (i + s)-е. тогда это можно сделать в s этапов: сначала переставить выбранную бутылку на (i + 1)-е место, потом на (i + 2)-е и т. д. To же верно и в случае, если мы должны перевинить какую-то бутылку ближе к началу очереди: это также можно сделать в несколько этапов, меняя местами лишь рядом стоящие бутылки. Если убедиться, что на каждом этапе применима лемма, то тем самым будет доказано, что выполнение правил п. 4 не увеличивает времени работы линии. Согласно предыдущему замечанию только в этом и осталось убедиться, чтоы доказать утверждение 2.

Слушан, когда какая-то бутылка переносится в начало или в конец очереди, рассматривают совершенное аналогично. Рассмотрим, например, второй из них.

Пусть по правилам п. 4 решено на некоторых шаге перевести какую-то бутылку с i-го на (i + s)-е место, и пусть на этом шаге i-я и (i + 1)-я строки задаются таблией 6. Тогда число b является наименьшим среди

*) См. замечание в конце п. 5.

чисел, обозначающих время наполнения и закупоривания для всех бутылок, еще не расставленных к этому моменту на свой окончательные места. В частности, b = min (a, b, c, d). Тем самым, min (a, d) ≥ min (b, c). Значит, лемма применима. Точно так же доказывается, что она применима на любом этапе. Таким образом, доказательство полностью закончено.

У разнения

1. В п. 3 мы подсчитали, что если порядок подачи бутылок на автоматическую линию задан, то время работы линии вычисляется за 3N — 2 сложения (где N — число бутылок). А сколько действий нужно произвести для определения «наплачшим» порядка?

Если называть «действием» выбор наименьшего числа в таблице из двух столбцов и произвольного числа строк, то потребуется N действия (см. утверждение 2 в п. 4). Пока N не велико, данное определение «действия» разумно,— например, можно считать, что при составлении таблицы 1’ по таблице 1 в п. 5 мы действительно потребили N действия (N = 6). При больших N нахождения наименьшего числа в таблице явно переставят бутыль элементарным актом, так что «действием» разумнее называется сравнение двух чисел (и выбор наименьшего из них). Сколько таких действий-сравнения требуется для определения наименьшего порядка?

2. Можно рассматривать «задачу о бутыках» не для двух, а для n автоматов. (В математической литературе решения в затемке задача известна под названием «задача Джонсона для n = 2».)

При n > 2 (далее при n = 3) эта задача до сих пор не решена. Во многом это объясняется следующим. При n = 2 добавление (N + 1)-й бутылок к N бутыкам, уже расположенным наличием образом, не влияет на взаимный порядок первых N бутылок. При n > 2 это представляется быть верным: уже при n = N = 3 можно так задать время a_i, b_i, c_i (i = 1, 2, 3) обработки трех бутылок времени, что «в присутствии 3-й бутылок» 1-я бутыка должна подаваться на линию равше 2-й, а «в отсутствие 3-й бутылок», наоборот, 2-я бутыка должна подаваться на линию равше 1-й. Приведите пример, подтверждающий это.

3. Проверьте, что при n = 3 бутыки, рассставленные «наплачшим образом», подаются на каждый из автоматов в одном и том же порядке. При n > 3 это уже не обязательно так: чтобы сделать время работы линии наименьшим, может иногда попадаться отсторону очередную бутылу, обработанную неокончательным автоматом A, и на следующий автомат B подать ее уже после бутыки, которая выйдет из автомата A позже этой. Приведите соответствующий пример.