Ещё раз о построении касательной

14

КВАНТ 2018/№10

второстепенных технических идей: использование куска, который оценивается неодинаково, для создания запаса; оформление алгоритма в виде индуктивного; использование разделов с быстро увеличивающейся точностью (сходящийся ряд). Многие из этих идей широко известны и часто применяются в различных ситуациях. Очень полезно владеть широким набором таких технических идей. Их богатый арсенал позволяет подходить к задаче с разных сторон, а это уже помогает нащупать путь для решения. Интересно, что в комбинаторной задаче работают методы малых величин, типичные для анализа. Из-за этого найденный алгоритм не очень эффективен на практике. Мы даже не можем оценить, каким будет число разделов в зависимости от n. Значит, в этой задаче еще есть над чем поработать. Для интересующихся данной темой есть набор статей. Может быть, кому-то из читателей удастся придумать собственный алгоритм раздела!

Литература

ференции Турнира городов, том 1, 2009, с. 71–82. 2. W.Stromquist. How to cut a cake fairly. – The American Mathematical Monthly, vol. 87, №8, 1980, pp. 640–644. 3. S.J.Brams, A.D.Taylor. An envy-free cake division protocol. – The American Mathematical Monthly, vol. 102, №1, 1995, pp. 9–18. 4. S.J.Brams, A.D.Taylor, W.S.Zwicker. A moving-knife solution to the four-person envy- free cake division. – Proceedings of the American Mathematical Society, 125, 1997, pp. 547–554. 5. W.Stromquist. Envy-free cake divisions cannot be found by finite protocols. – The Electronic Journal of Combinatorics, R11, 15, 2008. 6. A.D.Procaccia. Thou shalt covet thy neighbor’s cake. – Proceedings IJCAI’09, pp. 239–244. 7. H.Aziz, S.Mackenzie. A discrete and bounded envy-free cake cutting protocol for any number of agents. – Preprint, https://arxiv.org/abs/ 1604.03655 8. H.Aziz, S.Mackenzie. A discrete and bounded envy-free cake cutting protocol for four agents. – Preprint, https://arxiv.org/ abs/1508.05143

1. И.А.Иванов, А.Я.Канель-Белов, С.И.Кублановский, А.С.Малистов. Задача о разбойниках. – Избранные материалы Летней кон-

Работа поддержана грантом РНФ №17-11- 01337. Первый автор является лауреатом премии «Молодая математика России».

НАМ ПИШУТ

Еще раз о построении касательной

В статье Д.Швецова «Поляра» («Квант» №5 за 2017 г.) показано, как с помощью одной линейки из точки вне окружности провести к этой окружности касательные. Наш постоянный автор и читатель И.Вайнштейн заметил, что это построение позволяет проводить касательную к окружности и через точку, лежащую на окружности. Приведем построение из письма И.Вайнштейна. Пусть на окружности дана точка E (рис.1). Через эту точку проведем секущую (не через центр окружности), которая пересечет окружность в точке F. Возьмем на прямой EF произвольные точки B и D вне окружности и из них проведем касательные к окружности так, как это указано в статье «Поляра». Пусть соответствующие точки пересечения касательных – A

Рис. 1

и C, а точки касания – K, L, M, N. Пусть прямые KL и MN пересекаются в точке P. Тогда PE – искомая касательная. В самом деле, нетрудно доказать, что прямая AC тоже проходит через точку P, прямые NK и ML пересекаются на прямой BD, а точки

(Продолжение см. на с. 25)