Заплаты на кафтане

13

В № 1 журнала «Квант» за этот год была опубликована следующая задача Е. Б. Дынкина:

M185 *. На кафмане плочадью 1 помещается 5 заплам, плочадь каждой из которых не меньше $1/2$. Доказите, что найдет две запламы, плочадь общей части которых не меньше $1/5$.

Мы разберем решение этой задачи и обсуждим некоторые ее обобщения и варианты *). Наше изложение будет сопроводаться задачими, в которых, в частности, будут отмечены отдельные детали проводимых доказательств; номера наиболее трудных задач помещены звездочкой.

Мы будем обозначать как сам кафтан, так и его плочадь (по условию равную 1) буквой $M$; заплаты на кафтане (и плошади этих заплат) мы обозначим через $M_1$, $M_2$, $M_3$, $M_4$ и $M_5$, а, скажем, обещую часть заплат $M_1$ и $M_2$ (и плочадь этой общей части) — через $M_{12}$; аналогично этому общую часть заплат $M_1$, $M_2$ и $M_3$ (и ее плочадь) мы обозначим через $M_{123}$ и т. д. To obstruction, что, например, через $M_1$ мы обозначаем как заплату (геометрическую функцию), так и плочадь этой заплаты (число!), не должно нас смущать — из текста каждой раз будет понятно, в каком смысле мы употребляем запись $M_1$.

Начинаем решать задачу

Из того, что обещая плочадь всех заплат

$$M_1 + M_2 + M_3 + M_4 + M_5 \geq \frac{5}{2}$$

большое плочади $M = 1$ кафтана, вытекает, что наша пллаты перекрываются — и задача состоит в том, чтобы оценить плочади их общих частей (точнее — оценить наиболее из чисел $M_{12}$, $M_{13}, \dots, M_{45}$). Мы утверждаем, что

$$M - (M_1 + M_2 + M_3 + M_4 + M_5) + (M_{12} + M_{13} + M_{14} + \dots + M_{45}) \geq 0.$$ (1)

В самом деле, если бы заплаты не перекрывались, то была бы неотрицательная разность $M - (M_1 + M_2 + M_3 + M_4 + M_5)$, равная плочади части кафтана, вовсе не покрытой запланами. Но на самом деле наша пллаты пересекаются — и сумма $M_1 + M_2 + M_3 + M_4 + M_5$ оказывается гораздо больше общей плочадии $S$ покрытой запланами части кафтана (где, разумеется, $S \leq M = 1$): часть $M_{12}$ кафтана учитывает в сумме $M_1 + M_2 + M_3 + M_4 + M_5$ дважды, поскольку она входит в слагаемое $M_1$ и в слагаемое $M_2$, часть $M_{123}$ — трижды и т. д. Попробуйте теперь доказать, что

$$S \geq \sum M_i - \sum M_{ij}.$$ (1')

*) Краткое решение этой задачи приведено в «Кванте» № 10, 1973.

14

Если вам не удалось сделать, прочитите следующий раздел статы, а потом вернитесь к этому неравенству.

Из (1’), поскольку $M \geq S$, вытекает неравенство (1).

Неравенство (1) уже позволяет оценить попарные пересечения $M_{12}, M_{13}, \dots$ заплат. В самом деле, из него следует, что $(M_{12} + M_{13} + \dots + M_{45}) \geq \geq (M_1 + M_2 + M_3 + M_4 + M_5) - M \geq \geq \frac{5}{2} - 1 = \frac{3}{2}$.

А так как общее число попарных пересечений заплат $M_{ij}$ равно $C_5^2 = 10$, то наиболее из чисел $M_{12}, M_{13}, \dots, M_{45}$ не меньше чем
$$\frac{3}{2}:10 = \frac{3}{20}.$$

Полученная нами оценка, однако, х уже требуемой оценки $\frac{1}{5} \left( = \frac{4}{20} \right)$.

Уражение

1. На кафтане площади 1 имеется 9 заплат площади $1/5$. Докажите, что найдет такие две заплаты, площад обшей части которых не меньше $1/45$.

