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

Теоре́ма про бутербро́д стверджує, що якщо дано n вимірних «об'єктів» у n-вимірному евклідовому просторі, їх можна розділити навпіл (за їх мірою, тобто об'ємом) за допомогою однієї (n − 1)-вимірної гіперплощини.

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

Назва

Бутерброд з шинкою

Теорема про бутерброд отримала свою назву від випадку, коли n=3, а трьома об'єктами довільної форми є скибка шинки і дві скибки хліба. Умовно кажучи, бутерброд, який можна розділити одночасно одним розрізом (тобто, площиною). В розмірності два теорема відома як теорема про млинець, оскільки полягає в розрізанні нескінченно тонкого млинця на дві половинки одним розрізом (тобто, прямою).

Історія

За Байєром і Жардецкі, найранішою статтею про теорему про бутерброд, а саме для випадку n=3 розсічення трьох тіл площиною, є стаття Штейнгауза. Стаття Баєра і Жардецкі включає переклад статті 1938 року. Стаття приписує твердження проблеми Гуго Штейнгаузу і стверджує, що Стефан Банах першим розв'язав задачу, звівши її до теореми Борсука — Уляма. Стаття показує задачу двома способами. Перший, формальний: «Чи завжди можна розбити три довільно розташованих тіла однією площиною?». Другий, неформальний: «Чи можемо ми розташувати шматок шинки під ніж так, що м'ясо, кістка і жир розділилися ножем навпіл?». У статті запропоновано доведення теореми.

Свіжіша стаття — стаття Стоуна і Тьюкі, яка й дала назву «теоремі Стоуна — Тьюкі». Ця стаття доводить n-вимірну версію теореми в більш загальних умовах мір. Стаття приписує випадок n=3 Станіславу Уляму, ґрунтуючись на власній інформації, але Баєр і Жардецкі стверджують, що це неправильно, посилаючись на статтю Штейнгауза, хоча й уточнюють: «Улям зробив фундаментальний внесок у доведення» теореми Борсука — Уляма".

Двовимірний варіант: доведення, що використовує «рухомий ніж»

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

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

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

Коли ніж розташований під кутом 0, він розрізає також і млинець № 2, але його частини можуть і не бути рівними (якщо нам пощастило і вони виявилися рівними, ми досягли мети). Визначимо як «додатний» бік ножа, з якого частка млинця № 2 більша. визначимо $p(\alpha )$ як частку млинця № 2 з додатного боку ножа. Спочатку $p(0)\geqslant 1/2$.

Коли ніж повернеться на кут $180^{\circ }$, він виявиться на тому ж місці, але «догори ногами», так що $p(180)\leqslant 1/2$. За теоремою про проміжне значення повинен існувати кут, за якого $p(\alpha )=1/2$. Розріз з цим кутом нахилу ножа поділить навпіл обидва млинці одночасно.

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

Теорему про бутерброд можна довести за допомогою теореми Борсука — Уляма. Наведене доведення слідує доведенню зі статті Штейнгауза та інших 1938 року, де воно приписане Стефану Банаху, для випадку n=3. В галузі еквіваріантної топології це доведення відповідає парадигмі конфігураційного простору/тестового простору-карти.

Нехай $A_{1},A_{2},\dots ,A_{n}$ означають n об'єктів, які ми хочемо одночасно розділити надвоє. Нехай S буде одиничною (n − 1)-сферою, вкладеною в n-вимірний евклідів простір $\mathbb {R} ^{n}$ і з центром у початку координат. Для кожної точки p на поверхні сфери S ми можемо визначити континуум орієнтованих афінних гиперплощин (які не обов'язково проходять через центр 0), перпендикулярних (нормалі) до вектора від початку координат у p, з «додатним боком» кожної гіперплощини, визначеним як бік, на який вказує вектор (тобто, це вибір орієнтації). За теоремою про проміжне значення будь-яке сімейство таких гіперплощин містить принаймні одну гіперплощину, яка ділить навпіл обмежений об'єкт $A_{n}$ — при одному екстремальному перенесенні не виявиться ніякого об'єму в $A_{n}$ з додатного боку, але при екстремальному перенесенні в іншому напрямку весь об'єм виявиться з додатного боку, тому між цими крайнощами має існувати перенесення, за якого з додатного боку буде половина об'єму $A_{n}$. Якщо є більше від однієї такої гіперплощини, ми можемо вибрати одну як середину інтервалу перенесень, які ділять навпіл $A_{n}$. Таким чином, ми отримуємо для кожної точки p на сфері S гіперплощину $\pi (p)$, яка перпендикулярна до вектора від початку координат у точку p і яка ділить навпіл $A_{n}$.

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

