Stromquist – Woodallova věta - Stromquist–Woodall theorem

The Stromquist – Woodallova věta je věta v spravedlivé rozdělení a teorie míry. Neformálně se říká, že pro každý dort, pro jakýkoli n lidé s různým vkusem a pro jakýkoli zlomek r, existuje podmnožina dortu, kterou si všichni váží přesně za zlomek r z celkové hodnoty dortu.^[1]

Věta je o kruhovém jednorozměrném koláči („koláč“). Formálně to lze popsat jako interval [0,1], ve kterém jsou identifikovány dva koncové body. Existují n průběžná opatření přes dort: ${ displaystyle V_ {1}, ldots, V_ {n}}$ ; každé opatření představuje ocenění jiné osoby nad podmnožinami dortu.

Věta říká, že pro každou váhu ${ displaystyle w v [0,1]}$ , existuje podmnožina ${ displaystyle C_ {w}}$ , což je nanejvýš svazek ${ displaystyle n-1}$ intervaly, které všichni lidé přesně ocení ${ displaystyle w}$ :

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

Důkazní skica

${ displaystyle W subseteq [0,1]}$ být podmnožinou všech vah, pro které je věta pravdivá. Pak:

${ displaystyle 1 ve W}$ . Důkaz: vezměte si ${ displaystyle C_ {1}: = C}$ (připomeňte, že hodnotové míry jsou normalizovány tak, že všichni partneři oceňují celý koláč jako 1).
Li ${ displaystyle w in W}$ , pak také ${ displaystyle 1-w ve W}$ . Důkaz: vezměte si ${ displaystyle C_ {1-w}: = C smallsetminus C_ {w}}$ . Li ${ displaystyle C_ {w}}$ je svazek ${ displaystyle n-1}$ intervaly v kruhu ${ displaystyle C_ {1-t}}$ je také svazkem ${ displaystyle n-1}$ intervaly.
${ displaystyle W}$ je uzavřená sada. To je snadné dokázat, protože prostor odborů ${ displaystyle n-1}$ intervaly je a kompaktní sada pod vhodnou topologií.
Li ${ displaystyle w in W}$ , pak také ${ displaystyle w / 2 in W}$ . Toto je nejzajímavější část důkazu; viz. níže.

Z 1-4 to vyplývá ${ displaystyle W = [0,1]}$ . Jinými slovy, věta je platná pro každý možná hmotnost.

Důkazní skica pro část 4

Předpokládat, že ${ displaystyle C_ {w}}$ je svazek ${ displaystyle n-1}$ intervaly a to všechno ${ displaystyle n}$ partneři to hodnotí přesně ${ displaystyle w}$ .
Definujte následující funkci na dortu, ${ displaystyle f: C to mathbb {R} ^ {n}}$ :

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

Definujte následující opatření na ${ displaystyle mathbb {R} ^ {n}}$ :

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

Všimněte si, že ${ displaystyle f ^ {- 1} ( mathbb {R} ^ {n}) = C}$ . Proto pro každého partnera ${ displaystyle i}$ : ${ displaystyle U_ {i} ( mathbb {R} ^ {n}) = w}$ .
Proto, tím Stone – Tukeyova věta, existuje hyperrovina, která řeže ${ displaystyle mathbb {R} ^ {n}}$ do dvou poloprostorů, ${ displaystyle H, H '}$ takové, že:

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

Definovat ${ displaystyle M = f ^ {- 1} (H) čepice C_ {w}}$ a ${ displaystyle M '= f ^ {- 1} (H') cap C_ {w}}$ . Poté, podle definice ${ displaystyle U_ {i}}$ :

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

Sada ${ displaystyle C_ {w}}$ má ${ displaystyle n-1}$ připojené komponenty (intervaly). Proto jeho obraz ${ displaystyle f (C_ {w})}$ také má ${ displaystyle n-1}$ připojené komponenty (jednorozměrné křivky v ${ displaystyle mathbb {R} ^ {n}}$ ).
Nadrovina, která tvoří hranici mezi ${ displaystyle H}$ a ${ displaystyle H '}$ protíná se ${ displaystyle f (C_ {w})}$ maximálně ${ displaystyle n}$ bodů. Celkový počet připojených komponent (křivek) v ${ displaystyle H cap f (C_ {w})}$ a ${ displaystyle H ' cap f (C_ {w})}$ je ${ displaystyle 2n-1}$ . Proto jeden z nich musí mít nanejvýš ${ displaystyle n-1}$ komponenty.
Předpokládejme, že je ${ displaystyle H}$ to má nanejvýš ${ displaystyle n-1}$ komponenty (křivky). Proto, ${ displaystyle M}$ má nanejvýš ${ displaystyle n-1}$ komponenty (intervaly).
Proto můžeme vzít ${ displaystyle C_ {w / 2} = M}$ . To dokazuje ${ displaystyle w in W}$ .

Důkaz těsnosti

Stromquist a Woodall toto číslo dokazují ${ displaystyle n-1}$ je těsný, pokud je váha ${ displaystyle w}$ je buď iracionální, nebo racionální se sníženým zlomkem ${ displaystyle r / s}$ takhle ${ displaystyle s geq n}$ .

Důkazní skica pro ${ displaystyle w = 1 / n}$

Vybrat ${ displaystyle (n-1) (n + 1)}$ rovnoměrně rozmístěné body podél kružnice; zavolej jim ${ displaystyle P_ {1}, ldots, P _ {(n-1) (n + 1)}}$ .
Definovat ${ displaystyle n-1}$ opatření následujícím způsobem. Opatření ${ displaystyle i}$ je soustředěna v malých čtvrtích následujících oblastí ${ displaystyle (n + 1)}$ body: ${ displaystyle P_ {i}, P_ {i + (n-1)}, ldots, P_ {i + n (n-1)}}$ . Takže blízko každého bodu ${ displaystyle P_ {i + k (n-1)}}$ , existuje zlomek ${ displaystyle 1 / (n + 1)}$ opatření ${ displaystyle u_ {i}}$ .
Definujte ${ displaystyle n}$ -té opatření jako úměrné délce opatření.
Každá podmnožina, jejíž konsenzuální hodnota je ${ displaystyle 1 / n}$ , se musí dotknout alespoň dvou bodů pro každý z prvních ${ displaystyle n-1}$ míry (protože hodnota poblíž každého jednotlivého bodu je ${ displaystyle 1 / (n + 1)}$ což je o něco méně, než je požadováno ${ displaystyle 1 / n}$ ). Proto se musí alespoň dotýkat ${ displaystyle 2 (n-1)}$ bodů.
Na druhou stranu každá podmnožina, jejíž konsenzuální hodnota je ${ displaystyle 1 / n}$ , musí mít celkovou délku ${ displaystyle 1 / n}$ (kvůli ${ displaystyle n}$ -té opatření). Počet "mezer" mezi body je ${ displaystyle 1 / { big (} (n + 1) (n-1) { big)}}$ ; podskupina tedy může obsahovat maximálně ${ displaystyle n-1}$ mezery.
Podmnožina konsensu se musí dotknout ${ displaystyle 2 (n-1)}$ body, ale obsahují maximálně ${ displaystyle n-1}$ mezery; proto musí obsahovat alespoň ${ displaystyle n-1}$ intervaly.