Формула вklюченной и исключенной

Наша оценка (1’) для площади $S$ всей покрытой запланами части кафтана не точна. Постараемся точнее определить эту площад. В правило части формулы (1’) невойдет площад никакой части кафтана, покрытой сразу тремя запланами: например, $M_{123}$ войдет в имеющие знак «плюс» члены $M_1, M_2, M_3$ и в имеющие знак «минус» члены $M_{12}, M_{13}, M_{23}$ — то есть полностью ввинадем из формулы (1’). Поэтому лучше оценкой для $S$ может служить выражение
$$\sum M_i - \sum M_{ij} + \sum M_{ijk}.$$
Однако и эта величина еще не равна $S$, поскольку какая часть кафтана $M$, покрытая сразу тремя запланами, учитывает в ней дваж-

ды: в самом деле, скажем, величина $M_{1234}$ учитывает в 8 членах $M_1, M_2, M_3, M_4; M_{123}, M_{124}, M_{134}, M_{234}$ последнего выражения, входящих в него со знаком «плюс», и лишь в 6 членах $M_{12}, M_{13}, M_{14}, M_{23}, M_{24}$ и $M_{34}$, входящих в это выражение со знаком «минус». Поэтому следует приближением к истинной величины $S$ явится выражение
$$\sum M_i - \sum M_{ij} + \sum M_{ijk} - \sum M_{ijkl},$$
которое уже «почти равно» $S$ — в нем точно учитываются все участки кафтана $M$, покрытые запланами не более чем четыреххитвых запланами, из последнего выражения «винадем»: в самом деле, он входит во все члены этого выражения, то есть как в 15 членов $M_1, M_2, M_3, M_4, M_5; M_{123}, M_{124}, \dots, M_{345}$, имеющих перед собой знак «плюс», так и в 15 членов $M_{12}, M_{13}, \dots, M_{45}; M_{1234}, M_{1235}, M_{1245}, M_{1345}$ и $M_{2345}$, имеющих перед собой знак «минус». Поэтому для того, чтобы получить точное выражение для $S$, мы должны член $M_{12345}$ к последней сумме прибавить. Вот точное равенство:
$$S = \sum M_i - \sum M_{ij} + \sum M_{ijk} - \sum M_{ijkl} + M_{12345}.$$
(здесь $i, j, k, l = 1, 2, 3, 4$ или 5). Но площад σ части кафтана, не покрытой ни одной запланой, равна $M - S$; так как $\sigma \geq 0$, то имеем $\sigma = M - \sum M_i + \sum M_{ij} - \sum M_{ijkl} + \sum M_{ijkl} - M_{12345} \geq 0.$

Формула (3) получается последовательным исключеннымрокъных запланами участки кафтана $M$ и вklючением тех из них, которые оказались исключенными двумя критрами; ее иногда называют формулой вklюченной и исключенной. Эта формула используется во многих комбинаторных рассмотренях.

15

Формула включает и исключающий справедлива и для отличного от пятки числа запlat. В обшем случае $n$ запlat формула включает и исключающий принимает внешне несколько пуляшей своей сложностью, но по существу — в полне произрачный вид:

$$\sigma = M - \sum M_{i_1} + \sum M_{i_1 i_2} - \sum M_{i_1 i_2 i_3} + \sum M_{i_1 i_2 i_3 i_4} - \dots + (-1)^{n-1} \sum M_{i_1 i_2 i_3 \dots i_{n-1}} + (-1)^n M_{123 \dots n} \geq 0$$

(здесь все индексы $i_1, i_2, \dots, i_{n-1}$ могут принимать любые из значений 1, 2, 3, \dots, $n$, причем для пересечения $M_{i_1 i_2 \dots i_k}$ запlat $M_{i_1} M_{i_2} \dots M_{ik}$ все значения $i_1, i_2, \dots, i_k$ обязательно различины).

