Теорема о бутерброде

Теорема о бутерброде утверждает, что если дано n измеримых «объектов» в n-мерном евклидовом пространстве, их можно разделить пополам (согласно их мере, то есть объёме) с помощью одной (n − 1)-мерной гиперплоскости.

Утверждение высказал Гуго Штейнгауз, а доказал Стефан Банах (в размерности три не предполагая автоматического переноса теоремы на n-мерный случай), а годом позднее утверждение было названо теоремой Стоуна — Тьюки по именам Артура Г. Стоуна и Джона Тьюки.

Название

Бутерброд с ветчиной

Теорема о бутерброде получила своё название от случая, когда n=3, а тремя объектами любой формы являются ломтик ветчины и два ломтика хлеба. Условно говоря, бутерброд, который может быть разделён одновременно одним разрезом (то есть плоскостью). В размерности два теорема известна как теорема о блине, поскольку заключается в разрезании бесконечно тонкого блина на две половинки одним разрезом (то есть прямой).

История

Согласно Байеру и Жардецки^[1], самой ранней статьёй о теореме о бутерброде, а именно для случая n=3 рассечения трёх тел плоскостью, является статья Штейнгауза^[2]. Статья Байера и Жардецки включает перевод статьи 1938 года. Статья приписывает утверждение проблемы Гуго Штейнгаузу и утверждает, что Стефан Банах первым решил задачу путём сведения к теореме Борсука — Улама. Статья показывает задачу двумя путями. Первый, формальный: «Всегда ли можно разбить три произвольно расположенных тела одной плоскостью?». Второй, неформальный: «Можем ли мы расположить кусок ветчины под нож так, что мясо, кость и жир разделились ножом пополам?» Статья предложила доказательство теоремы.

Более свежая статья — статья Стоуна и Тьюки^[3], которая и дала название «теореме Стоуна — Тьюки». Эта статья доказывает n-мерную версию теоремы в более общих условиях мер. Статья приписывает случай n=3 Станиславу Уламу, основываясь на собственной информации, но Байер и Жардецки^[1] утверждают, что это неверно, указывая на статью Штейнгауза, хотя и оговариваются: «Улам сделал фундаментальный вклад в доказательство» теоремы Борсука — Улама".

Двумерный вариант: доказательство, использующее «движущийся нож»

Двумерный вариант теоремы (известный также как теорема о блине) можно доказать с помощью доводов, которые появляются в литературе о задаче справедливого разрезания торта (см., например, статью Процедура «Движущийся нож» Робертсона — Уэбба).

Для любого угла $\alpha \in [0,180^{\circ }]$ мы можем разрезать блин № 1 с помощью прямой под углом $\alpha$ (чтобы это видеть, будем передвигать прямую под углом $\alpha$ из $-\infty$ в $\infty$ . Доля блина № 1, отсекаемая прямой, меняется при этом непрерывно от 0 до 1, так что по теореме о промежуточном значении она должна принять где-то значение 1/2).

Это означает, что мы можем взять прямой нож и вращать его на угол $\alpha \in [0,180^{\circ }]$ , передвигая его параллельно на необходимое расстояние, так, чтобы блин № 1 был всегда разбит пополам для любого угла.

Когда нож находится под углом 0, он разрезает также и блин № 2, но его части могут и не быть равными (если нам посчастливилось и куски оказались равными, мы сделали своё дело). Определим как «положительную» сторону ножа, с которой доля блина № 2 больше. Определим $p(\alpha )$ как долю блина № 2 с положительной стороны ножа. Первоначально $p(0)\geqslant 1/2$ .

Когда нож повернётся на угол 180, он окажется на том же месте, но «вверх ногами», так что $p(180)\leqslant 1/2$ . По теореме о промежуточном значении должен существовать угол, при котором $p(\alpha )=1/2$ . Разрезание с этим углом наклона ножа разрежет пополам оба блина одновременно.

n-мерный вариант: доказательство с помощью теоремы Борсука — Улама

Теорема о бутерброде можно доказать следующим образом с помощью теоремы Борсука — Улама. Приводимое доказательство следует доказательству, приведённому Штейнгаузом и другими в статье 1938 года, приписываемое там Стефану Банаху, для случая n=3. В области эквивариантной топологии^[англ.] это доказательство соответствует парадигме конфигурационного пространства/тестового пространства-карты.

