Теорема о сэндвиче с ветчиной

Не путать с теоремой о сжатии (иногда называемой «сэндвич-теоремой»).

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

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

Именование

Сэндвич с ветчиной

Теорема о сэндвиче с ветчиной получила свое название от случая, когда n = 3 и три объекта, которые нужно разделить пополам, являются ингредиентами сэндвича с ветчиной . Источники расходятся во мнениях относительно того, являются ли эти три ингредиента двумя ломтиками хлеба и куском ветчины ( Peters 1981 ), хлебом, сыром и ветчиной ( Cairns 1963 ) или хлебом с маслом и ветчиной ( Dubins & Spanier 1961 ). В двух измерениях эта теорема известна как теорема о блинах и относится к плоской природе двух объектов, которые нужно разделить пополам линией ( Cairns 1963 ).

История

Согласно Beyer & Zardecki (2004) , самая ранняя известная статья о теореме о сэндвиче с ветчиной, в частности о случае n = 3 разделения трех твердых тел плоскостью пополам, представляет собой заметку 1938 года в польском математическом журнале ( Editors 1938 ). Статья Бейера и Зардецкого включает перевод этой заметки, в котором постановку проблемы приписывают Хьюго Штейнхаусу , а Стефан Банах считается первым, кто решил проблему путем сведения к теореме Борсука-Улама . В записке проблема ставится двояко: во-первых, формально, как «Всегда ли можно разделить пополам три произвольно расположенных тела с помощью подходящей плоскости?» и, во-вторых, неофициально: «Можем ли мы положить кусок ветчины под нож для мяса, чтобы мясо, кости и жир были разрезаны пополам?» Затем в заметке предлагается доказательство теоремы.

Более современная ссылка - Stone & Tukey (1942) , которая легла в основу названия «теорема Стоуна-Тьюки». В данной статье доказывается n -мерная версия теоремы в более общей ситуации, включающей меры. Статья приписывает n = 3 случай Станиславу Уламу на основании информации рефери; но Бейер и Зардеки (2004) утверждают, что это неверно, учитывая упомянутое выше примечание, хотя «Улам действительно внес фундаментальный вклад, предложив» теорему Борсука-Улама .

Двумерный вариант: доказательство с

Пример двумерной теоремы о сэндвиче с ветчиной с несмежными областями: линии с шагом 5 ° делят область одинакового цвета (розовая ветчина и зеленый овощ) пополам на две равные области, черная линия обозначает общую биссектрису обеих областей.

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

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

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

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

n Борсука

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

Пусть A ₁ , A ₂ , ..., An _{обозначают} n объектов , которые мы хотим одновременно разделить пополам. Пусть S — единичная ( n − 1) -сфера, вложенная в n -мерное евклидово пространство. $\mathbb {R} ^{n}$, с центром в начале координат . Для каждой точки p на поверхности сферы S мы можем определить континуум ориентированных аффинных гиперплоскостей (не обязательно с центром в 0), перпендикулярных ( нормальному ) вектору от начала координат до p , с «положительной стороной» каждой гиперплоскости. определяется как сторона, на которую указывает этот вектор (т.е. это выбор ориентации ). По теореме о промежуточном значении каждое семейство таких гиперплоскостей содержит по крайней мере одну гиперплоскость, которая делит пополам ограниченный объект An _все объем An не находится _{: при одном крайнем перемещении ни один} на положительной стороне, а при другом крайнем перемещении - A _{Громкость n} находится на положительной стороне, поэтому между ними должен быть перевод, у которого половина громкости An _{находится} на положительной стороне. Если в семействе более одной такой гиперплоскости, мы можем выбрать одну канонически, выбрав середину интервала сдвигов, для которого делится _An пополам. Таким образом, мы получаем для каждой точки p на сфере S гиперплоскость π ( p ), перпендикулярную вектору из начала координат в p и это делит An _{пополам} .

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

f ( p ) = ( объем A ₁ на положительной стороне π ( p ) , объем A ₂ на положительной стороне π ( p ) , ..., объем A _{n −1} на положительной стороне π ( п )) .

Эта функция f непрерывна . (что при формальном доказательстве потребует некоторого обоснования) По теореме Борсука–Улама существуют противоположные точки p и q на сфере S такие, что f ( p ) = f ( q ) . Противоположные точки p и q соответствуют гиперплоскостям π ( p ) и π ( q ) , которые равны, за исключением того, что они имеют противоположные положительные стороны. Таким образом, f ( p ) = f ( q ) означает, что объём A _i одинаков на положительной и отрицательной стороне π ( p ) (или π ( q ) ), для i = 1, 2,... , п -1 . Таким образом, π ( p ) (или π ( q ) делит пополам объёмы A1 _, , A2 _. , ... An _{) — это желаемый разрез сэндвича с ветчиной ,} который одновременно

Теоретические версии измерений

В теории меры Стоун и Тьюки (1942) доказали две более общие формы теоремы о сэндвиче с ветчиной. Обе версии касаются деления пополам n подмножеств X ₁ , X ₂ , ..., X _n общего множества X , где X имеет Каратеодори внешнюю меру , а каждое X _i имеет конечную внешнюю меру.

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