Упражнения
2. Докажите формулу (4) при $n = 6$.
3*. Докажите формулу (4).
4. Домпонеров регулярно посещают 220 школьников. При домапонеров имеется шесть спортивных секций: легкоатлетическая (л), волейбольная (в), баскетбольная (б), футбольная (ф), секция самбо (с) и шахматная секция (ш). Число участников этих секций таково: (л) — 30 человек, (в) — 26 человек, (б) — 32 человек, (ф) — 31 человек, (с) — 28 человек и (ш) — 36 человек. Несолько секций посещают 53 школьника; из них 24 школьника посещают три или больше секций, 9 школьников — не меньше четырех секций и 3 школьника — даже пять секций (в последнюю тройку школьников входит и один чудак, который посещает все шесть спортивных секций). Сколько из посещающих домпонеров школьников не участвуют ни в одной спортивной секции?

Решение задачи M185

Мы видели, что «сокращенная» формула включает и исключающий $M - \sum M_i + \sum M_{ij} \geq 0$ (1) не дает точной оценки интересующей нас величины max $M_{ij}$ (набольшей из величины $M_{ij}$); поэтому нам придется привлечь «полную» формулу $M - \sum M_i + \sum M_{ij} - \sum M_{ijk} + \sum M_{ijkl} - M_{12345} \geq 0$. (3')

Приименим теперь формулу включает и исключающий (4) (где мы считаем теперь, что $n = 4$) к части $M_1$ кафтана $M$, покрытой своим заплатами $M_{12}, M_{13}, M_{14}$ и $M_{15}$. Мы получаем

$$\sigma_1 = M_1 - \sum M_{1i} + \sum M_{1ij} - \sum M_{1ijk} + M_{12345} \geq 0,$$

где $\sigma_1$ — часть заплаты $M_1$, не покрытая другими заплатами, и номера (или индексы) $i, j, k$ пробегают всевозможные значения 2, 3, 4 или 5. Аналогичные неравенства можно выписать и для участков $M_2, M_3, M_4$ и $M_5$ кафтана:

$$\sigma_2 = M_2 - \sum M_{2i} + \sum M_{2ij} - \sum M_{2ijk} + M_{12345} \geq 0,$$

$$\sigma_5 = M_5 - \sum M_{5i} + \sum M_{5ij} - \sum M_{5ijk} + M_{12345} \geq 0.$$

Сложив полученные таким путем 5 неравенств, отвечающих участкам $M_1, M_2, \dots, M_5$ кафтана, получаем (проверьте это):

$$\sum M_i - 2 \sum M_{ij} + 3 \sum M_{ijk} - 4 \sum M_{ijkl} + 5 M_{12345} \geq 0.$$ (5)

Найдем теперь такую комбинацию неравенств (3’) и (5), в которой овсе отсутствует сумма $\sum M_{ijk}$ «тройных перекрытый заплат». Очевидно, для этого достаточно прибавить к (3’) умноженное на $1/3$ неравенство (5). Мы получим такое неравенство

$$M - \frac{2}{3} \sum M_i + \frac{1}{3} \sum M_{ij} - \frac{1}{3} \sum M_{ijkl} + \frac{2}{3} M_{12345} \geq 0.$$ (6)

Из него следует также, что

$$M - \frac{2}{3} \sum M_i + \frac{1}{3} \sum M_{ij} \geq 0.$$ (7)

Действительно, часть $M_{12345}$ кафтана входит в каждой из его частей $M_{ijkl}$, в силу чего $\sum M_{ijkl} > 5M_{12345}$, и по-

16

Формулировка общей задачи;
случай двух запласт

На кафмане М площади 1 имеется n запласт $M_1, M_2, \dots, M_n$, площadb каждой из которых не меньше известного нам числа $\alpha$; требуется оценить площadb наиболее из пересечений $M_{ij}$ запласт.

Другими словами, для каждой конфигурации из $n$ запласт на кафтане мы находим максимум $M_{ij}$, а потом отыскиваем минимум этого максимума $M_{ij}$ по всем возможным конфигурациям запласт*). Такого рода «минимаксные» (то есть связанные с нахождением минимума некоторых максимумов) задачи играют в современной математике очень большую роль.

