Stromquist-Woodalls sats

Stromquist -Woodall-satsen är en teorem inom rättvis division och måttteori . Informellt står det att det för vilken kaka som helst, för alla n personer med olika smaker och för vilken bråkdel r som helst, det finns en delmängd av kakan som alla människor värderar till exakt en bråkdel r av det totala kakvärdet.

Satsen handlar om en cirkulär 1-dimensionell kaka (en "paj"). Formellt kan det beskrivas som intervallet [0,1] i vilket de två ändpunkterna identifieras. Det finns n kontinuerliga mått över kakan: $V_{1},\ldots ,V_{n}$ ; varje mått representerar värderingen av en annan person över delmängder av kakan.

Satsen säger att det för varje vikt $w\in [0,1]$ finns en delmängd $C_{w}$ , som är en union av högst $n-1$ intervall, som alla människor värderar exakt $w$ :

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

Bevisskiss

$W\subseteq [0,1]$ är delmängden av alla vikter för vilka satsen är sann. Sedan:

$1\in W$ . Bevis: ta $C_{1}:=C$ (kom ihåg att värdemåtten är normaliserade så att alla partners värderar hela kakan som 1).
Om $w\in W$ , då också $1-w\in W$ . Bevis: ta $C_{1-w}:=C\smallsetminus C_{w}$ . Om $C_{w}$ är en förening av $n-1$ intervall i en cirkel, så är $C_{1-w}$ också en union av $n-1$ intervall.
$W$ är en sluten uppsättning . Detta är lätt att bevisa, eftersom utrymmet för föreningar med $n-1$ intervall är en kompakt uppsättning under en lämplig topologi.
Om $w\in W$ , då även $w/2\in W$ . Detta är den mest intressanta delen av beviset; se nedan.

Från 1-4 följer att $W=[0,1]$ . Med andra ord, satsen är giltig för alla möjliga vikter.

Korrekturskiss för del 4

Antag att $C_{w}$ är en förening av $n-1$ intervall och att alla $n$ partner värderar det som exakt $w$ .
Definiera följande funktion på kakan, $f:C\to \mathbb {R} ^{n}$ :

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

Definiera följande mått på $\mathbb {R} ^{n}$ :

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

Observera att $f^{-1}(\mathbb {R} ^{n})=C$ . Därför, för varje partner $i$ : $U_{i}(\mathbb {R} ^{n})=w$ .
Därför finns det enligt Stone–Tukey-satsen ett hyperplan som skär $\mathbb {R} ^{n}$ till två halvrum, $H,H'$ , Så att:

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

Definiera $M=f^{-1}(H)\cap C_{ w}$ och $M'=f^{-1}(H')\cap C_{w}$ . Sedan, enligt definitionen av $U_{i}$ :

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

Uppsättningen $C_{w}$ har $n-1$ anslutna komponenter (intervall). Därför har dess bild $f(C_{w})$ också $n-1$ anslutna komponenter (1-dimensionella kurvor i $\mathbb {R} ^{n}$ ).
Hyperplanet som bildar gränsen mellan $H$ och $H'$ skär $f(C_{w})$ i högst $n$ punkter. Det totala antalet anslutna komponenter (kurvor) i $H\cap f(C_{w})$ och $H'\cap f. (C_{w})$ är $2n-1$ . Därför måste en av dessa ha högst $n-1$ komponenter.
Antag att det är $H$ som har högst $n-1$ komponenter (kurvor). Därför $M$ högst $n-1$ komponenter (intervall).
Därför kan vi ta $C_{w/2}=M$ . Detta bevisar att $w\in W$ .

Täthetssäker

Stromquist och Woodall bevisar att talet $n-1$ är snävt om vikten $w$ är antingen irrationell eller rationell med en reducerad bråkdel $r/s$ så att $s\geq n$ .

Bevisskiss för $w=1/n$

Välj $(n-1)(n+1)$ jämnt fördelade punkter längs cirkeln; kalla dem $P_{1},\ldots ,P_{(n-1)(n+1)}$ .
Definiera $n-1$ mått på följande sätt. Mått ${\displaystyle i} är koncentrerat i små$ $P_{i},P_{i+(n-1)},\ldots ,P_{i+n(n-1)}$ med följande $(n+1)$ punkter: . Så nära varje punkt ${\displaystyle P_{i+k(n-1)}} ,$ finns det en bråkdel $1/(n+1 )$ av måttet $u_{i}$ .
Definiera $n$ -:e måttet som proportionellt mot längdmåttet.
Varje delmängd vars konsensusvärde är $1/n$ , måste röra vid minst två punkter för var och en av de första $n-1$ måtten (eftersom värdet nära varje enskild punkt är $1/(n+1)$ vilket är något mindre än det erforderliga $1/n$ ). Därför måste den vidröra minst $2(n-1)$ punkter.
Å andra sidan måste varje delmängd vars konsensusvärde är $1/n$ , ha total längd $1/n$ (på grund av det $n$ -te måttet) . Antalet "luckor" mellan punkterna är $1/{\big (}(n+1)(n-1){\big )}$ ; därför kan delmängden innehålla högst $n-1$ luckor.
Konsensusdelmängden måste röra $2(n-1)$ punkter men innehålla högst $n-1$ luckor; därför måste den innehålla minst $n-1$ intervall.

Se även