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

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

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

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

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

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

Для любого угла ${\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}$. Разрезание с этим углом наклона ножа разрежет пополам оба блина одновременно.

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

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

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

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

• Точный делёж

• Гуго Штейнгауз "Математический калейдоскоп"Библиотечка•Квант• выпуск 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