Hill-Beck földosztási probléma

A Hill-Beck földmegosztási probléma a Tad Hill által 1983-ban javasolt méltányos tortavágás probléma egy változata [1] .

A probléma leírása

Van egy D terület n országgal szomszédos . Minden ország megbecsüli (a maga módján) a D terület részhalmazait . Az országok igazságosan akarják felosztani a D területet egymás között, ahol a "méltányosság" arányos felosztást jelent . Ezen túlmenően, az egyes országokhoz kiosztott részeknek kapcsolódniuk kell a kijelölt országhoz és szomszédosnak kell lenniük . Ezek a földrajzi korlátok különböztetik meg a problémát a klasszikus méltányos tortavágás problémájától .

Formálisan bármely C i országnak meg kell kapnia a D terület diszjunkt darabjait , amelyeket D i -vel jelölünk úgy, hogy a C i és D közötti határ egyes részei benne legyenek . $C_{i}\cup D_{i}$

Lehetetlenség és lehetőség

Vannak esetek, amikor a probléma nem oldható meg:

Ha van egy pont, ahol a föld minden értéke koncentrálódik (például egy "szent hely"), akkor nyilvánvaló, hogy a területet nem lehet arányosan felosztani. Az ilyen helyzetek elkerülése érdekében feltételezzük, hogy minden ország minden egyes ponthoz 0 értéket rendel.
Ha D egy négyzet, akkor 4 ország érinti a négyzet 4 oldalát, és mindegyik ország az összes földértéket a négyzet ellentétes oldalának határában látja, majd minden olyan eloszlást, amely összeköti mondjuk egy északi országot a kívántnal. déli oldala lehetetlenné teszi a keleti ország összekapcsolását a tér kívánt nyugati oldalával (ha kétdimenziós síkról beszélünk). Az ilyen helyzetek elkerülése érdekében feltételezzük, hogy minden ország nulla határárat feltételez D.

Hill 1983-ban bebizonyította, hogy ha D -ben minden egyes pont értéke 0 minden országra, és D határa minden országra 0, akkor van egy arányos osztás, amelyre szomszédsági megszorítások vonatkoznak. Bizonyítása csak a létezésre vonatkozott, algoritmust nem mutatott be [1] .

Algoritmus

Négy évvel később Anatole Beck leírt egy protokollt egy ilyen felosztás elérésére [2] . Lényegében a protokoll az „ utolsó minimum ” protokoll továbbfejlesztése. A jegyzőkönyv lehetővé teszi az országok számára, hogy a D terület egyes részeire jelentkezzenek, a legkisebb kérelmet benyújtó részt adja a kérelmezőnek, a fennmaradó részt pedig felosztja a fennmaradó országok között. Némi változtatásra van szükség a szomszédsági korlátozások teljesülésének biztosításához. $n-1$

Egyetlen összekapcsolt terület

Ha a D terület egyszerűen össze van kötve , akkor a következő algoritmust használjuk:

Keresse meg azt a h Riemann-leképezést , amely leképezi D -t az egységkörre úgy, hogy minden országra bármely origó középpontú kör értéke 0, és az origó bármely sugarának értéke 0 (egy ilyen h leképezés léte igazolt érvek megszámlálásával).
Megkérünk minden országot, hogy a h ( D ) egység kijelzőkörre rajzoljanak egy lemezt, amelynek középpontja az origóban van (lemez középpontja h ( D )) és egy értéket . Ez annak a ténynek köszönhető, hogy minden origó középpontú körnek 0 az értéke. ${\tfrac {1}{n))$
Keresse meg a legkisebb r 1 sugarú D 1 lemezt .

Két eset van.

Egyetlen győztes

4. Ha D 1 -et csak egy ország rajzolja ki, mondjuk C i , akkor a lemezt C i országnak adjuk . Értéke más országokban szigorúan kisebb, mint , így C i országnak adhatunk egy kis extra darabot a lefoglalt lemez mellett. ${\tfrac {1}{n))$

Ehhez rajzoljunk egy szektort, amely összeköti D 1 -et a D kör határával . Hagyja, hogy minden ország (kivéve C i ) válasszon ki ebből a szektorból, hogy a lemez és a szektor együttes értéke ne haladja meg a . Ez azzal a feltétellel lehetséges, hogy az origótól számított összes sugár értéke 0. Adjuk meg C i országnak a D 1 és a csonka szektor unióját . ${\tfrac {1}{n))$

A fennmaradó terület egyszerűen össze van kötve, és legalább a fennmaradó országok számára értéke van, így a felosztás rekurzív módon folytatható az 1. lépéstől. ${\tfrac {n-1}{n))$ $n-1$

Több nyertes

Ha a D 1 részt k >1 ország kérte , akkor néhány kifinomultabb aukcióra van szükség ahhoz, hogy megtaláljuk azt az országot, amelyhez megadhatjuk a lemezt és a hivatkozási szektort.

5. Válasszunk ki egy tetszőlegesen győztes országot, és nevezzük deklarátornak , C 1 . Kérje meg, hogy adjon hozzá egy szektort, amely összeköti a D 1 -et jelenlegi területével, és hagyja, hogy a többi ország elszakadjon ettől a szektortól, így:

Bármely vesztes ország esetében a D 1 plusz a cut-off szektor értéke nem élvez elsőbbséget (ez lehetséges, mivel a D 1 értéke számukra kisebb, mint ). ${\tfrac {1}{n))$ ${\tfrac {1}{n))$
Bármely nyertes ország esetében a csonka szektor értéke kisebb, mint . ${\tfrac {1}{n))$

6. Minden nyertes ország javasoljon új r sugarat (kisebbet, mint az eredeti javaslat), így a szektor levágott részének és az r sugarú korongnak az értéke pontosan . A legkisebb ilyen D 2 lemezt választjuk . Ismét két eset van: ${\tfrac {1}{n))$

Ha C 1 a D 2 -re jelentkező országok egyike , akkor egyszerűen megadjuk neki a D 2 területet (ami valamivel kisebb, mint az eredeti D 1 kérelem ) és a csatlakozó szektort. C 1 egyetért azzal, hogy az érték , és más országok egyetértenek abban, hogy az érték nem nagyobb, mint , így folytathatjuk rekurzív módon az 1. lépéstől. ${\tfrac {1}{n))$ ${\tfrac {1}{n))$

Ellenkező esetben C 1 egyetért azzal, hogy D 2 és az összekötő szektor összértéke kisebb, mint . Ezzel minden vesztesnek egyet kell értenie, mivel D 2 kisebb, mint D 1 . Így a C 1 és minden más ország, amely egyetért ezzel, kikerül a nyertesek sorából. ${\tfrac {1}{n))$

7. A fennmaradó nyertesek közül új C 2 pályázót választunk . Adjon hozzá egy másik szektort, amely összeköti a D 2 -t az aktuális területtel, és hagyja, hogy más országok csonkolják ezt a szektort, mint az 5. lépésben.

Jegyezzük meg, hogy most a D 2 terület két területtel van összekötve - C 1 és C 2 . Ez probléma, mivel a terület többi részét inkoherenssé teszi. A probléma megoldására C 2 választhat egy másik szektort, amelynek hossza kisebb, mint 1, hogy ne szakítsa meg a kapcsolatot [2] . Ezt a harmadik szektort ismét minden ország csonkolja, mint az 5. lépésben. Válaszul a C 2 -nek vissza kell adnia a D 2 -t a C 1 -gyel összekötő szektor egy részét , amelynek értéke megegyezik a fogadott harmadik értékével. ágazat.

A C 2 ország által javasolt vágás most a következő részeket tartalmazza: D 2 , egy 1 hosszúságú szektor, amely összeköti a D 2 -t a C 2 -vel , és két rövid szektor, amelyek nem érik el a D határát . Ennek a konstrukciónak az értéke C 2 -re egyenlő , a veszteseknél az érték kisebb, mint , és a többi nyertesnél nem haladja meg a -t . ${\tfrac {1}{n))$ ${\tfrac {1}{n))$ ${\tfrac {1}{n))$

Ez a folyamat a fennmaradó nyertesekkel folytatódik, amíg csak egy nyertes marad.

Biztosan összekapcsolt terület

Ha a D terület k -összekötve véges k -vel, akkor az osztás k -on történő indukcióval elvégezhető .

Ha D csatlakoztatva van és felosztható az előző szakasz protokolljával. $k=1,$

Ellenkező esetben jelölje D külső határát B 1 - nek , belső határait pedig . $(k>1)$ ${\displaystyle B_{2},\dots ,B_{k))$

Megtaláljuk a B 1 külső határt a B k belső határral összekötő L egyenest úgy, hogy ennek az L vonalnak az értéke minden ország esetében 0. Ezt a következő érv alapján tehetjük meg. Megszámlálhatatlan számú páronként nem metsző egyenes van, amely összeköti a B 1 -et és a B k -t D -ben . De a mértékük D -ben véges, tehát a pozitív mértékû sorok számának megszámlálhatónak kell lennie, és akkor van egy nulla mértékû egyenes.

A készlet -csatlakozik . Bontsuk fel rekurzív módon, majd rendeljük tetszőlegesen L -t bármely országhoz, amellyel ez a terület határos. Ez nem sérti az osztás igazságosságát, mivel az L értéke minden országra 0. $D\setminus L$ $(k-1)$

Lásd még

Fair Cake Cutting Challenge

Jegyzetek

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

Irodalom

Hill TP Determining a Fair Border // The American Mathematical Monthly. - 1983. - T. 90 , sz. 7 . - doi : 10.2307/2975720 . — .
Beck A. Egy tisztességes határ felépítése // The American Mathematical Monthly. - 1987. - T. 94 , sz. 2 . - doi : 10.2307/2322417 . — .
A probléma egyéb megoldásaiért lásd: Webb WA A Combinatorial Algorithm to Establish a Fair Border // European Journal of Combinatorics. - 1990. - T. 11 , sz. 3 . – S. 301–304 . - doi : 10.1016/s0195-6698(13)80129-1 .