Искомое число min max $M_{ij}$ зависит, разумеется, от заданного числа $\alpha$, то есть является функцией от $\alpha$; так как оно зависит также и от числа $n$ запласт, то мы обозначим эту функцию через $f_n(\alpha)$ (где, очень удобно, $0 \leqslant \alpha \leqslant 1$, а $n \geqslant 2$). Решение задачи M185 сводится к доказательству равенства

$$f_5\left(\frac{1}{2}\right) = \frac{1}{5};$$

общая задача требует указыть формулу, выражающего $f_n(\alpha)$ через $\alpha$ и $n$.

Для того чтобы понять, какого ответа можно ожидать в этой общей задаче, мы начнем с (совсем простого!) случай $n = 2$. Итак, мы считаем, что на кафтане М площади 1 имеется двое запласт $M_1$ и $M_2$, площadb каждой из которых не меньше $\alpha$; нам надо указыть наименьшую возможную площад $f_2(\alpha)$ пересечения $M_{12}$ этих двух запласт.

Ясно, что если $\alpha \leqslant 1/2$, то заплаты могут во все пересечения (рис. 2, а); если же $\alpha \geqslant 1/2$, то наименьшая возможная площад $f_2(\alpha)$ пересечения

*) Мы предполагаем, что такой минимум существует, хотя это далеко не очень удобно.

17

М$_{12}$ заплат равна $2\alpha - 1$ (рис. 2, б). Таким образом,

$$f_2(\alpha) = \begin{cases} 0 & \text{при } 0 \leqslant \alpha \leqslant 1/2, \\ 2\alpha - 1 & \text{при } 1/2 \leqslant \alpha \leqslant 1, \end{cases}$$

— то есть график функции $y = f_2(\alpha)$ представляет собой ломаную линию (рис. 3). Это обстоятельство называется ломаной линий.

Уражнение
5. Описите функцию $y = f_3(\alpha)$.
Указание e: рассмотренте три сектора $M_1, M_2$ и $M_3$ круга $M$, оси симметрины $l_1, l_2$ и $l_3$ которых попарно образуют углы в $120^\circ$, а центральные углы (измеренные в долях полного угла!) равны $\alpha$; начинате с небольших значений $\alpha$ (рис. 4) и выясните, что произойдет при росте $\alpha$ вплоть до $\alpha = 1$.

Случай пяты заплат
Обратимся теперь к исходному случай 5 заплат $M_1, M_2, M_3, M_4$

Рис. 3.

Рис. 4.

2 «Квант» № 2

18

быть равны 0, и все $M_{ij}$ должны иметь одну и ту же величины $\frac{1}{2}\alpha - \frac{1}{10}$. Но если все $M_{ijk} = 0$, то каждую заплату площади $\alpha$ (например, заплату $M_1$) «заплаты на заплате» $M_{12}, M_{13}, M_{14}$ и $M_{15}$ площади $\frac{1}{2}\alpha - \frac{1}{10}$ должны покрывать уже без перекрытия, что возможно только, если $4\left(\frac{1}{2}\alpha - \frac{1}{10}\right) \leq \alpha$ и, значит, $\alpha \leq \frac{2}{5}$ (ср. с разбором выше случая образнения функций $f_5(\alpha)$ в 0).

Таким образом, нам удалось продолжить график функции $y = f_5(\alpha)$:

$$f_5(\alpha) = \frac{1}{2}\alpha - \frac{1}{10}$$ при $\frac{1}{5} \leq \alpha \leq \frac{2}{5}$.

Далее нам придется обратиться к неравенству (7) (с. 15), явившееся основным инструментом решения задачи M185. Из этого неравенства вытекает, что

$$\sum M_{ij} \geq 2\sum M_i - 3M \geq 2(5\alpha) - 3 = 10\alpha - 3,$$

откуда

$$f_5(\alpha) \geq \frac{1}{10}(10\alpha - 3) = \alpha - \frac{3}{10}.$$