Их вторая формулировка такова: для любых n + 1 измеримых функций f ₀ , f ₁ , ..., f _n над X над , линейно независимых любым подмножеством X положительной меры, существует линейная комбинация f = a ₀ f ₀ + a ₁ f ₁ + ... + a _n f _n такая, что поверхность f ( x ) = 0 , делящая X на f ( x ) < 0 и f ( x ) > 0 , одновременно делит пополам внешнюю меру Икс ₁ , Икс ₂ , ..., Х _п . Эта теорема обобщает стандартную теорему о сэндвиче с ветчиной, полагая f ₀ ( x ) = 1 и позволяя f _i ( x ) для i > 0 быть i -й координатой x .

дискретной и

Сэндвич с ветчиной, состоящий из восьми красных и семи синих точек на плоскости.

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

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

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

В вычислительной геометрии эта теорема о сэндвиче с ветчиной приводит к вычислительной задаче — задаче о сэндвиче с ветчиной . В двух измерениях проблема заключается в следующем: для заданного конечного набора из n точек на плоскости, каждая из которых окрашена в «красный» или «синий», найти для них вырезанный сэндвич с ветчиной. Во-первых, Мегиддо (1985) описал алгоритм для особого, отдельного случая. Здесь все красные точки находятся по одну сторону некоторой линии, а все синие точки — по другую сторону, ситуация, когда существует уникальный кусок сэндвича с ветчиной, который Мегиддо мог найти за линейное время. Позже Эдельсбруннер и Ваупотич (1986) предложили алгоритм для общего двумерного случая; время работы их алгоритма равно O ( n log n ) , где символ O указывает на использование нотации Big O. Наконец, Ло и Штайгер (1990) нашли оптимальный за O ( n ) -время алгоритм . распространили этот алгоритм на более высокие измерения, Ло, Матушек и Штайгер (1994) где время работы равно $o(n^{d-1})$. Учитывая d наборов точек общего положения в d -мерном пространстве, алгоритм вычисляет ( d −1) -мерную гиперплоскость, которая имеет одинаковое количество точек каждого из наборов в обоих ее полупространствах, т. е. ветчину -вырезка сэндвича по заданным точкам. Если d является частью входных данных, то не ожидается существования алгоритма с полиномиальным временем, как если бы точки находились на кривой моментов , проблема становится эквивалентной расщеплению ожерелья , которое является PPA-полным .

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

Обобщения

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

Данный ${\binom {k+n}{n}}-1$ мер в n –мерном пространстве, существует алгебраическая поверхность степени k, которая делит их все пополам. ( Смит и Вормальд (1998) ).

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

( Икс , y ) → ( Икс , y , Икс ² , и ² , ху ) .

См. также

• Точное деление

Ссылки

• Бейер, Вашингтон; Зардецки, Эндрю (2004), «Ранняя история теоремы о сэндвиче с ветчиной» , American Mathematical Monthly , 111 (1): 58–61, doi : 10.2307/4145019 , JSTOR   4145019 , ПроКвест   203746537 .
• Кэрнс, Стюарт С. (весна 1963 г.), «Сети, сэндвичи с ветчиной и замазка», Pi Mu Epsilon Journal , 3 (8): 389–403, JSTOR   24338222 .
• Дубинс, Луизиана ; Спаниер, Э.Х. (январь 1961 г.), «Как правильно разрезать торт», American Mathematical Monthly , 68 (1P1): 1–17, doi : 10.1080/00029890.1961.11989615
• Эдельсбруннер, Герберт ; Ваупотич, Р. (1986), «Вычисление разрезанного в двух измерениях сэндвича с ветчиной», Журнал символических вычислений , 2 (2): 171–178, doi : 10.1016/S0747-7171(86)80020-7 .
• Ло, Чи-Юань; Штайгер, В.Л. (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 of Mathematics , 11 (3): 473–482, doi : 10.1216/RMJ-1981-11-3-473 , JSTOR   44236614 .
• Смит, В.Д.; Вормальд, Северная Каролина (1998), «Теоремы и приложения о геометрических сепараторах», Труды 39-го ежегодного симпозиума по основам информатики (кат. № 98CB36280) , стр. 232, номер домена : 10.1109/sfcs.1998.743449 , ISBN  0-8186-9172-7 , S2CID   17962961
• Редакторы (1938), «Notatki: Z топологии», Mathesis Polska (на польском языке), 11 (1–2): 26–28 .
• Стоун, Артур Х .; Тьюки, Джон В. (1942), «Обобщенные «сэндвичевые» теоремы», Duke Mathematical Journal , 9 (2): 356–359, doi : 10.1215/S0012-7094-42-00925-6 .
• Стойменович, Иван (1991), «Биссечения и сэндвич-разрезы выпуклых многоугольников и многогранников», Information Processing Letters , 38 (1): 15–21, doi : 10.1016/0020-0190(91)90209-Z .

Внешние ссылки

• Вайсштейн, Эрик В. , «Теорема о сэндвиче с ветчиной» , MathWorld
• Теорема о сэндвиче с ветчиной о самых ранних известных употреблениях некоторых математических слов
• Сэндвич-нарезки с ветчиной от Даниэль МакНевин
• Интерактивная 2D-демонстрация