Меню Главная Случайная статья Настройки Теорема о бутерброде Материал из https://ru.wikipedia.org Теорема о бутерброде утверждает, что если дано n измеримых «объектов» в Утверждение высказал Гуго Штейнгауз, а доказал Стефан Банах (в размерности три не предполагая автоматического переноса теоремы на n-мерный случай), а годом позднее утверждение было названо теоремой Стоуна — Тьюки по именам Артура Г. Стоуна и Джона Тьюки. Содержание 1 Название 2 История 3 Двумерный вариант: доказательство, использующее «движущийся нож» 4 n-мерный вариант: доказательство с помощью теоремы Борсука — Улама 5 Версии в теории меры 6 Версии в дискретной и вычислительной геометрии 7 Обобщения 8 См. также 9 Примечания 10 Литература 11 Ссылки Название Теорема о бутерброде получила своё название от случая, когда История Согласно Байеру и Жардецки[1], самой ранней статьёй о теореме о бутерброде, а именно для случая Более свежая статья — статья Стоуна и Тьюки[3], которая и дала название «теореме Стоуна — Тьюки». Эта статья доказывает Двумерный вариант: доказательство, использующее «движущийся нож» Двумерный вариант теоремы (известный также как теорема о блине) можно доказать с помощью доводов, которые появляются в литературе о задаче справедливого разрезания торта (см., например, статью Процедура «Движущийся нож» Робертсона — Уэбба). Для любого угла ${\displaystyle \alpha \in [0,180^{\circ }]}$ мы можем разрезать блин № 1 с помощью прямой под углом ${\displaystyle \alpha }$ (чтобы это видеть, будем передвигать прямую под углом ${\displaystyle \alpha }$ из ${\displaystyle -\infty }$ в ${\displaystyle \infty }$. Доля блина № 1, отсекаемая прямой, меняется при этом непрерывно от 0 до 1, так что по теореме о промежуточном значении она должна принять где-то значение 1/2). Это означает, что мы можем взять прямой нож и вращать его на угол ${\displaystyle \alpha \in [0,180^{\circ }]}$, передвигая его параллельно на необходимое расстояние, так, чтобы блин № 1 был всегда разбит пополам для любого угла. Когда нож находится под углом 0, он разрезает также и блин № 2, но его части могут и не быть равными (если нам посчастливилось и куски оказались равными, мы сделали своё дело). Определим как «положительную» сторону ножа, с которой доля блина № 2 больше. Определим ${\displaystyle p(\alpha )}$ как долю блина № 2 с положительной стороны ножа. Первоначально ${\displaystyle p(0)\geqslant 1/2}$. Когда нож повернётся на угол 180, он окажется на том же месте, но «вверх ногами», так что ${\displaystyle p(180)\leqslant 1/2}$. По теореме о промежуточном значении должен существовать угол, при котором ${\displaystyle p(\alpha )=1/2}$. Разрезание с этим углом наклона ножа разрежет пополам оба блина одновременно. n-мерный вариант: доказательство с помощью теоремы Борсука — Улама Теорема о бутерброде можно доказать следующим образом с помощью теоремы Борсука — Улама. Приводимое доказательство следует доказательству, приведённому Штейнгаузом и другими в статье 1938 года, приписываемое там Стефану Банаху, для случая Пусть ${\displaystyle A_{1},A_{2},\dots ,A_{n}}$ означают Теперь мы определим функцию f из (n 1)-сферы S в (n 1)-мерное евклидово пространство ${\displaystyle \mathbb {R} ^{n-1}}$ следующим образом: ${\displaystyle f(p)=(V_{1},V_{2},\dots ,V_{n})}$ где ${\displaystyle V_{k}}$ равен объёму ${\displaystyle A_{k}}$ с положительной стороны ${\displaystyle \pi (p)}$. Эта функция f непрерывна. По теореме Борсука — Улама существуют антиподальные точки[англ.] p и q на сфере S, такие, что ${\displaystyle f(p)=f(q)}$. Антиподальные точки p и q соответствуют гиперплоскостям ${\displaystyle \pi (p)}$ и ${\displaystyle \pi (q)}$, которые равны, за исключением ориентации положительной стороны. Тогда ${\displaystyle f(p)=f(q)}$ означает, что объём ${\displaystyle A_{i}}$ тот же самый с положительной и отрицательной сторон ${\displaystyle \pi (p)}$ (или ${\displaystyle \pi (q)}$), для i=1, 2, …, n1. Таким образом, ${\displaystyle \pi (p)}$ (или ${\displaystyle \pi (q)}$) является искомым разрезанием бутерброда, делящим пополам объёмы ${\displaystyle A_{1},A_{2},\dots ,A_{n}}$. Версии в теории меры В теории меры Стоун и Тьюки[3] доказали две более общие формы теоремы о бутерброде. Обе версии касаются деления пополам n подмножества ${\displaystyle X_{,}X_{2},\dots ,X_{n}}$ общего множества X, где X имеет внешнюю меру Каратеодори, а каждое подмножество ${\displaystyle X_{i}}$ имеет конечную внешнюю меру. Их первая обобщённая формулировка следующая: для любой должным образом ограниченной вещественной функции ${\displaystyle f\colon S^{n}\times X\to \mathbb {R} }$ существует точка p n-сферы ${\displaystyle S^{n}}$, такая, что поверхность ${\displaystyle f(s,x)=0}$, делящая множество X на ${\displaystyle f(s,x)<0}$ и ${\displaystyle f(s,x)>0}$, одновременно делит пополам внешнюю меру ${\displaystyle X_{1},X_{2},\dots ,X_{n}}$. Доказательство опять осуществляется сведением к теореме Борсука — Улама. Эта теорема обобщает стандартную теорему о бутерброде путём допущения ${\displaystyle f(s,x)=s_{0}+s_{1}x_{1}+\dots +s_{n}x_{n}}$. Их вторая обобщённая формулировка следующая: для любых n + 1 измеримых функций ${\displaystyle f_{0},f_{1},\dots ,f_{n}}$ на X, линейно независимых на любом подмножестве X положительной меры, существует линейная комбинация ${\displaystyle f=a_{0}f_{0}+a_{1}f_{1}+\dots +a_{n}f_{n}}$, такая, что последовательность ${\displaystyle f(x)=0}$, делящая X на f(x) < 0 и f(x) > 0, одновременно делит пополам внешние меры ${\displaystyle X_{1},X_{2},\dots ,X_{n}}$. Эта теорема обобщает стандартную теорему о бутерброде, в которой ${\displaystyle f_{0}(x)=1}$, а ${\displaystyle f_{i}(x)}$ для i > 0 является i-ой координатой вектора x. Версии в дискретной и вычислительной геометрии В комбинаторной и вычислительной геометрии теорема о бутерброде обычно относится к специальному случаю, когда каждое из требующих разбиения множеств является конечным множеством точек. Здесь наиболее подходящей мерой является считающая мера, которая подсчитывает число точек по одной стороне от гиперплоскости. В размерности два теорему можно сформулировать следующим образом: Для конечного множества точек на плоскости, выкрашенных в «красный» и «синий» цвета, существует прямая, которая одновременно разделяет пополам красные точки и синие точки, то есть число красных точек на каждой стороне от прямой одинаково и то же самое верно для синих точек. Имеется исключение, когда точки лежат на прямой. В этом случае мы считаем каждую из этих точек лежащей на одной или другой стороне, либо вообще ни на одной из сторон от прямой (это может зависеть от точки), то есть «разделение пополам», фактически, означает, что каждая сторона содержит меньше половины общего числа точек. Этот исключительный случай требуется для выполнения теоремы, конечно, когда число красных точек или число синих точек нечётно, но также и в определённых конфигурациях с чётным числом точек, например, когда все точки лежат на одной прямой и два цвета отделены друг друга (не перемежаются вдоль прямой). Ситуация, когда число точек с каждой стороны не соответствуют друг другу, обрабатывается путём добавления дополнительных точек вне прямой. В вычислительной геометрии эта теорема о бутерброде приводит к вычислительной задаче о бутерброде с ветчиной. В двумерном варианте задача следующая: если дано конечное множество из n точек на плоскости, выкрашенных в «красный» и «синий» цвета, найти для них разрезание бутерброда с ветчиной. Сначала Мегиддо[4] описал алгоритм для специального, разделённого случая. Здесь все красные точки лежат по одну сторону от некоторой прямой, а все синие точки находятся по другую сторону от той же прямой. В этой ситуации имеется единственное разрезание бутерброда с ветчиной, которое Мегиддо мог найти за линейное время. Позднее Эдельсбруннер и Уапотич[5] дали алгоритм для общего двумерного случая. Время работы их алгоритма составляет ${\displaystyle O(n\log n)}$, где символ O означает O-большое. Наконец, Ло и Штайгер[6] нашли оптимальный алгоритм с временем работы O(n). Этот Алгоритм распространили на высокие размерности Ло, Матушек и Штайгер[7] и время работы алгоритма равно ${\displaystyle o(n^{d-1})}$. Если дано d точек в общей позиции в d-мерном пространстве, алгоритм вычисляет (d1)-мерную гиперплоскость, которая имеет равное количество точек в каждом из полупространств, то есть даёт разрезание бутерброда с ветчиной для данных точек. Если d содержится во входных данных, то не ожидается никакого алгоритма полиномиального времени, так как в случае, когда точки лежат на кривой моментов, задача становится эквивалентной разрезанию ожерелья, которая PPA-сложна[англ.]. Алгоритм линейного времени, который осуществляет разделение двух непересекающихся выпуклых многоугольников, описал Стойменович[8]. Обобщения Исходная теорема работает максимум для n коллекций, где n — число размерностей. Если мы хотим разбить большее число коллекций без перехода в большие размерности, мы можем использовать вместо гиперплоскости алгебраическую поверхность степени k, то есть (n1)-мерную поверхность, определённую полиномиальной функцией степени k: Если дано ${\displaystyle {\binom {k+n}{n}}-1}$ мер в n-мерном пространстве, существует алгебраическая поверхность степени k, которая разрезает пополам их всех[9]. Это обобщение доказывается путём отображения n-мерной плоскости в ${\displaystyle {\binom {k+n}{n}}-1}$-мерную плоскость с последующим применением исходной теоремы. Например, для n=2 и k=2, 2-мерная плоскость отображается в 5-мерную плоскость: ${\displaystyle (x,y)\to (x,y,x^{2},y^{2},xy)}$. См. также Точный делёж Примечания 1 2 Beyer, Zardecki, 2004. Steinhaus, 1938. 1 2 Stone, Tukey, 1942. Megiddo, 1985. Edelsbrunner, Waupotitsch, 1986. Lo, Steiger, 1990. Lo, Matouek, Steiger, 1994. Stojmenovc, 1991. Smith, Wormald, 1998. Литература Beyer W. A., Andrew Zardecki. The early history of the ham sandwich theorem // American Mathematical Monthly. — 2004. — Т. 111, вып. 1. — С. 58–61. — doi:10.2307/4145019. — . Herbert Edelsbrunner, Waupotitsch R. Computing a ham sandwich cut in two dimensions // Journal of Symbolic Computation. — 1986. — Т. 2, вып. 2. — С. 171–178. — doi:10.1016/S0747-7171(86)80020-7. Chi-Yuan Lo, Steiger W. L. An optimal time algorithm for ham-sandwich cuts in the plane // Proceedings of the Second Canadian Conference on Computational Geometry. — 1990. — С. 5–9. Chi-Yuan Lo, Ji Matouek, William L. Steiger. Algorithms for Ham-Sandwich Cuts // Discrete and Computational Geometry. — 1994. — Т. 11, вып. 4. — С. 433–452. — doi:10.1007/BF02574017. Nimrod Megiddo. Partitioning with two lines in the plane // Journal of Algorithms. — 1985. — Т. 6, вып. 3. — С. 430–433. — doi:10.1016/0196-6774(85)90011-2. Smith W. D., Wormald N. C. Geometric separator theorems and applications // Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280). — 1998. — С. 232. — ISBN 0-8186-9172-7. — doi:10.1109/sfcs.1998.743449. Hugo Steinhaus. A note on the ham sandwich theorem // Mathesis Polska. — 1938. — Т. 9. — С. 26–28. Arthur Harold Stone, John W. Tukey. Generalized "sandwich" theorems // Duke Mathematical Journal. — 1942. — Т. 9, вып. 2. — С. 356–359. — doi:10.1215/S0012-7094-42-00925-6. Ivan Stojmenovi. Bisections and ham-sandwich cuts of convex polygons and polyhedra. // Info. Processing Letts.. — 1991. — Т. 38. — С. 15–21. — doi:10.1016/0020-0190(91)90209-Z. • Гуго Штейнгауз "Математический калейдоскоп"Библиотечка•Квант• выпуск 8 перевод с польского Ф.Л.Варпаховского Москва "Наука" Главная редакция физико-математической литературы 1981 Ссылки Weisstein, Eric W. Ham Sandwich Theorem (англ.) на сайте Wolfram MathWorld. ham sandwich theorem on the Earliest known uses of some of the words of mathematics Ham Sandwich Cuts by Danielle MacNevin An interactive 2D demonstration