Теорема Стромквиста–Вудалла

В этой статье только ссылки на первичные источники . Помогите улучшить эту статью, добавив вторичные или третичные источники . Найти источники:  «Теорема Стромквиста–Вудалла» – новости  · газеты  · книги  · ученый  · JSTOR ( ноябрь 2022 г. ) ( Узнайте, как и когда удалить это сообщение )

Эта статья в значительной степени или полностью основана на одном источнике . Соответствующее обсуждение можно найти на странице обсуждения . Пожалуйста, помогите улучшить эту статью, добавив ссылки на дополнительные источники . Найти источники:  «Теорема Стромквиста–Вудалла» – новости  · газеты  · книги  · ученый  · JSTOR ( ноябрь 2022 г. )

Теорема Стромквиста –Вудолла — это теорема в теории справедливого дележа и меры . Неформально она гласит, что для любого торта, для любых n людей с разными вкусами и для любой доли w существует подмножество торта, которое все люди оценивают ровно в долю w от общей стоимости торта, и его можно разрезать, используя не более чем несколько разрезов. ^[1]${\displaystyle 2n-2}$

Теорема о круглом одномерном торте («пироге»). Формально его можно описать как интервал [0,1], в котором определены две конечные точки. На торте есть n непрерывных мер: ; каждая мера представляет оценки другого человека по подмножествам торта. Теорема гласит, что для каждого веса , существует подмножество , которое все люди оценивают точно в :${\displaystyle V_{1},\ldots ,V_{n}}$${\displaystyle w\in [0,1]}$${\displaystyle C_{w}}$${\displaystyle w}$

${\displaystyle \forall i=1,\ldots ,n:\,\,\,\,\,V_{i}(C_{w})=w}$,

где — объединение не более интервалов. Это означает, что разрезов достаточно для разрезания подмножества . Если торт не круглый (то есть конечные точки не идентифицированы), то может быть объединением до интервалов, в случае, если один интервал смежный с 0, а другой — смежный с 1.${\displaystyle C_{w}}$${\displaystyle n-1}$${\displaystyle 2n-2}$${\displaystyle C_{w}}$${\displaystyle C_{w}}$${\displaystyle n}$

Пусть — подмножество всех весов, для которых теорема верна. Тогда:${\displaystyle W\subseteq [0,1]}$

1. ${\displaystyle 1\in W}$Доказательство: взять (напомним, что меры ценности нормализованы таким образом, что все партнеры оценивают весь торт как 1).${\displaystyle C_{1}:=C}$
2. Если , то также . Доказательство: взять . Если — объединение интервалов в окружности, то — также объединение интервалов.${\displaystyle w\in W}$${\displaystyle 1-w\in W}$${\displaystyle C_{1-w}:=C\smallsetminus C_{w}}$${\displaystyle C_{w}}$${\displaystyle n-1}$${\displaystyle C_{1-w}}$${\displaystyle n-1}$
3. ${\displaystyle W}$является замкнутым множеством . Это легко доказать, поскольку пространство объединений интервалов является компактным множеством при подходящей топологии.${\displaystyle n-1}$
4. Если , то также . Это самая интересная часть доказательства; см. ниже.${\displaystyle w\in W}$${\displaystyle w/2\in W}$

Из 1-4 следует, что . Другими словами, теорема верна для любого возможного веса.${\displaystyle W=[0,1]}$

• Предположим, что это объединение интервалов и что все партнеры оценивают его как ровно .${\displaystyle C_{w}}$${\displaystyle n-1}$${\displaystyle n}$${\displaystyle w}$
• Определим следующую функцию на торте :${\displaystyle f:C\to \mathbb {R} ^{n}}$

${\displaystyle f(t)=(t,t^{2},\ldots ,t^{n})\,\,\,\,\,\,t\in [0,1]}$

• Определить следующие меры :${\displaystyle \mathbb {R} ^{n}}$

${\displaystyle U_{i}(Y)=V_{i}(f^{-1}(Y)\cap C_{w})\,\,\,\,\,\,\,\,\,Y\subseteq \mathbb {R} ^{n}}$

• Обратите внимание, что . Следовательно, для каждого партнера : .${\displaystyle f^{-1}(\mathbb {R} ^{n})=C}$${\displaystyle i}$${\displaystyle U_{i}(\mathbb {R} ^{n})=w}$
• Следовательно, по теореме Стоуна–Тьюки , существует гиперплоскость, которая разрезает два полупространства, такие, что:${\displaystyle \mathbb {R} ^{n}}$${\displaystyle H,H'}$

${\displaystyle \forall i=1,\ldots ,n:\,\,\,\,\,U_{i}(H)=U_{i}(H')=w/2}$

• Определим и . Тогда по определению :${\displaystyle M=f^{-1}(H)\cap C_{w}}$${\displaystyle M'=f^{-1}(H')\cap C_{w}}$${\displaystyle U_{i}}$

${\displaystyle \forall i=1,\ldots ,n:\,\,\,\,\,V_{i}(M)=V_{i}(M')=w/2}$

• Множество имеет связные компоненты (интервалы). Следовательно, его изображение также имеет связные компоненты (одномерные кривые в ).${\displaystyle C_{w}}$${\displaystyle n-1}$${\displaystyle f(C_{w})}$${\displaystyle n-1}$${\displaystyle \mathbb {R} ^{n}}$
• Гиперплоскость, образующая границу между и пересекается в не более чем точках. Следовательно, общее число связных компонент (кривых) в и равно . Следовательно, одна из них должна иметь не более чем компоненты.${\displaystyle H}$${\displaystyle H'}$${\displaystyle f(C_{w})}$${\displaystyle n}$${\displaystyle H\cap f(C_{w})}$${\displaystyle H'\cap f(C_{w})}$${\displaystyle 2n-1}$${\displaystyle n-1}$
• Предположим, что имеет не более компонентов (кривых). Следовательно, имеет не более компонентов (интервалов).${\displaystyle H}$${\displaystyle n-1}$${\displaystyle M}$${\displaystyle n-1}$
• Следовательно, мы можем взять . Это доказывает, что .${\displaystyle C_{w/2}=M}$${\displaystyle w\in W}$

Стромквист и Вудол доказывают, что число является узким, если вес либо иррационален, либо рационален с уменьшенной дробью, такой что .${\displaystyle n-1}$${\displaystyle w}$${\displaystyle r/s}$${\displaystyle s\geq n}$

• Выберите точки, расположенные на окружности на одинаковом расстоянии друг от друга; назовите их .${\displaystyle (n-1)(n+1)}$${\displaystyle P_{1},\ldots ,P_{(n-1)(n+1)}}$
• Определим меры следующим образом. Мера сосредоточена в небольших окрестностях следующих точек: . Таким образом, вблизи каждой точки находится часть меры .${\displaystyle n-1}$${\displaystyle i}$${\displaystyle (n+1)}$${\displaystyle P_{i},P_{i+(n-1)},\ldots ,P_{i+n(n-1)}}$${\displaystyle P_{i+k(n-1)}}$${\displaystyle 1/(n+1)}$${\displaystyle u_{i}}$
• Определим -ю меру как пропорциональную мере длины.${\displaystyle n}$
• Каждое подмножество, консенсусное значение которого равно , должно касаться как минимум двух точек для каждой из первых мер (поскольку значение около каждой отдельной точки равно , что немного меньше требуемого ). Следовательно, оно должно касаться как минимум точек.${\displaystyle 1/n}$${\displaystyle n-1}$${\displaystyle 1/(n+1)}$${\displaystyle 1/n}$${\displaystyle 2(n-1)}$
• С другой стороны, каждое подмножество, консенсусное значение которого равно , должно иметь общую длину (из-за -й меры). Количество «пробелов» между точками равно ; следовательно, подмножество может содержать максимум пробелов.${\displaystyle 1/n}$${\displaystyle 1/n}$${\displaystyle n}$${\displaystyle 1/{\big (}(n+1)(n-1){\big )}}$${\displaystyle n-1}$
• Подмножество консенсуса должно касаться точек, но содержать не более пробелов; следовательно, оно должно содержать не менее интервалов.${\displaystyle 2(n-1)}$${\displaystyle n-1}$${\displaystyle n-1}$

• Справедливое разрезание торта
• Справедливое разделение пирогов
• Точное деление
• Теорема Стоуна–Тьюки