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

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

Твердження висловив Гуго Штейнгауз, а довів Стефан Банах (у розмірності 3, не припускаючи автоматичного перенесення теореми на 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^{\circ }$, він виявиться на тому ж місці, але «догори ногами», так що $p(180)⩽1/2$. За теоремою про проміжне значення повинен існувати кут, за якого $p(\alpha )=1/2$. Розріз з цим кутом нахилу ножа поділить навпіл обидва млинці одночасно.

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

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

Нехай $A_1,A_2,\dots ,A_n$ означають Шаблон:Mvar об'єктів, які ми хочемо одночасно розділити надвоє. Нехай Шаблон:Mvar буде одиничною [[Гіперсфера|Шаблон:Math-сферою]], вкладеною в Шаблон:Mvar-вимірний евклідів простір ${ℝ}^n$ і з центром у початку координат. Для кожної точки Шаблон:Mvar на поверхні сфери Шаблон:Mvar ми можемо визначити Шаблон:Не перекладено орієнтованих афінних гиперплощин (які не обов'язково проходять через центр 0), перпендикулярних (нормалі) до вектора від початку координат у Шаблон:Mvar, з «додатним боком» кожної гіперплощини, визначеним як бік, на який вказує вектор (тобто, це вибір орієнтації). За теоремою про проміжне значення будь-яке сімейство таких гіперплощин містить принаймні одну гіперплощину, яка ділить навпіл обмежений об'єкт $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 неперервна. За теоремою Борсука — Уляма існують Шаблон:Не перекладено Шаблон: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 описав алгоритм для спеціального, розділеного випадку. Тут усі червоні точки лежать по один бік від деякої прямої, а всі сині точки — по інший бік від тієї ж прямої. В цій ситуації є єдине розрізання бутерброда з шинкою, яке Мегіддо міг знайти за лінійний час. Пізніше Шаблон:Нп і Ваупотич (Roman Waupotitsch)Шаблон:Sfn дали алгоритм для загального двовимірного випадку. Час роботи їхнього алгоритму становить $O(n\log n)$, де символ Шаблон:Mvar означає O-велике. Нарешті, Ло і ШтайгерШаблон:Sfn знайшли оптимальний алгоритм з часом роботи Шаблон:Math. Цей алгоритм поширили на високі розмірності Ло, Шаблон:Нп і ШтайгерШаблон:Sfn і час роботи алгоритму дорівнює $o(n^{d-1})$. Якщо дано Шаблон:Mvar точок у загальному положенні в Шаблон:Mvar-вимірному просторі, алгоритм обчислює Шаблон:Math-вимірну гіперплощину, яка має рівну кількість точок у кожному з напівпросторів, тобто дає розрізання бутерброда з шинкою для даних точок. Якщо Шаблон:Mvar міститься у вхідних даних, то не очікується ніякого алгоритму поліноміального часу, оскільки в разі, коли точки лежать на кривій моментів, задача стає еквівалентною розрізанню намиста, яка Шаблон:Не перекладено .

Алгоритм лінійного часу, який ділить двох опуклі багатокутники, що не перетинаються, описав Шаблон:НпШаблон: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)$ .

Див. також

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

Література

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

Посилання

• Weisstein, Eric W. Ham Sandwich Theorem (англ.)
• ham sandwich theorem Шаблон:Webarchive on the Earliest known uses of some of the words of mathematics Шаблон:Webarchive
• Ham Sandwich Cuts Шаблон:Webarchive by Danielle MacNevin
• An interactive 2D demonstration Шаблон:Webarchive