Неравенство (10) выполняется при всех $\alpha$ (т. е. график функции $y = f_5(\alpha)$ целиком лежит над прямой $y = \alpha - \frac{3}{10}$; рис. 7); одноко в равенство оно обращается лишь при $\frac{2}{5} \leq \alpha \leq \frac{3}{5}$ (см. упражнение 6,a).

Далее нам придется применить формулу включений и исключений уже не только к области $M_i$ кафтана, но и к области $M_{ij}$ и $M_{ijh}$. Так, применяя эту формулу к кафтану $M_{12}$, покрытому третьями заплатими $M_{123}, M_{124}$ и $M_{125}$, получаем

$$\sigma_{12} = M_{12} - \sum M_{12i} + \sum M_{12ij} - M_{12345} \geq 0.$$

Выписьвая 10 подобных неравенств, отвечающих 10 пересечениям $M_{ij}$ заплат, и затем складывая их все, получаем (проверьте это!), что

$$\sum M_{ijh} - 4\sum M_{ijkl} + 10M_{12345} \geq 0.$$

19

Рис. 8.

Теперь мы имеем четыре неравенства (3′), (5), (11) и (12), связывающие одни и те же величины $M$, $\sum M_i$, $\sum M_{ij}$, $\sum M_{ijk}$, $\sum M_{ijkl}$ и $M_{12345}$.

Сложив неравенства (3′); (5), умноженное на $1/2$; (11), умноженное на $1/6$, мы придем к неравенству

$$M - \frac{1}{2} \sum M_i + \frac{1}{6} \sum M_{ij} - \frac{1}{6} M_{12345} \geq 0,$$

(13)

из которого выпали как член $\sum M_{ijk}$, так и член $\sum M_{ijkl}$. Из (13), очевидно, следует, что тем более

$$M - \frac{1}{2} \sum M_i + \frac{1}{6} \sum M_{ij} \geq 0$$

и, значит,

$$\sum M_{ij} \geq 3 \sum M_i - 6M \geq 3(5\alpha) - 6,$$

откуда

$$f_5(\alpha) \geq \frac{1}{10}(15\alpha - 6) = \frac{3}{2}\alpha - \frac{3}{5}.$$

(14)

Таким образом, график функции $y = f_5(\alpha)$ лежит не ниже прямой $y = \frac{3}{2}\alpha - \frac{3}{5}$ (рис. 8).

Аналогично, складывая неравенства (3′); (5), умноженное на $3/5$;

(11), умноженное на $3/10$; (12), умноженное на $1/10$, мы получим неравенство

$$M - \frac{2}{5} \sum M_i + \frac{1}{10} \sum M_{ij} \geq 0,$$

(15)

из которого выпали все члены, кроме $M$, $\sum M_i$ и $\sum M_{ij}$. Из (15), очевидно, следует, что

$$\sum M_{ij} \geq 4 \sum M_i - 10M \geq 4(5\alpha) - 10 = 20\alpha - 10$$

и, значит,

$$f_5(\alpha) \geq \frac{1}{10}(20\alpha - 10) = 2\alpha - 1.$$

Таким образом, график функции $y = f_5(\alpha)$ лежит не ниже прямой $y = \frac{3}{2}\alpha - \frac{3}{5}$ (рис. 8).

Упражнения

6. Докажите, что

a) $f_5(\alpha) = \alpha - \frac{3}{10}$ при $2/5 \leq \alpha \leq 3/5$;

b) $f_5(\alpha) = \frac{3}{2}\alpha - \frac{3}{5}$ при $3/5 \leq \alpha \leq 4/5$;

b) $f_5(\alpha) = 2\alpha - 1$ при $4/5 \leq \alpha \leq 1$.

7. Описите функцию

a) $f_4(\alpha)$; b) $f_6(\alpha)$.

20

Случай $n$ заплат

Этот случай рассматривается аналогично случайю $n = 5$; изложим коротко соответствующее рассуждение.

Прежде всего ясно, что для того, чтобы $n$ заплат $M_1, M_2, \dots, M_n$, плошадь каждой из которых не меньше $\alpha$, не перекрылаись, надо, чтобы их общая площадь $\sum M_i \geq n\alpha$ не превысило площади $M = 1$ кафтана; поэтому

$$f_n(\alpha) = 0 \text{ при } 0 \leq \alpha \leq \frac{1}{n}.$$

Далее рассмотрим основное неравенство (4) (формулу включенной и исключенной, с. 15). Из этого неравенства следует, что

$$M - \sum M_i + \sum M_{ij} \geq 0 \tag{16}$$

(почему?); и, значит,

$$\sum M_{ij} \geq \sum M_i - M \geq n\alpha - 1.$$

А так как общее число «попарных пересечений заплат» $M_{ij}$ в общем случае равно числу $C_n^2 = \frac{n(n-1)}{2}$ соответствий из $n$ по 2, то

$$f_n(\alpha) \geq \frac{1}{n(n-1)/2} (n\alpha - 1) = \frac{2}{n-1} \alpha - \frac{2}{n(n-1)}. \tag{17}$$

При этом неравенство (17) может обращаться в равенство, только если обращается в равенство (16), то есть если в формуле включенной и исключенной (4) обращаются в 0 все следующие за $\sum M_{ij}$ члены (и если, кроме того, все заплаты $M_i$ имеют площадь $\alpha$ и полностью покрывают кафтан $M$). Но в этом случае $n - 1$ «попарных пересечений заплат» $M_{12}, M_{13}, \dots, M_{1n}$ покрывают заплату $M_1$ без перекрытия (ибо все $M_{ij} = 0$). А так как в этом случае все

$$M_{1i} = \frac{2}{n-1} \alpha - \frac{2}{n(n-1)},$$

то

$$(n - 1) \left[ \frac{2}{n-1} \alpha - \frac{2}{n(n-1)} \right] \leq \alpha,$$

и, значит, $\alpha \leq \frac{2}{n}$ (и, разумеется, $\alpha \geq \frac{1}{n}$).

Далее нам придется применять формулу включенной и исключенной уже к заплатам $M_i$ (вместо всего кафтана $M$), к их пересечениям $M_{ij}, M_{ijh}$ и т. д. Применим, например, эту формулу к заплате $M_1$, покрытой «заплатами второго порядка» $M_{12}, M_{13}, \dots, M_{1n}$:

$$M_1 - \sum M_{1i} + \sum M_{1i1} i_2 - \sum M_{1i1} i_2 i_3 + \dots + (-1)^{n-2} \sum M_{1i1} i_2 \dots i_{n-2} + (-1)^{n-1} M_{123} \dots n \geq 0$$

(где $i_1, i_2, \dots, i_{n-2} = 2, 3, \dots, n$).

Складывая $n$ таких неравенств, отвечающих заплатам $M_1, M_2, \dots, M_n$, получаем неравенство

$$\sum M_i - 2 \sum M_{i1} i_2 + 3 \sum M_{i1} i_2 i_3 - \dots + (-1)^{n-2}(n-1) \sum M_{i1} i_2 \dots i_{n-1} + (-1)^{n-1} n M_{123} \dots n \geq 0 \tag{18}$$

(ср. с неравенством (5) на с. 15). Из неравенства (4) и (18) нетрудно использовать член $\sum M_{i1} i_2 i_3$ – для этого достаточно сложить (4) с умножением на 1/3 неравенством (18):

$$M - \frac{2}{3} \sum M_{i1} + \frac{1}{3} \sum M_{i1} i_2 - \frac{1}{3} \sum M_{i1} i_2 i_3 i_4 + \dots + (-1)^{n-1} \frac{n-3}{3} \times M_{123} \dots n \geq 0. \tag{19}$$

Из (19) следует, что

$$M - \frac{2}{3} \sum M_{i1} + \frac{1}{3} \sum M_{i1} i_2 \geq 0 \tag{19a}$$

и, значит,