Пусть $A_{1},A_{2},\dots ,A_{n}$ означают n объектов, которые мы хотим одновременно разделить надвое. Пусть S будет единичной (n − 1)-сферой, вложенной в n-мерное евклидово пространство $\mathbb {R} ^{n}$ и имеющее центр в начале координат. Для каждой точки p на поверхности сферы S мы можем определить континуум^[англ.] ориентированных аффинных гиперплоскостей (не обязательно проходящих через центр 0), перпендикулярных (нормали) вектору из начала координат в p, с «положительной стороной» каждой гиперплоскости, определённой как сторона, в которую указывает вектор (то есть это выбор ориентации^[англ.]). По теореме о теореме о промежуточном значении любое семейство таких гиперплоскостей содержит по меньшей мере одну гиперплоскость, которая делит пополам ограниченный объект $A_{n}$ — при одном экстремальном переносе не окажется никакого объёма у $A_{n}$ с положительной стороны, но при экстремальном переносе в другом направлении весь объём окажется с положительной стороны, так между этими крайностями должен существовать перенос, который имеет с положительной стороны половину объёма $A_{n}$ . Если есть более одной такой гиперплоскости, мы можем выбрать одну как середину интервала переносов, делящих пополам $A_{n}$ . Таким образом, мы получаем для каждой точки p на сфере S гиперплоскость $\pi (p)$ , которая перпендикулярна вектору из начала координат в точку p и которая делит пополам $A_{n}$ .

Теперь мы определим функцию f из (n − 1)-сферы S в (n − 1)-мерное евклидово пространство $\mathbb {R} ^{n-1}$ следующим образом:

f(p)=(V_{1},V_{2},\dots ,V_{n})

где $V_{k}$ равен объёму $A_{k}$ с положительной стороны $\pi (p)$ . Эта функция f непрерывна. По теореме Борсука — Улама существуют антиподальные точки^[англ.] p и q на сфере S, такие, что $f(p)=f(q)$ . Антиподальные точки p и q соответствуют гиперплоскостям $\pi (p)$ и $\pi (q)$ , которые равны, за исключением ориентации положительной стороны. Тогда $f(p)=f(q)$ означает, что объём $A_{i}$ тот же самый с положительной и отрицательной сторон $\pi (p)$ (или $\pi (q)$ ), для i=1, 2, …, n−1. Таким образом, $\pi (p)$ (или $\pi (q)$ ) является искомым разрезанием бутерброда, делящим пополам объёмы $A_{1},A_{2},\dots ,A_{n}$ .

Версии в теории меры

В теории меры Стоун и Тьюки^[3] доказали две более общие формы теоремы о бутерброде. Обе версии касаются деления пополам n подмножества $X_{,}X_{2},\dots ,X_{n}$ общего множества X, где X имеет внешнюю меру Каратеодори, а каждое подмножество $X_{i}$ имеет конечную внешнюю меру.

Их первая обобщённая формулировка следующая: для любой должным образом ограниченной вещественной функции $f\colon S^{n}\times X\to \mathbb {R}$ существует точка p n-сферы $S^{n}$ , такая, что поверхность $f(s,x)=0$ , делящая множество X на $f(s,x)<0$ и $f(s,x)>0$ , одновременно делит пополам внешнюю меру $X_{1},X_{2},\dots ,X_{n}$ . Доказательство опять осуществляется сведением к теореме Борсука — Улама. Эта теорема обобщает стандартную теорему о бутерброде путём допущения $f(s,x)=s_{0}+s_{1}x_{1}+\dots +s_{n}x_{n}$ .

Их вторая обобщённая формулировка следующая: для любых n + 1 измеримых функций $f_{0},f_{1},\dots ,f_{n}$ на X, линейно независимых на любом подмножестве X положительной меры, существует линейная комбинация $f=a_{0}f_{0}+a_{1}f_{1}+\dots +a_{n}f_{n}$ , такая, что последовательность $f(x)=0$ , делящая X на f(x) < 0 и f(x) > 0, одновременно делит пополам внешние меры $X_{1},X_{2},\dots ,X_{n}$ . Эта теорема обобщает стандартную теорему о бутерброде, в которой $f_{0}(x)=1$ , а $f_{i}(x)$ для i > 0 является i-ой координатой вектора x.

Версии в дискретной и вычислительной геометрии

Разрез бутерброда с ветчиной из восьми красных точек и семи синих на плоскости.

В комбинаторной и вычислительной геометрии теорема о бутерброде обычно относится к специальному случаю, когда каждое из требующих разбиения множеств является конечным множеством точек. Здесь наиболее подходящей мерой является считающая мера, которая подсчитывает число точек по одной стороне от гиперплоскости. В размерности два теорему можно сформулировать следующим образом:

Для конечного множества точек на плоскости, выкрашенных в «красный» и «синий» цвета, существует прямая, которая одновременно разделяет пополам красные точки и синие точки, то есть число красных точек на каждой стороне от прямой одинаково и то же самое верно для синих точек.

Имеется исключение, когда точки лежат на прямой. В этом случае мы считаем каждую из этих точек лежащей на одной или другой стороне, либо вообще ни на одной из сторон от прямой (это может зависеть от точки), то есть «разделение пополам», фактически, означает, что каждая сторона содержит меньше половины общего числа точек. Этот исключительный случай требуется для выполнения теоремы, конечно, когда число красных точек или число синих точек нечётно, но также и в определённых конфигурациях с чётным числом точек, например, когда все точки лежат на одной прямой и два цвета отделены друг друга (не перемежаются вдоль прямой). Ситуация, когда число точек с каждой стороны не соответствуют друг другу, обрабатывается путём добавления дополнительных точек вне прямой.

В вычислительной геометрии эта теорема о бутерброде приводит к вычислительной задаче о бутерброде с ветчиной. В двумерном варианте задача следующая: если дано конечное множество из n точек на плоскости, выкрашенных в «красный» и «синий» цвета, найти для них разрезание бутерброда с ветчиной. Сначала Мегиддо^[4] описал алгоритм для специального, разделённого случая. Здесь все красные точки лежат по одну сторону от некоторой прямой, а все синие точки находятся по другую сторону от той же прямой. В этой ситуации имеется единственное разрезание бутерброда с ветчиной, которое Мегиддо мог найти за линейное время. Позднее Эдельсбруннер и Уапотич^[5] дали алгоритм для общего двумерного случая. Время работы их алгоритма составляет $O(n\log n)$ , где символ O означает O-большое. Наконец, Ло и Штайгер^[6] нашли оптимальный алгоритм с временем работы O(n). Этот Алгоритм распространили на высокие размерности Ло, Матушек и Штайгер^[7] и время работы алгоритма равно $o(n^{d-1})$ . Если дано d точек в общей позиции в d-мерном пространстве, алгоритм вычисляет (d−1)-мерную гиперплоскость, которая имеет равное количество точек в каждом из полупространств, то есть даёт разрезание бутерброда с ветчиной для данных точек. Если d содержится во входных данных, то не ожидается никакого алгоритма полиномиального времени, так как в случае, когда точки лежат на кривой моментов, задача становится эквивалентной разрезанию ожерелья, которая PPA-сложна^[англ.].

Алгоритм линейного времени, который осуществляет разделение двух непересекающихся выпуклых многоугольников, описал Стойменович^[8].

Обобщения

Исходная теорема работает максимум для n коллекций, где n — число размерностей. Если мы хотим разбить большее число коллекций без перехода в бо́льшие размерности, мы можем использовать вместо гиперплоскости алгебраическую поверхность степени k, то есть (n−1)-мерную поверхность, определённую полиномиальной функцией степени k:

Если дано ${\binom {k+n}{n}}-1$ мер в n-мерном пространстве, существует алгебраическая поверхность степени k, которая разрезает пополам их всех^[9].

Это обобщение доказывается путём отображения n-мерной плоскости в ${\binom {k+n}{n}}-1$ -мерную плоскость с последующим применением исходной теоремы. Например, для n=2 и k=2, 2-мерная плоскость отображается в 5-мерную плоскость:

(x,y)\to (x,y,x^{2},y^{2},xy)

.

См. также

Точный делёж

Примечания

Литература

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. — JSTOR 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ří Matoušek, 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

[_a4e3c565998eb41d-1] ¹ ² Beyer, Zardecki, 2004.

[_5ddf21382060232e-2] Steinhaus, 1938.

[_c47180861ccd1994-3] ¹ ² Stone, Tukey, 1942.

[_2512b5a5a49cfd8b-4] Megiddo, 1985.

[_2679f20cf326afc9-5] Edelsbrunner, Waupotitsch, 1986.

[_432d9c9617488708-6] Lo, Steiger, 1990.

[_6dc6e64ee323bf50-7] Lo, Matoušek, Steiger, 1994.

[_d04a2989cf554b0d-8] Stojmenovíc, 1991.

[_78ee6afc6e2b5297-9] Smith, Wormald, 1998.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]