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

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

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

Название

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

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

История

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

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

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

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

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

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

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

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

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

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

Пусть $A_1,A_2,\dots ,A_n$ означают Шаблон:Mvar объектов, которые мы хотим одновременно разделить надвое. Пусть Шаблон:Mvar будет единичной [[Гиперсфера|Шаблон:Math-сферой]], вложенной в Шаблон:Mvar-мерное евклидово пространство ${ℝ}^n$ и имеющее центр в начале координат. Для каждой точки Шаблон:Mvar на поверхности сферы Шаблон:Mvar мы можем определить Шаблон:Не переведено 5 ориентированных аффинных гиперплоскостей (не обязательно проходящих через центр 0), перпендикулярных (нормали) вектору из начала координат в Шаблон:Mvar, с «положительной стороной» каждой гиперплоскости, определённой как сторона, в которую указывает вектор (то есть это выбор Шаблон:Не переведено 5). По теореме о теореме о промежуточном значении любое семейство таких гиперплоскостей содержит по меньшей мере одну гиперплоскость, которая делит пополам ограниченный объект $A_n$ — при одном экстремальном переносе не окажется никакого объёма у $A_n$ с положительной стороны, но при экстремальном переносе в другом направлении весь объём окажется с положительной стороны, так между этими крайностями должен существовать перенос, который имеет с положительной стороны половину объёма$A_n$. Если есть более одной такой гиперплоскости, мы можем выбрать одну как середину интервала переносов, делящих пополам $A_n$. Таким образом, мы получаем для каждой точки Шаблон:Mvar на сфере Шаблон:Mvar гиперплоскость $\pi (p)$, которая перпендикулярна вектору из начала координат в точку Шаблон:Mvar и которая делит пополам $A_n$.

Теперь мы определим функцию Шаблон:Mvar из Шаблон:Math-сферы Шаблон:Mvar в Шаблон:Math-мерное евклидово пространство ${ℝ}^{n-1}$ следующим образом:

$f(p)=(V_1,V_2,\dots ,V_n)$

где $V_k$ равен объёму $A_k$ с положительной стороны $\pi (p)$. Эта функция Шаблон:Mvar непрерывна. По теореме Борсука — Улама существуют Шаблон:Не переведено 5 Шаблон:Mvar и Шаблон:Mvar на сфере Шаблон:Mvar, такие, что $f(p)=f(q)$. Антиподальные точки Шаблон:Mvar и Шаблон:Mvar соответствуют гиперплоскостям $\pi (p)$ и $\pi (q)$, которые равны, за исключением ориентации положительной стороны. Тогда $f(p)=f(q)$ означает, что объём $A_i$ тот же самый с положительной и отрицательной сторон $\pi (p)$ (или $\pi (q)$), для Шаблон:Math. Таким образом, $\pi (p)$ (или $\pi (q)$) является искомым разрезанием бутерброда, делящим пополам объёмы $A_1,A_2,\dots ,A_n$.

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

В теории меры Стоун и ТьюкиШаблон:Sfn доказали две более общие формы теоремы о бутерброде. Обе версии касаются деления пополам Шаблон:Mvar подмножества $X_{,}{X}_2,\dots ,X_n$ общего множества Шаблон:Mvar, где Шаблон:Mvar имеет внешнюю меру Каратеодори, а каждое подмножество $X_i$ имеет конечную внешнюю меру.

Их первая обобщённая формулировка следующая: для любой должным образом ограниченной вещественной функции $f:S^n\times X\to ℝ$ существует точка Шаблон:Mvar Шаблон:Mvar-сферы $S^n$, такая, что поверхность $f(s,x)=0$, делящая множество Шаблон:Mvar на $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$.

Их вторая обобщённая формулировка следующая: для любых Шаблон:Math измеримых функций $f_0,f_1,\dots ,f_n$ на Шаблон:Mvar, линейно независимых на любом подмножестве Шаблон:Mvar положительной меры, существует линейная комбинация $f=a_0{f}_0+a_1{f}_1+\dots +a_n{f}_n$, такая, что последовательность $f(x)=0$, делящая Шаблон:Mvar на Шаблон:Math и Шаблон:Math, одновременно делит пополам внешние меры $X_1,X_2,\dots ,X_n$. Эта теорема обобщает стандартную теорему о бутерброде, в которой $f_0(x)=1$, а $f_i(x)$ для Шаблон:Math является Шаблон:Mvar-ой координатой вектора Шаблон:Mvar.

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

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

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

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

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

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

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

Обобщения

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

Если дано $(\genfrac{}{}{0ex}{}{k+n}{n})-1$ мер в Шаблон:Mvar-мерном пространстве, существует алгебраическая поверхность степени Шаблон:Mvar, которая разрезает пополам их всехШаблон:Sfn.

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

$(x,y)\to (x,y,x^2,y^2,xy)$.

См. также

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья

Шаблон:Refend• Гуго Штейнгауз "Математический калейдоскоп"Библиотечка•Квант• выпуск 8 перевод с польского Ф.Л.Варпаховского Москва "Наука" Главная редакция физико-математической литературы 1981

Ссылки

• Шаблон: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