$$\sum M_{i1} i_2 \geq 2 \sum M_{i1} - 3 M \geq 2 (n\alpha) - 3 = 2n\alpha - 3.$$

Таким образом,

$$f_n(\alpha) \geq \frac{1}{n(n-1)} (2n\alpha - 3) =$$

21

$$\frac{4}{n-1} \alpha - \frac{6}{n(n-1)},$$

причем в равенство (20) обращается лишь при $\frac{2}{n} \leqslant \alpha \leqslant \frac{3}{n}$ (см. упр. 8).

Продолжая поступать так же, как выше, окончательно найдем

$$f_n(\alpha) = 2 \frac{r-1}{n-1} \alpha - \frac{r(r-1)}{n(n-1)}$$

при $\frac{r-1}{n} \leqslant \alpha \leqslant \frac{r}{n}$, $r=1, 2, \ldots, n$.

Упражнения

8. Докажите, что (20) обращается в равенство лишь при $\frac{2}{n} \leqslant \alpha \leqslant \frac{3}{n}$.

9*. Докажите, что $f_n(\alpha) = \frac{6}{n-1} \alpha - \frac{12}{n(n-1)}$ при $\frac{3}{n} \leqslant \alpha \leqslant \frac{4}{n}$.

10*. Докажите равенство (21).

Дополнительные замечания

1. Конечно, даже «общие» формулы (21) далеко не исчерпываются тематику этой заметки, ее можно продолжать довольно далее.

2°. Метод «выравнивания заплат». Задача М185 получила в письмах читателей «Кванта» довольно много решений; некоторые читатели формулировали и обшюзну о $n$ заплатах площади, не меньше $\alpha$ на кафтане площади 1. Оdnako лишь В. Хонину из г. Первоуральска в его очень интересном письме удалось решить до конца эту «общую» задачу и найти формулы, по существу, равносильные формулам (21). При этом путь, который шел В. Хонин, в корне отличен от развитого в настоящее заметке. Хонин исходит, по существу, из рисунка 1, изображающего «оптимальное» покрытие кафтана пять заплатами: из этого рисунка видно, что в самом выгодной ситуации все части кафтана покрыты либо двумя, либо трех заплатами, причем все пересечения $M_{ij}$ заплат (где $i$ и $j=1, 2, \ldots, 5$) и все пересечения $M_{ijh}$ равны между собой.

Исходя из этого, Хонин разрабатывает своеобразную процедуру «перекройки» заплат с целью выравнивания их площадей и площадей их пересечений, при котором исключая величины max $M_{ij}$ все время не увеличивается; таким путем он доказывait, что и в общем случае «оптимальное» их расположение (к которым мы приходим в процессе построения «выравнивания» заплат) будет близко к рисунку 1, что позволяет ему найти формулы (21). При этом предложенный В. Хониным метод решения задачи является весма перспективным и в случае более сложных задачи.

Во время подготовки статьи к публикации в редакцию пришла заметка ученика 9 класса из г. Львова А. Макаревича, в которой развит подход к решению задачи М185 и ее обобщенной, аналогичной предложенной В. Хониным. К сожалению, из-за недостатка места мы не можем опубликовать эту интересную заметку.

3°. О методах «линейного программирования». Рисунок 9 показывает, что решение «общей» задачи сводится к решению системы линейных неравенств, связывающихся величины $y (=f_n(\alpha))$ с числом $\alpha$. Вопросы, связшиеся к решению системы линейных неравенств, играют большую роль в современных применениях математических методов к экономическим задачам; для их решения выработаны специальные методы — так называемые «методы линейного программирования» *). В 1968 году методы линейного программирования применили для решения «общей» задачи студент Московского университета Сергея Пирогов, при этом ему удалось не только доказать формулу (21), но и решить более задачи.

*) См., например, популяриную книгу: С. Гасс, Путешествие в страну линейного программирования, М., «Мир», 1973; см. также гл. 13 превосходной книги: А. Кофман, Р. Фор, Займемся исследованием операций, М., «Мир», 1966.