Теорема о разрезании бутерброда (или трех тел) плоскостью
Ham sandwich theorem
Теорема о "бутерброде": доказывает возможность одновременного деления n объектов в n-мерном пространстве плоскостью пополам. Математика, геометрия, Банах.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Теорема о том, что любые три объекта в пространстве могут быть одновременно рассечены плоскостью.
Theorem that any three objects in space can be simultaneously bisected by a plane
В математической теории меры для каждого положительного целого числа n теорема о "сэндвиче с ветчиной" утверждает, что для n измеримых "объектов" в n-мерном евклидовом пространстве существует гиперплоскость размерности (n − 1), которая рассекает каждый из них пополам (относительно их меры, например, объема). Это возможно даже в случае перекрытия объектов. Теорема была предложена Хьюго Стейнхаусом и доказана Стефаном Банахом (явно в размерности 3, без формулирования теоремы для n-мерного случая), а позднее была названа теоремой Стоуна — Туки в честь Артура Х. Стоуна и Джона Туки.
In mathematical measure theory, for every positive integer n the ham sandwich theorem states that given n measurable "objects" in n dimensional Euclidean space, it is possible to divide each one of them in half (with respect to their measure, e. g. volume) with a single (n − 1) dimensional hyperplane. This is even possible if the objects overlap. It was proposed by Hugo Steinhaus and proved by Stefan Banach (explicitly in dimension 3, without taking the trouble to state the theorem in the n dimensional case), and also years later called the Stone–Tukey theorem after Arthur H. Stone and John Tukey.
Именование
Теорема о бутерброде с ветчиной получила свое название от случая, когда 1=n = 3 и три объекта, которые необходимо разделить пополам, являются ингредиентами этого бутерброда. Источники расходятся во мнениях относительно того, какие именно три ингредиента имеются в виду: два ломтика хлеба и кусок ветчины, хлеб, сыр и ветчина, или хлеб, масло и ветчина. В двух измерениях теорема известна как теорема о блине, что отражает плоскую форму двух объектов, которые необходимо разделить линией.
The ham sandwich theorem takes its name from the case when 1=n = 3 and the three objects to be bisected are the ingredients of a ham sandwich. Sources differ on whether these three ingredients are two slices of bread and a piece of ham , bread and cheese and ham , or bread and butter and ham In two dimensions, the theorem is known as the pancake theorem to refer to the flat nature of the two objects to be bisected by a line .
История
Согласно , самая ранняя известная работа о теореме о бутерброде с ветчиной, а именно случай 1 = n = 3, касающийся деления трех тел плоскостью на две равные части, — это заметка 1938 года в польском математическом журнале. Статья Бейера и Зардецкого включает перевод этой заметки, в которой постановка задачи приписывается Уго Штейнхаусу, а Стефан Банах назван первым, кто решил задачу, сведя её к теореме Борсука — Улама. В заметке задача сформулирована двумя способами: во-первых, формально: «Всегда ли можно разрезать три произвольно расположенных тела плоскостью так, чтобы они разделились пополам?», а во-вторых, неформально: «Можно ли положить кусок ветчины под мясорубку так, чтобы мясо, кость и жир были разрезаны пополам?». Далее в заметке приводится доказательство теоремы. Более современным источником является , который послужил основой для названия «теорема Стоуна — Туки». В этой статье доказана n-мерная версия теоремы в более общем контексте, включающем меры. В статье случай 1 = n = 3 приписывается Станиславу Уламу, основываясь на информации, полученной от рецензента; однако утверждается, что это неверно, учитывая вышеупомянутую заметку, хотя «Улам внес фундаментальный вклад, предложив» теорему Борсука — Улама.
According to , the earliest known paper about the ham sandwich theorem, specifically the 1=n = 3 case of bisecting three solids with a plane, is a 1938 note in a Polish mathematics journal Beyer and Zardecki's paper includes a translation of this note, which attributes the posing of the problem to Hugo Steinhaus, and credits Stefan Banach as the first to solve the problem, by a reduction to the Borsuk–Ulam theorem. The note poses the problem in two ways: first, formally, as "Is it always possible to bisect three solids, arbitrarily located, with the aid of an appropriate plane?" and second, informally, as "Can we place a piece of ham under a meat cutter so that meat, bone, and fat are cut in halves?" The note then offers a proof of the theorem. A more modern reference is , which is the basis of the name "Stone–Tukey theorem". This paper proves the n dimensional version of the theorem in a more general setting involving measures. The paper attributes the 1=n = 3 case to Stanislaw Ulam, based on information from a referee; but claim that this is incorrect, given the note mentioned above, although "Ulam did make a fundamental contribution in proposing" the Borsuk–Ulam theorem.
Двумерный вариант: проверка с помощью вращающегося ножа
Двумерный вариант теоремы (также известный как теорема о блинах) может быть доказан с помощью аргумента, встречающегося в литературе о справедливом разрезании торта (см., например, процедуру вращающегося ножа Робертсона — Уэбба). Для каждого угла α прямая линия ("нож") с углом α может рассечь блинчик №1. Чтобы увидеть это, переместите [параллельно сдвиньте] прямую линию с углом α из точки A в точку B; доля блинчика №1, покрытая линией, непрерывно меняется от 0 до 1, следовательно, по теореме о промежуточном значении она должна где-то на этом пути быть равна 1/2. Возможно, целый ряд параллельных переносов нашей линии дают долю 1/2; в этом случае каноническим выбором будет выбор среднего из всех таких переносов. Когда нож находится под углом 0, он также разрезает блинчик №2, но части, вероятно, будут неравными (если нам повезет, и части окажутся равными, то мы закончили). Определим "положительную" сторону ножа как сторону, на которой доля блинчика №2 больше. Теперь поворачиваем нож и перемещаем его, как описано выше. Когда угол равен α, обозначим через f(α) долю блинчика №2 на положительной стороне ножа. Изначально функция f(α) непрерывна, поскольку небольшие изменения угла приводят к небольшим изменениям положения ножа. Когда нож находится под углом 180, нож перевернут, поэтому f(180) = 0. По теореме о промежуточном значении, должен существовать угол, при котором рассечение под этим углом одновременно рассекает оба блинчика пополам.
The two dimensional variant of the theorem (also known as the pancake theorem) can be proved by an argument which appears in the fair cake cutting literature (see e. g. Robertson–Webb rotating knife procedure). For each angle , a straight line ("knife") of angle can bisect pancake #1. To see this, translate [move parallelly] a straight line of angle from to ; the fraction of pancake #1 covered by the line changes continuously from 0 to 1, so by the intermediate value theorem it must be equal to 1/2 somewhere along the way. It is possible that an entire range of translations of our line yield a fraction of 1/2; in this case, it is a canonical choice to pick the middle one of all such translations. When the knife is at angle 0, it also cuts pancake #2, but the pieces are probably unequal (if we are lucky and the pieces are equal, we are done). Define the 'positive' side of the knife as the side in which the fraction of pancake #2 is larger. We now turn the knife, and translate it as described above. When the angle is , define as the fraction of pancake #2 at the positive side of the knife. Initially The function is continuous, since small changes in the angle lead to small changes in the position of the knife. When the knife is at angle 180, the knife is upside down, so By the intermediate value theorem, there must be an angle in which Cutting at that angle bisects both pancakes simultaneously.
Измерение теоретических версий
В теории меры доказаны две более общие формы теоремы о ветчинном сэндвиче. Обе версии касаются бисекции n подмножеств X₁, X₂, …, Xₙ общего множества X, где X имеет внешнюю меру Каратэодори и каждое Xᵢ имеет конечную внешнюю меру. Их первая общая формулировка следующая: для любой непрерывной вещественной функции f существует точка p на n-сфере Sⁿ и вещественное число s₀, такие что поверхность f(p, x) = s₀ делит X на области, где f(p, x) < s₀ и f(p, x) > s₀, имеющие равную меру, и одновременно делит внешнюю меру множеств X₁, X₂, …, Xₙ пополам. Доказательство снова сводится к теореме Борсука — Улама. Эта теорема обобщает стандартную теорему о ветчинном сэндвиче, позволяя f(s, x) = s₁x₁ + … + sₙxₙ. Их вторая формулировка следующая: для любых n + 1 измеримых функций f₀, f₁, …, fₙ на X, которые линейно независимы на любом подмножестве X положительной меры, существует линейная комбинация f = a₀f₀ + a₁f₁ + … + aₙfₙ такая, что поверхность f(x) = 0, делящая X на области, где f(x) < 0 и f(x) > 0, одновременно делит внешнюю меру множеств X₁, X₂, …, Xₙ пополам. Эта теорема обобщает стандартную теорему о ветчинном сэндвиче, полагая f₀(x) = 1 и полагая, что fᵢ(x) для i > 0 является i-й координатой x.
In measure theory, proved two more general forms of the ham sandwich theorem. Both versions concern the bisection of n subsets X1, X2, , Xn of a common set X, where X has a Carathéodory outer measure and each Xi has finite outer measure. Their first general formulation is as follows: for any continuous real function , there is a point p of the n sphere S^(n) and a real number s0 such that the surface 1=f(p,x) = s0 divides X into f(p,x) < s0 and f(p,x) > s0 of equal measure and simultaneously bisects the outer measure of X1, X2, , Xn. The proof is again a reduction to the Borsuk Ulam theorem. This theorem generalizes the standard ham sandwich theorem by letting 1=f(s,x) = s1x1 + + snxn. Their second formulation is as follows: for any n + 1 measurable functions f0, f1, , fn over X that are linearly independent over any subset of X of positive measure, there is a linear combination 1=f = a0f0 + a1f1 + + anfn such that the surface 1=f(x) = 0, dividing X into f(x) < 0 and f(x) > 0, simultaneously bisects the outer measure of X1, X2, , Xn. This theorem generalizes the standard ham sandwich theorem by letting 1=f0(x) = 1 and letting fi(x), for i > 0, be the i th coordinate of x.
Обобщения
Первоначальная теорема работает для не более чем n коллекций, где n — число измерений. Чтобы разделить более чем n коллекций, не переходя в пространство большей размерности, можно использовать вместо гиперплоскости алгебраическую поверхность степени k, то есть (n-1)-мерную поверхность, заданную полиномиальной функцией степени k:
The original theorem works for at most n collections, where n is the number of dimensions. To bisect a larger number of collections without going to higher dimensions, one can use, instead of a hyperplane, an algebraic surface of degree k, i. e., an (n−1)–dimensional surface defined by a polynomial function of degree k:
Для заданных мер в n-мерном пространстве существует алгебраическая поверхность степени k, которая разделяет их все пополам. Это обобщение доказывается путем отображения n-мерной плоскости в d-мерную плоскость, а затем применения исходной теоремы. Например, для n = 2 и k = 2, двумерная плоскость отображается в пятимерную плоскость следующим образом:
Given measures in an n–dimensional space, there exists an algebraic surface of degree k which bisects them all. This generalization is proved by mapping the n–dimensional plane into a dimensional plane, and then applying the original theorem. For example, for 1=n = 2 and 1=k = 2, the 2–dimensional plane is mapped to a 5–dimensional plane via: