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

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

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

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

,

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

Эскиз доказательства

Позволять $W\subseteq [0,1]$ — подмножество всех весов, для которых теорема верна. Затем:

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

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

Эскиз доказательства для части 4

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

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

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

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

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

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

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

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

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

Доказательство герметичности

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

Эскиз доказательства $w=1/n$

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

См. также

Ссылки

^ Стромквист, Уолтер; Вудалл, ДР (1985). «Наборы, по которым согласуются несколько мер». Журнал математического анализа и приложений . 108 : 241–248. дои : 10.1016/0022-247x(85)90021-6 .

[stromquistwoodall85-1] Стромквист, Уолтер; Вудалл, ДР (1985). «Наборы, по которым согласуются несколько мер». Журнал математического анализа и приложений . 108 : 241–248. дои : 10.1016/0022-247x(85)90021-6 .

[ 1 ]