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

Теорема о бутербродеутверждает, что если даноnизмеримых«объектов» вn-мерномевклидовом пространстве, их можно разделить пополам (согласно ихмере, то есть объёме) с помощью одной(n− 1)-мернойгиперплоскости.
Утверждение высказалГуго Штейнгауз, а доказалСтефан Банах(в размерности три не предполагая автоматического переноса теоремы на n-мерный случай), а годом позднее утверждение было названотеоремой Стоуна — Тьюкипо именам Артура Г. Стоуна иДжона Тьюки.
Теорема о бутерброде получила своё название от случая, когдаn=3, а тремя объектами любой формы являются ломтикветчиныи два ломтикахлеба. Условно говоря,бутерброд, который может быть разделён одновременно одним разрезом (то естьплоскостью). В размерности два теорема известна кактеорема о блине, поскольку заключается в разрезании бесконечно тонкогоблинана две половинки одним разрезом (то естьпрямой).
СогласноБайеруи Жардецки, самой ранней статьёй о теореме о бутерброде, а именно для случаяn=3рассечения трёх тел плоскостью, является статья Штейнгауза. Статья Байера и Жардецки включает перевод статьи 1938 года. Статья приписывает утверждение проблемыГуго Штейнгаузуи утверждает, чтоСтефан Банахпервым решил задачу путём сведения ктеореме Борсука — Улама. Статья показывает задачу двумя путями. Первый, формальный: «Всегда ли можно разбить три произвольно расположенных тела одной плоскостью?». Второй, неформальный: «Можем ли мы расположить кусок ветчины под нож так, что мясо, кость и жир разделились ножом пополам?» Статья предложила доказательство теоремы.
Более свежая статья — статья Стоуна и Тьюки, которая и дала название «теореме Стоуна — Тьюки». Эта статья доказываетn-мерную версию теоремы в более общих условиях мер. Статья приписывает случайn=3Станиславу Уламу, основываясь на собственной информации, но Байер и Жардецкиутверждают, что это неверно, указывая на статью Штейнгауза, хотя и оговариваются: «Улам сделал фундаментальный вклад в доказательство»теоремы Борсука — Улама".
Двумерный вариант теоремы (известный также кактеорема о блине) можно доказать с помощью доводов, которые появляются в литературе озадаче справедливого разрезания торта(см., например, статьюПроцедура «Движущийся нож» Робертсона — Уэбба).
Для любого углаα∈[0,180∘]{\displaystyle \alpha \in [0,180^{\circ }]}мы можем разрезать блин № 1 с помощью прямой под угломα{\displaystyle \alpha }(чтобы это видеть, будем передвигать прямую под угломα{\displaystyle \alpha }из−∞{\displaystyle -\infty }в∞{\displaystyle \infty }. Доля блина № 1, отсекаемая прямой, меняется при этом непрерывно от 0 до 1, так что потеореме о промежуточном значенииона должна принять где-то значение 1/2).
Это означает, что мы можем взять прямой нож и вращать его на уголα∈[0,180∘]{\displaystyle \alpha \in [0,180^{\circ }]}, передвигая его параллельно на необходимое расстояние, так, чтобы блин № 1 был всегда разбит пополам для любого угла.
Когда нож находится под углом 0, он разрезает также и блин № 2, но его части могут и не быть равными (если нам посчастливилось и куски оказались равными, мы сделали своё дело). Определим как «положительную» сторону ножа, с которой доля блина № 2 больше. Определимp(α){\displaystyle p(\alpha )}как долю блина № 2 с положительной стороны ножа. Первоначальноp(0)⩾1/2{\displaystyle p(0)\geqslant 1/2}.
Когда нож повернётся на угол 180, он окажется на том же месте, но «вверх ногами», так чтоp(180)⩽1/2{\displaystyle p(180)\leqslant 1/2}. Потеореме о промежуточном значениидолжен существовать угол, при которомp(α)=1/2{\displaystyle p(\alpha )=1/2}. Разрезание с этим углом наклона ножа разрежет пополам оба блина одновременно.
Теорема о бутерброде можно доказать следующим образом с помощьютеоремы Борсука — Улама. Приводимое доказательство следует доказательству, приведённому Штейнгаузом и другими в статье 1938 года, приписываемое тамСтефану Банаху, для случаяn=3. В областиэквивариантной топологииэто доказательство соответствует парадигме конфигурационного пространства/тестового пространства-карты.
ПустьA1,A2,…,An{\displaystyle A_{1},A_{2},\dots ,A_{n}}означаютnобъектов, которые мы хотим одновременно разделить надвое. ПустьSбудетединичной(n− 1)-сферой, вложенной вn-мерноеевклидово пространствоRn{\displaystyle \mathbb {R} ^{n}}и имеющее центр вначале координат. Для каждой точкиpна поверхности сферыSмы можем определитьконтинуумориентированных аффинныхгиперплоскостей(не обязательно проходящих через центр 0), перпендикулярных (нормали)векторуиз начала координат вp, с «положительной стороной» каждой гиперплоскости, определённой как сторона, в которую указывает вектор (то есть это выборориентации). По теореме отеореме о промежуточном значениилюбое семейство таких гиперплоскостей содержит по меньшей мере одну гиперплоскость, которая делит пополам ограниченный объектAn{\displaystyle A_{n}}— при одном экстремальном переносе не окажется никакого объёма уAn{\displaystyle A_{n}}с положительной стороны, но при экстремальном переносе в другом направлении весь объём окажется с положительной стороны, так между этими крайностями должен существовать перенос, который имеет с положительной стороны половину объёмаAn{\displaystyle A_{n}}. Если есть более одной такой гиперплоскости, мы можем выбрать одну как середину интервала переносов, делящих пополамAn{\displaystyle A_{n}}. Таким образом, мы получаем для каждой точкиpна сфереSгиперплоскостьπ(p){\displaystyle \pi (p)}, которая перпендикулярна вектору из начала координат в точкуpи которая делит пополамAn{\displaystyle A_{n}}.
Теперь мы определим функциюfиз(n− 1)-сферыSв(n− 1)-мерное евклидово пространствоRn−1{\displaystyle \mathbb {R} ^{n-1}}следующим образом:
гдеVk{\displaystyle V_{k}}равен объёмуAk{\displaystyle A_{k}}с положительной стороныπ(p){\displaystyle \pi (p)}.
Эта функцияfнепрерывна. Потеореме Борсука — Уламасуществуютантиподальные точкиpиqна сфереS, такие, чтоf(p)=f(q){\displaystyle f(p)=f(q)}. Антиподальные точкиpиqсоответствуют гиперплоскостямπ(p){\displaystyle \pi (p)}иπ(q){\displaystyle \pi (q)}, которые равны, за исключением ориентации положительной стороны. Тогдаf(p)=f(q){\displaystyle f(p)=f(q)}означает, что объёмAi{\displaystyle A_{i}}тот же самый с положительной и отрицательной сторонπ(p){\displaystyle \pi (p)}(илиπ(q){\displaystyle \pi (q)}), дляi=1, 2, …,n−1. Таким образом,π(p){\displaystyle \pi (p)}(илиπ(q){\displaystyle \pi (q)}) является искомым разрезанием бутерброда, делящим пополам объёмыA1,A2,…,An{\displaystyle A_{1},A_{2},\dots ,A_{n}}.
Втеории мерыСтоун и Тьюкидоказали две более общие формы теоремы о бутерброде. Обе версии касаются деления пополамnподмножестваX,X2,…,Xn{\displaystyle X_{,}X_{2},\dots ,X_{n}}общего множестваX, гдеXимеетвнешнюю меруКаратеодори, а каждое подмножествоXi{\displaystyle X_{i}}имеет конечную внешнюю меру.
Их первая обобщённая формулировка следующая: для любой должным образом ограниченной вещественнойфункцииf:Sn×X→R{\displaystyle f\colon S^{n}\times X\to \mathbb {R} }существует точкаpn-сферыSn{\displaystyle S^{n}}, такая, что поверхностьf(s,x)=0{\displaystyle f(s,x)=0}, делящая множествоXнаf(s,x)<0{\displaystyle f(s,x)<0}иf(s,x)>0{\displaystyle f(s,x)>0}, одновременно делит пополам внешнюю меруX1,X2,…,Xn{\displaystyle X_{1},X_{2},\dots ,X_{n}}. Доказательство опять осуществляется сведением к теореме Борсука — Улама. Эта теорема обобщает стандартную теорему о бутерброде путём допущенияf(s,x)=s0+s1x1+⋯+snxn{\displaystyle f(s,x)=s_{0}+s_{1}x_{1}+\dots +s_{n}x_{n}}.
Их вторая обобщённая формулировка следующая: для любыхn+ 1измеримых функцийf0,f1,…,fn{\displaystyle f_{0},f_{1},\dots ,f_{n}}наX,линейно независимыхна любом подмножествеXположительной меры, существуетлинейная комбинацияf=a0f0+a1f1+⋯+anfn{\displaystyle f=a_{0}f_{0}+a_{1}f_{1}+\dots +a_{n}f_{n}}, такая, что последовательностьf(x)=0{\displaystyle f(x)=0}, делящаяXнаf(x) < 0иf(x) > 0, одновременно делит пополам внешние мерыX1,X2,…,Xn{\displaystyle X_{1},X_{2},\dots ,X_{n}}. Эта теорема обобщает стандартную теорему о бутерброде, в которойf0(x)=1{\displaystyle f_{0}(x)=1}, аfi(x){\displaystyle f_{i}(x)}дляi> 0являетсяi-ой координатой вектораx.
Вкомбинаторнойивычислительной геометриитеорема о бутерброде обычно относится к специальному случаю, когда каждое из требующих разбиения множеств являетсяконечным множествомточек. Здесь наиболее подходящей мерой являетсясчитающая мера, которая подсчитывает число точек по одной стороне от гиперплоскости. В размерности два теорему можно сформулировать следующим образом:
Имеется исключение, когда точки лежат на прямой. В этом случае мы считаем каждую из этих точек лежащей на одной или другой стороне, либо вообще ни на одной из сторон от прямой (это может зависеть от точки), то есть «разделение пополам», фактически, означает, что каждая сторона содержит меньше половины общего числа точек. Этот исключительный случай требуется для выполнения теоремы, конечно, когда число красных точек или число синих точек нечётно, но также и в определённых конфигурациях с чётным числом точек, например, когда все точки лежат на одной прямой и два цвета отделены друг друга (не перемежаются вдоль прямой). Ситуация, когда число точек с каждой стороны не соответствуют друг другу, обрабатывается путём добавления дополнительных точек вне прямой.
В вычислительной геометрии эта теорема о бутерброде приводит к вычислительной задачео бутерброде с ветчиной. В двумерном варианте задача следующая: если дано конечное множество изnточек на плоскости, выкрашенных в «красный» и «синий» цвета, найти для них разрезание бутерброда с ветчиной. Сначала Мегиддоописал алгоритм для специального, разделённого случая. Здесь все красные точки лежат по одну сторону от некоторой прямой, а все синие точки находятся по другую сторону от той же прямой. В этой ситуации имеется единственное разрезание бутерброда с ветчиной, которое Мегиддо мог найти за линейное время. Позднее Эдельсбруннер и Уапотичдали алгоритм для общего двумерного случая. Время работы их алгоритма составляетO(nlog⁡n){\displaystyle O(n\log n)}, где символOозначаетO-большое. Наконец, Ло и Штайгернашли оптимальныйалгоритмс временем работыO(n). Этот Алгоритм распространили на высокие размерности Ло, Матушек и Штайгери время работы алгоритма равноo(nd−1){\displaystyle o(n^{d-1})}. Если даноdточек в общей позиции вd-мерном пространстве, алгоритм вычисляет(d−1)-мерную гиперплоскость, которая имеет равное количество точек в каждом из полупространств, то есть даёт разрезание бутерброда с ветчиной для данных точек. Еслиdсодержится во входных данных, то не ожидается никакого алгоритма полиномиального времени, так как в случае, когда точки лежат накривой моментов, задача становится эквивалентнойразрезанию ожерелья, котораяPPA-сложна.
Алгоритм линейного времени, который осуществляет разделение двух непересекающихся выпуклых многоугольников, описал Стойменович.
Исходная теорема работает максимум дляnколлекций, гдеn— число размерностей. Если мы хотим разбить большее число коллекций без перехода в бо́льшие размерности, мы можем использовать вместо гиперплоскостиалгебраическую поверхностьстепениk, то есть (n−1)-мерную поверхность, определённую полиномиальной функцией степениk:
Если дано(k+nn)−1{\displaystyle {\binom {k+n}{n}}-1}мер вn-мерном пространстве, существует алгебраическая поверхность степениk, которая разрезает пополам их всех.
Это обобщение доказывается путём отображенияn-мерной плоскости в(k+nn)−1{\displaystyle {\binom {k+n}{n}}-1}-мерную плоскость с последующим применением исходной теоремы. Например, дляn=2иk=2, 2-мерная плоскость отображается в 5-мерную плоскость:
• Гуго Штейнгауз "Математический калейдоскоп"Библиотечка•Квант• выпуск 8 перевод с польского Ф.Л.Варпаховского  Москва "Наука" Главная редакция физико-математической литературы 1981