Problém dělení půdy Hill-Beck

Hill-Beck problém sdílení půdy je variantou problému krájení dortu , který navrhl Tad Hill v roce 1983 [1] .

Prohlášení o problému

Území D sousedí s n zeměmi. Každá země odhaduje (svým způsobem) podmnožiny území D . Země si chtějí mezi sebou spravedlivě rozdělit území D , kde „spravedlnost“ znamená poměrné rozdělení . Kromě toho části přidělené každé zemi musí být spojeny a sousedit s přidělenou zemí . Tato geografická omezení odlišují problém od klasického problému krájení dortu .

Formálně musí každá země C i obdržet nesouvislé části území D , které označíme D i , takže části hranice mezi C i a D jsou obsaženy uvnitř . $C_{i}\cup D_{i}$

Nemožnost a možnost

Existují případy, kdy problém nelze vyřešit:

Pokud existuje jeden bod, ve kterém je soustředěna veškerá hodnota pozemku (například „svaté místo“), pak je zřejmé, že území nelze proporcionálně rozdělit. Abychom takovým situacím předešli, předpokládáme, že všechny země přiřadí všem jednotlivým bodům hodnotu 0.
Je-li D čtverec, existují 4 země, které se dotýkají 4 stran tohoto čtverce, a každá země vidí veškerou hodnotu půdy na hranici opačné strany čtverce, pak jakékoli rozdělení, které spojuje, řekněme, severní zemi s požadovaným jižní strana znemožňuje spojení východní země s požadovanou západní stranou náměstí (pokud mluvíme o dvourozměrné rovině). Abychom takovým situacím předešli, předpokládáme, že všechny země předpokládají nulovou hraniční cenu D .

Hill v roce 1983 dokázal, že pokud má každý jednotlivý bod v D hodnotu 0 pro všechny země a hranice D má hodnotu 0 pro všechny země, existuje proporcionální dělení podléhající omezením sousedství. Jeho důkaz se týkal pouze existence, nepředložil žádný algoritmus [1] .

Algoritmus

O čtyři roky později Anatole Beck popsal protokol pro dosažení takového rozdělení [2] . Protokol je v podstatě evolucí protokolu „ poslední minimum “. Protokol umožňuje zemím žádat o části území D , část s nejmenší žádostí dává žadateli a zbytek rozdělí mezi zbývající země. Je potřeba určitá variace, aby se zajistilo, že budou splněna omezení sousedství. $n-1$

Single Connected Territory

Pokud je území D jednoduše připojeno , použije se následující algoritmus:

Najděte Riemannovo zobrazení h , které mapuje D na jednotkovou kružnici , takže pro všechny země je hodnota libovolné kružnice se středem v počátku 0 a hodnota libovolného poloměru od počátku je 0 (existence takového zobrazení h je prokázána počítáním argumentů).
Požádáme každou zemi, aby do kruhu zobrazení jednotek h ( D ) nakreslila disk se středem v počátku (střed disku h ( D )) a hodnotu . To je možné díky skutečnosti, že všechny kružnice se středem v počátku mají hodnotu 0. ${\tfrac {1}{n))$
Najděte disk D 1 s nejmenším poloměrem r 1 .

Existují dva případy.

Jediný vítěz

4. Pokud je D 1 tažena pouze jednou zemí, řekněme C i , pak dáme disk zemi C i . Jeho hodnota pro ostatní země je přísně nižší než , takže zemi C i můžeme přidělit malý kousek navíc vedle přiděleného disku. ${\tfrac {1}{n))$

K tomu nakreslíme sektor spojující D 1 s okrajem kružnice D . Nechte každou zemi (kromě C i ) odříznout tento sektor tak, aby společné hodnoty disků a sektorů nepřesáhly . To je možné díky podmínce, že hodnoty všech poloměrů od počátku jsou 0. Dejme zemi C i spojení D 1 a zkráceného sektoru. ${\tfrac {1}{n))$

Zbývající území je jednoduše připojeno a má hodnotu alespoň pro zbývající země, takže v dělení lze rekurzivně pokračovat od kroku 1. ${\tfrac {n-1}{n))$ $n-1$

Několik vítězů

Pokud si část D 1 vyžádalo k >1 zemí, pak jsou potřeba nějaké sofistikovanější aukce, aby se našla země, které můžeme dát disk a spojovací sektor.

5. Vyberme si libovolnou vítěznou zemi a nazvěme ji deklarátor , C 1 . Nechte ji přidat sektor spojující D 1 s jejím současným územím a nechejte ostatní země odříznout se od tohoto sektoru, takže:

