В математической теории меры , для любого натурального числа п в бутерброде теоремы состояний, заданных п измеримого «объекты» в п - мерное евклидово пространства , можно разделить их все пополам (в отношении их мер , например , объем) с единственная ( n - 1) -мерная гиперплоскость .
Она была предложена Хьюго Штайнхаусом и доказана Стефаном Банахом (явно в размерности 3, не беспокоясь об автоматическом формулировании теоремы в n-мерном случае), а также спустя годы названа теоремой Стоуна – Тьюки в честь Артура Х. Стоуна и Джона Тьюки. .
Именование
Теорема о сэндвиче с ветчиной получила свое название от случая, когда n = 3 и три объекта, которые нужно разделить пополам, являются ингредиентами сэндвича с ветчиной . Источники различаются относительно того, являются ли эти три ингредиента двумя ломтиками хлеба и кусочком ветчины ( Peters 1981 ), хлебом с сыром и ветчиной ( Cairns 1963 ) или хлебом с маслом и ветчиной ( Dubins & Spanier 1961 ). В двух измерениях эта теорема известна как теорема о блине и указывает на плоскую природу двух объектов, которые должны быть разделены линией пополам ( Cairns 1963 ).
История
Согласно Beyer & Zardecki (2004) , самая ранняя известная статья о теореме о бутерброде с ветчиной, в частности о случае n = 3 деления трех тел пополам с плоскостью, написана Штейнхаусом (1938) . Статья Бейера и Зардецки включает перевод статьи 1938 года. Автор приписывает постановку проблемы Хьюго Штайнхаусу и отмечает, что Стефан Банах первым решил проблему путем сведения к теореме Борсука – Улама . В статье проблема ставится двояко: во-первых, формально: «Всегда ли можно разделить пополам три произвольно расположенных тела с помощью подходящей плоскости?» и, во-вторых, неформально: «Можно ли положить кусок ветчины под нож для мяса, чтобы мясо, кости и жир были разрезаны пополам?» Позже в статье предлагается доказательство теоремы.
Более современная ссылка - это Stone & Tukey (1942) , лежащая в основе названия «теорема Стоуна – Тьюки». В этой статье доказывается n -мерная версия теоремы в более общей постановке, включающей меры. В статье приписывается случай n = 3 Станиславу Уламу на основании информации от рефери; но Бейер и Зардеки (2004) утверждают, что это неверно, учитывая статью Штейнхауса, хотя «Улам действительно внес фундаментальный вклад в предложение» теоремы Борсука – Улама .
Двумерный вариант: проверка вращающимся ножом
Двумерный вариант теоремы (также известный как теорема о блине ) может быть доказан аргументом, который появляется в прекрасной литературе по разрезанию торта (см., Например, процедуру вращающегося ножа Робертсона – Уэбба ).
Для каждого угла , мы можем разрезать блин №1 пополам, используя прямую под углом (чтобы увидеть это, переместите [переместите] прямую под углом из к ; доля блинов №1, покрываемая линией, непрерывно изменяется от 0 до 1, поэтому по теореме о промежуточном значении она должна быть равна 1/2 где-то по пути).
Это значит, что мы можем взять прямой нож и вращать его на любой угол. и переместите его соответствующим образом для этого конкретного угла так, чтобы блин №1 делился пополам под каждым углом и соответствующим перемещением.
Когда нож находится под углом 0, он также разрезает блин №2, но куски, вероятно, не равны (если нам повезет и кусочки равны, все готово). Определите «положительную» сторону ножа как сторону, на которой доля блина №2 больше. Определятькак фракция блина №2 на положительной стороне ножа. Первоначально.
Когда нож находится под углом 180, нож перевернут, поэтому . По теореме о промежуточном значении должен существовать угол, в котором. При разрезании под этим углом оба блина делятся пополам одновременно.
n -мерный вариант: доказательство с использованием теоремы Борсука – Улама.
Теорема о бутерброде с ветчиной может быть доказана следующим образом с помощью теоремы Борсука – Улама . Это доказательство следует за доказательством, описанным Штейнхаусом и другими (1938), приписываемым Штефану Банаху для случая n = 3 . В области эквивариантной топологии это доказательство подпадало бы под парадигму конфигурационного пространства / тестовой карты.
Пусть A 1 , A 2 ,…, A n обозначают n объектов, которые мы хотим одновременно разделить пополам. Пусть S - единичная ( n - 1) -сфера, вложенная в n -мерное евклидово пространство. с центром в начале координат . Для каждой точки p на поверхности сферы S мы можем определить континуум ориентированных аффинных гиперплоскостей (не обязательно с центром в 0), перпендикулярных ( нормальному ) вектору от начала координат до p , с «положительной стороной» каждой гиперплоскости определяется как сторона, на которую указывает этот вектор (т.е. это выбор ориентации ). По теореме о промежуточном значении каждое семейство таких гиперплоскостей содержит по крайней мере одну гиперплоскость, которая делит пополам ограниченный объект A n : при одном крайнем сдвиге объем A n не находится на положительной стороне, а при другом крайнем переносе все A Объем n находится на положительной стороне, поэтому между ними должен быть перевод, который имеет половину объема A n на положительной стороне. Если в семействе имеется более одной такой гиперплоскости, мы можем выбрать одну канонически, выбрав середину интервала перемещений, для которого A n делится пополам. Таким образом, мы получаем для каждой точки p на сфере S гиперплоскость π ( p ), которая перпендикулярна вектору от начала координат до p и делит A n пополам .
Теперь определим функцию f из ( n - 1) -сферы S в ( n - 1) -мерное евклидово пространство следующим образом:
- f ( p ) = ( vol из A 1 на положительной стороне π ( p ) , vol из A 2 на положительной стороне π ( p ) ,…, vol из A n −1 на положительной стороне π ( p )) .
Эта функция F является непрерывным . По теореме Борсука – Улама существуют антиподальные точки p и q на сфере S такие, что f ( p ) = f ( q ) . Антиподальные точки p и q соответствуют гиперплоскостям π ( p ) и π ( q ) , которые равны, за исключением того, что они имеют противоположные положительные стороны. Таким образом, f ( p ) = f ( q ) означает, что объем A i одинаков на положительной и отрицательной стороне π ( p ) (или π ( q ) ) для i = 1, 2,…, n −1 . Таким образом, π ( p ) (или π ( q ) ) - это желаемый кусок бутерброда с ветчиной, который одновременно делит пополам объемы A 1 , A 2 ,…, A n .
Версии теории меры
В теории меры , Stone & Тьюки (1942) доказал еще две общие формы теоремы о бутерброде. Обе версии касаются деления пополам n подмножеств X 1 , X 2 ,…, X n общего множества X , где X имеет внешнюю меру Каратеодори, а каждое X i имеет конечную внешнюю меру.
Их первая общая формулировка такова: для любой подходящей ограниченной действительной функции , Существует точка р о п - сфера S п так , что поверхность F ( s , х ) = 0 , разделяющие X в F ( s , х ) <0 и F ( s , х )> 0 , одновременно делит пополам внешняя мера X 1 , X 2 ,…, X n . Доказательство снова сводится к теореме Борсука-Улама. Эта теорема обобщает стандартную теорему о бутерброде с ветчиной, полагая f ( s , x ) = s 0 + s 1 x 1 +… + s n x n .
Их вторая формулировка такова: для любых n + 1 измеримых функций f 0 , f 1 ,…, f n над X , которые линейно независимы над любым подмножеством X положительной меры, существует линейная комбинация f = a 0 f 0 + a 1 f 1 +… + a n f n такая, что поверхность f ( x ) = 0 , делящая X на f ( x ) <0 и f ( x )> 0 , одновременно делит пополам внешнюю меру X 1 , X 2 ,…, X n . Эта теорема обобщает стандартную теорему о бутерброде с ветчиной, полагая f 0 ( x ) = 1 и позволяя f i ( x ) для i > 0 быть i -й координатой x .
Варианты дискретной и вычислительной геометрии
В дискретной геометрии и вычислительной геометрии , теорема о бутерброде обычно относится к частному случаю , в котором каждый из множеств будучи разделенным является конечным множеством из точек . Здесь релевантной мерой является счетная мера , которая просто подсчитывает количество точек по обе стороны от гиперплоскости. В двух измерениях теорему можно сформулировать следующим образом:
- Для конечного набора точек на плоскости, каждая из которых окрашена в красный или синий цвет, существует линия, которая одновременно делит пополам красные точки и пополам синие точки, то есть количество красных точек по обе стороны от линии. равно, и количество синих точек по обе стороны от линии равно.
Исключительный случай, когда точки лежат на прямой. В этой ситуации мы считаем каждую из этих точек либо на одной стороне, либо на другой, либо на обеих сторонах линии (возможно, в зависимости от точки), т.е. «деление пополам» на самом деле означает, что каждая сторона содержит менее половины от общего количества баллов. Этот исключительный случай на самом деле требуется для выполнения теоремы, конечно, когда количество красных точек или количество синих нечетно, но также и в определенных конфигурациях с четным количеством точек, например, когда все точки лежат на одной прямой. и два цвета отделены друг от друга (т. е. цвета не чередуются по линии). Ситуация, когда количество точек на каждой стороне не может совпадать, обеспечивается путем добавления дополнительной точки вне линии в предыдущей конфигурации.
В вычислительной геометрии эта теорема о сэндвиче с ветчиной приводит к вычислительной проблеме - проблеме сэндвича с ветчиной . В двух измерениях проблема заключается в следующем: учитывая конечный набор из n точек на плоскости, каждая из которых окрашена в красный или синий цвет, найдите для них нарезанный бутерброд с ветчиной. Во-первых, Мегиддо (1985) описал алгоритм для особого, отдельного случая. Здесь все красные точки находятся на одной стороне некоторой линии, а все синие точки - на другой стороне, ситуация, когда есть уникальная нарезка бутерброда с ветчиной, которую Мегиддо мог найти за линейное время. Позже Edelsbrunner & Waupotitsch (1986) представили алгоритм для общего двумерного случая; время работы их алгоритма O ( п войти п ) , где символ вывода указывает на использование Big O нотации . И, наконец, Ли & Стейгер (1990) нашел оптимальное O ( п ) -time алгоритм . Этот алгоритм был расширен до более высоких измерений Lo, Matoušek & Steiger (1994), где время работы. Для заданных d наборов точек общего положения в d -мерном пространстве алгоритм вычисляет ( d −1) -мерную гиперплоскость, которая имеет равное количество точек каждого из множеств в обоих своих полупространствах, т. Е. -сэндвич-нарезка по заданным точкам. Если d является частью входных данных, то не ожидается, что алгоритм полиномиального времени будет существовать, как если бы точки были на кривой моментов , проблема становится эквивалентной разделению ожерелья , которое является полным PPA .
Алгоритм линейного времени, делающий пополам два непересекающихся выпуклых многоугольника, описан Стойменовичем (1991) .
Обобщения
Исходная теорема работает не более чем для n наборов, где n - количество измерений. Если мы хотим разделить пополам большее количество наборов без перехода к более высоким измерениям, мы можем использовать вместо гиперплоскости алгебраическую поверхность степени k , т. Е. ( N - 1 ) -мерную поверхность, определяемую полиномиальной функцией степени k :
Дано меры в n -мерном пространстве, существует алгебраическая поверхность степени k, которая делит их все пополам. ( Смит и Вормальд (1998) ).
Это обобщение доказывается отображением n -мерной плоскости вразмерной плоскости, а затем применив исходную теорему. Например, для n = 2 и k = 2 двумерная плоскость отображается на пятимерную плоскость с помощью:
- ( x , y ) → ( x , y , x 2 , y 2 , xy ) .
Смотрите также
- Точное деление
Рекомендации
- Бейер, Вашингтон; Zardecki, Эндрю (2004), "Ранняя история теоремы о бутерброде" , American Mathematical Monthly , 111 (1): 58-61, DOI : 10,2307 / 4145019 , JSTOR 4145019 , ProQuest 203746537.
- Кэрнс, Стюарт С. (весна 1963 г.), «Сети, бутерброды с ветчиной и замазка», Журнал Пи Му Эпсилон , 3 (8): 389–403, JSTOR 24338222..
- Дубинс, Л. Е .; Spanier, EH (январь 1961), "Как вырезать торт достаточно", American Mathematical Monthly , 68 (1P1): 1-17, DOI : 10,1080 / 00029890.1961.11989615
- Эдельсбруннер, Герберт ; Waupotitsch, Р. (1986), "Вычисление бутерброда разреза в двух измерениях", журнал символьных вычислений , 2 (2): 171-178, DOI : 10.1016 / S0747-7171 (86) 80020-7.
- Ло, Чи-Юань; Steiger, WL (1990), "Алгоритм оптимального времени для разрезов ветчины-бутерброда на плоскости", Труды Второй Канадской конференции по вычислительной геометрии , стр. 5–9.
- Ло, Чи-Юань; Матушек, Иржи ; Стайгер, Уильям Л. (1994), "Алгоритмы Хэма-Сандвичевые порезы", Дискретная и Вычислительная геометрия , 11 (4): 433-452, DOI : 10.1007 / BF02574017.
- Мегиддо, Нимрод (1985), " Создание разделов с помощью двух линий в плоскости", журнал алгоритмов , 6 (3): 430-433, DOI : 10,1016 / 0196-6774 (85) 90011-2.
- Питерс, Джеймс В. (лето 1981), "Теорема о бутерброде и некоторые результаты", The Rocky Mountain Journal математики , 11 (3): 473-482, DOI : 10,1216 / RMJ-1981-11-3-473 , JSTOR 44236614.
- Смит, WD; Wormald, NC (1998), "Теоремы и приложения о геометрических разделителях", Труды 39-го ежегодного симпозиума по основам информатики (каталожный номер 98CB36280) , стр. 232, DOI : 10,1109 / sfcs.1998.743449 , ISBN 0-8186-9172-7, S2CID 17962961
- Steinhaus, Hugo (1938), "Notatki: Z topologii", Mathesis Polska (на польском языке), 11 (1–2): 26–28.
- Стоун, Артур Х .; Тьюки, Джон У. (1942), "Обобщенные" теоремы о сэндвиче ", Duke Mathematical Journal , 9 (2): 356–359, DOI : 10.1215 / S0012-7094-42-00925-6.
- Стойменович, Иван (1991), "Пополам и сэндвич-разрезания выпуклых многоугольников и многогранников", Инфо. Обработка Letts. , 38 (1): 15–21, DOI : 10.1016 / 0020-0190 (91) 90209-Z.
Внешние ссылки
- Вайсштейн, Эрик В. «Теорема о бутерброде с ветчиной» . MathWorld .
- Теорема о сэндвиче с ветчиной о самых ранних известных применениях некоторых слов математики
- Отрезки сэндвичей с ветчиной от Даниэль МакНевин
- Интерактивная 2D-демонстрация