$f(p)=(V_{1},V_{2},\dots ,V_{n})$

де $V_{k}$ дорівнює об'єму $A_{k}$ з додатного боку $\pi (p)$. Ця функція f неперервна. За теоремою Борсука — Уляма існують антиподальні точки p і q на сфері S, такі що $f(p)=f(q)$. Антиподальні точки p і q відповідають гіперплощинам $\pi (p)$ і $\pi (q)$, які рівні за винятком орієнтації додатного боку. Тоді, $f(p)=f(q)$ означає, що об'єм $A_{i}$ такий самий з додатного й від'ємного боків $\pi (p)$ (або $\pi (q)$), для i=1, 2, …, n−1. Таким чином, $\pi (p)$ (або $\pi (q)$) є шуканим розрізанням бутерброда, яке ділить навпіл об'єми $A_{1},A_{2},\dots ,A_{n}$.

Версії в теорії міри

В теорії міри Стоун і Тьюкі довели дві загальні форми теореми про бутерброд. Обидві версії стосуються поділу навпіл n підмножини $X_{,}X_{2},\dots ,X_{n}$ загальної множини X, де X має зовнішню міру Каратеодорі, а кожна підмножина $X_{i}$ має скінченну зовнішню міру.

Їхнє перше узагальнене формулювання таке: для будь-якої належним чином обмеженої дійсної функції $f\colon S^{n}\times X\to \mathbb {R}$ існує точка p n-сфери $S^{n}$, така, що поверхня $f(s,x)=0$, яка ділить множину X на $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}$.

Їхнє друге узагальнене формулювання таке: для будь-яких n + 1 вимірних функцій $f_{0},f_{1},\dots ,f_{n}$ на X, лінійно незалежних на будь-якій підмножині X додатної міри, існує лінійна комбінація $f=a_{0}f_{0}+a_{1}f_{1}+\dots +a_{n}f_{n}$, така що послідовність $f(x)=0$, яка ділить X на f(x) < 0 і f(x) > 0, одночасно ділить навпіл зовнішні міри $X_{1},X_{2},\dots ,X_{n}$. Ця теорема узагальнює стандартну теорему про бутерброд, у якій $f_{0}(x)=1$, а $f_{i}(x)$ для i > 0 є i-ою координатою вектора x.

Версії дискретній та обчислювальній геометрії

Розріз бутерброда з шинкою з восьми червоних точок і семи синіх на площині.

У комбінаторній та обчислювальній геометрії теорема про бутерброд зазвичай стосується особливого випадку, коли кожна із множин, які потребують розбиття, є скінченною множиною точок. Тут найвідповіднішою мірою є лічильна міра, яка підраховує кількість точок з одного боку від гіперплощини. В розмірності два теорему можна сформулювати так:

Для скінченної множини точок на площині, пофарбованих у червоний і синій кольори, існує пряма, яка одночасно розділяє навпіл червоні точки і сині точки, тобто число червоних точок з кожного боку від прямої однакове і це саме виконується для синіх точок.

Є виняток, коли точки лежать на прямій. У цьому випадку ми вважаємо кожну з цих точок такою, що лежить з одного або іншого боку, або взагалі з жодного боку від прямої (це може залежати від точки), тобто «поділ навпіл», фактично, означає, що кожен бік містить менше половини загального числа точок. Цей винятковий випадок потрібен для виконання теореми, звичайно, коли число червоних точок або число синіх точок непарне, але також і в певних конфігураціях з парним числом точок, наприклад, коли всі точки лежать на одній прямій і два кольори відокремлені один одного (не чергуються вздовж прямої). Ситуація, коли кількості точок з кожного боку не відповідають одна одній, обробляється додаванням точок поза прямою.