Pro žádnou prohrávající zemi nemá hodnota D 1 plus cut off sektor přednost (to je možné, protože hodnota D 1 pro ně je menší než ). ${\tfrac {1}{n))$ ${\tfrac {1}{n))$
Pro každou vítěznou zemi je hodnota zkráceného sektoru menší než . ${\tfrac {1}{n))$

6. Nechť každá z vítězných zemí navrhne nový poloměr r (menší než jejich původní návrh), takže hodnota odříznuté části sektoru plus kotouč o poloměru r bude oceněna přesně . Volíme nejmenší takový disk D 2 . Opět existují dva případy: ${\tfrac {1}{n))$

Pokud je C 1 jednou ze zemí, které požádaly o D 2 , pak jí jednoduše dáme oblast D 2 (která je o něco menší než původní žádost D 1 ) a spojovací sektor. C 1 souhlasí s tím, že hodnota je , a ostatní země souhlasí s tím, že hodnota není větší než , takže můžeme pokračovat rekurzivně od kroku 1. ${\tfrac {1}{n))$ ${\tfrac {1}{n))$

Jinak C 1 souhlasí s tím, že celková hodnota D 2 a spojovacího sektoru je menší než . Všichni poražení s tím musí také souhlasit, protože D 2 je menší než D 1 . C 1 a všechny ostatní země, které s tím souhlasí, jsou tedy odstraněny ze sady výherců. ${\tfrac {1}{n))$

7. Mezi zbývajícími výherci vybereme nového uchazeče C 2 . Ať přidá další sektor spojující D 2 s aktuálním územím a ostatní země nechají tento sektor zkrátit jako v kroku 5.

Všimněte si, že nyní je území D 2 spojeno se dvěma územími - C 1 a C 2 . To je problém, protože zbytek oblasti je nesoudržný. K vyřešení tohoto problému může C 2 zvolit jiný sektor, jehož délka je menší než 1, aby nenarušil konektivitu [2] . Tento třetí sektor je opět zkrácen všemi zeměmi, jako v kroku 5. V reakci na to je C 2 povinen vrátit část sektoru spojujícího D 2 s C 1 , jehož hodnota se rovná hodnotě přijatého třetího sektoru. sektor.

Řez navrhovaný zemí C2 nyní obsahuje následující části: D2 , sektor délky 1 spojující D2 s C2 a dva krátké sektory , které nedosahují hranice D. Hodnota této konstrukce pro C 2 je rovna , pro poražené je hodnota menší než a hodnota pro ostatní vítěze nepřesahuje . ${\tfrac {1}{n))$ ${\tfrac {1}{n))$ ${\tfrac {1}{n))$

Tento proces pokračuje se zbývajícími vítězi, dokud nezůstane pouze jeden vítěz.

Jistě připojené území

Je-li území D k - spojené s konečným k , lze dělení provést indukcí na k .

Pokud je D připojeno a lze jej rozdělit pomocí protokolu z předchozí části. $k=1,$

Jinak označte vnější hranici D jako B 1 a vnitřní hranice jako . $(k>1)$ ${\displaystyle B_{2},\tečky ,B_{k))$

Najdeme přímku L spojující vnější hranici B 1 s vnitřní hranicí Bk tak, že pro všechny země je hodnota této přímky L rovna 0. To lze provést s ohledem na následující argument. Existuje nespočetné množství párových neprotínajících se čar spojujících B1 a Bk obsažených v D . Ale jejich míra v D je konečná, takže počet čar s kladnou mírou musí být spočetný, a pak existuje přímka s nulovou mírou.

Sada je -připojena. Rozeberme to rekurzivně, pak L libovolně přiřaďme jakékoli zemi, se kterou tato oblast sousedí. To neporušuje spravedlivost rozdělení, protože hodnota L pro všechny země je 0. $D\setminus L$ $(k-1)$

Viz také

Výzva v krájení dortu

Poznámky

↑ 12 Hill , 1983 , s. 438–442.
↑ 12 Beck , 1987 , s. 157–162.

Literatura

Hill TP Určení spravedlivé hranice // The American Mathematical Monthly. - 1983. - T. 90 , čís. 7 . - doi : 10.2307/2975720 . — .
Beck A. Constructing a Fair Border // The American Mathematical Monthly. - 1987. - T. 94 , čís. 2 . - doi : 10.2307/2322417 . — .
Další řešení problému viz Webb WA A Combinatorial Algorithm to Establish a Fair Border // European Journal of Combinatorics. - 1990. - T. 11 , no. 3 . — S. 301–304 . - doi : 10.1016/s0195-6698(13)80129-1 .