В обчислювальній геометрії ця теорема про бутерброд призводить до обчислювальної задачі про бутерброд із шинкою. У двовимірному варіанті задача така: якщо дано скінченну множину з n точок на площині, пофарбованих у «червоний» і «синій» кольори, знайти для них розрізання бутерброда з шинкою. Спочатку Мегіддо описав алгоритм для спеціального, розділеного випадку. Тут усі червоні точки лежать по один бік від деякої прямої, а всі сині точки — по інший бік від тієї ж прямої. В цій ситуації є єдине розрізання бутерброда з шинкою, яке Мегіддо міг знайти за лінійний час. Пізніше Едельсбруннер і Ваупотич (Roman Waupotitsch) дали алгоритм для загального двовимірного випадку. Час роботи їхнього алгоритму становить $O(n\log n)$, де символ O означає O-велике. Нарешті, Ло і Штайгер знайшли оптимальний алгоритм з часом роботи O(n). Цей алгоритм поширили на високі розмірності Ло, Матушек і Штайгер і час роботи алгоритму дорівнює $o(n^{d-1})$. Якщо дано d точок у загальному положенні в d-вимірному просторі, алгоритм обчислює (d−1)-вимірну гіперплощину, яка має рівну кількість точок у кожному з напівпросторів, тобто дає розрізання бутерброда з шинкою для даних точок. Якщо d міститься у вхідних даних, то не очікується ніякого алгоритму поліноміального часу, оскільки в разі, коли точки лежать на кривій моментів, задача стає еквівалентною розрізанню намиста, яка PPA-складна .

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

Узагальнення

Початкова теорема працює максимум для n колекцій, де n — число вимірів. Якщо ми хочемо розбити більшу кількість колекцій без переходу у вищі розмірності, можна використати замість гіперплощини алгебричну поверхню степеня k тобто n−1-вимірну поверхню, визначену поліноміальною функцією степеня k

Якщо дано ${\binom {k+n}{n}}-1$ мір в n-вимірному просторі, існує алгебрична поверхня степеня k яка розрізає навпіл їх усіх .

Це узагальнення доводиться відображенням n-вимірної площини в ${\binom {k+n}{n}}-1$-вимірну площину з подальшим застосуванням початкової теореми. Наприклад, для n=2 і k=2 2-вимірна площина відображається у 5-вимірну площину:

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

Див. також

• Точний поділ

Література

• Beyer W. A., Andrew Zardecki. The early history of the ham sandwich theorem // American Mathematical Monthly. — 2004. — Т. 111, вип. 1 (12 травня). — С. 58–61. — DOI:10.2307/4145019. Архівовано з джерела 28 листопада 2019. Процитовано 10 грудня 2020.
• Herbert Edelsbrunner, Waupotitsch R. Computing a ham sandwich cut in two dimensions // Journal of Symbolic Computation. — 1986. — Т. 2, вип. 2 (12 травня). — С. 171–178. — DOI:10.1016/S0747-7171(86)80020-7.
• Chi-Yuan Lo, Steiger W. L. An optimal time algorithm for ham-sandwich cuts in the plane // Proceedings of the Second Canadian Conference on Computational Geometry. — 1990. — С. 5–9.
• Chi-Yuan Lo, Jiří Matoušek, William L. Steiger. Algorithms for Ham-Sandwich Cuts // Discrete and Computational Geometry. — 1994. — Т. 11, вип. 4 (12 травня). — С. 433–452. — DOI:10.1007/BF02574017.
• Nimrod Megiddo. Partitioning with two lines in the plane // Journal of Algorithms. — 1985. — Т. 6, вип. 3 (12 травня). — С. 430–433. — DOI:10.1016/0196-6774(85)90011-2.
• Smith W. D., Wormald N. C. Geometric separator theorems and applications // Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280). — 1998. — С. 232. — ISBN 0-8186-9172-7. — DOI:10.1109/sfcs.1998.743449.
• Hugo Steinhaus. A note on the ham sandwich theorem // Mathesis Polska. — 1938. — Т. 9 (12 травня). — С. 26–28.
• Arthur Harold Stone, John W. Tukey. Generalized "sandwich" theorems // Duke Mathematical Journal. — 1942. — Т. 9, вип. 2 (12 травня). — С. 356–359. — DOI:10.1215/S0012-7094-42-00925-6.
• Ivan Stojmenović. Bisections and ham-sandwich cuts of convex polygons and polyhedra. // Info. Processing Letts.. — 1991. — Т. 38 (12 травня). — С. 15–21. — DOI:10.1016/0020-0190(91)90209-Z.
• Гуго Штейнгауз "Математический калейдоскоп"Библиотечка•Квант• выпуск 8 перевод с польского Ф. Л. Варпаховского Москва «Наука» Главная редакция физико-математической литературы 1981

Посилання

• Weisstein, Eric W. Ham Sandwich Theorem (англ.)
• ham sandwich theorem [Архівовано 6 листопада 2020 у Wayback Machine.] on the Earliest known uses of some of the words of mathematics [Архівовано 4 березня 2009 у Wayback Machine.]
• Ham Sandwich Cuts [Архівовано 22 липня 2011 у Wayback Machine.] by Danielle MacNevin
• An interactive 2D demonstration [Архівовано 18 березня 2018 у Wayback Machine.]