Hill-Beckin maanjakoongelma

Hill-Beckin maanjakoongelma on muunnelma Tad Hillin vuonna 1983 [1] ehdottamasta reilun kakun leikkaamisen ongelmasta .

Ongelman selvitys

Alue D on n maan vieressä . Jokainen maa arvioi (omalla tavallaan) alueen D osajoukkoja . Maat haluavat jakaa alueen D tasapuolisesti keskenään, missä "reiluus" tarkoittaa suhteellista jakoa . Lisäksi kullekin maalle allokoitujen osien tulee olla yhteydessä ja vierekkäin allokoidun maan kanssa . Nämä maantieteelliset rajoitukset erottavat ongelman klassisesta reilun kakun leikkaamisen ongelmasta .

Muodollisesti minkä tahansa maan C i täytyy vastaanottaa epäyhtenäisiä paloja alueesta D , jota merkitsemme D i :llä siten, että osat C i :n ja D :n välisestä rajasta ovat sisällä . $C_{i}\cup D_{i}$

Mahdottomuus ja mahdollisuus

On tapauksia, joissa ongelmaa ei voida ratkaista:

Jos on yksi kohta, johon kaikki maan arvo on keskittynyt (esimerkiksi "pyhä paikka"), on selvää, että aluetta ei voida jakaa suhteellisesti. Tällaisten tilanteiden estämiseksi oletetaan, että kaikki maat antavat arvon 0 kaikille yksittäisille pisteille.
Jos D on neliö, on 4 maata, jotka koskettavat neliön neljää sivua, ja jokainen maa näkee kaiken maa-arvon neliön vastakkaisen puolen rajalla, sitten minkä tahansa jakauman, joka yhdistää esimerkiksi pohjoisen maan haluttuun eteläpuoli tekee mahdottomaksi yhdistää itämaata aukion haluttuun länsipuolelle (jos puhumme kaksiulotteisesta tasosta). Tällaisten tilanteiden estämiseksi oletetaan, että kaikki maat olettavat nollahinnaksi rajalla D .

Hill osoitti vuonna 1983, että jos D :n jokaisen yksittäisen pisteen arvo on 0 kaikille maille ja D :n rajan arvo on 0 kaikille maille, on olemassa suhteellinen jako, johon liittyy läheisyysrajoituksia. Hänen todisteensa koski vain olemassaoloa, hän ei esittänyt mitään algoritmia [1] .

Algoritmi

Neljä vuotta myöhemmin Anatole Beck kuvasi protokollan tällaisen jaon saavuttamiseksi [2] . Pohjimmiltaan protokolla on " viimeisen minimin " protokollan kehitys. Pöytäkirja sallii maiden hakea alueen D osia , antaa hakijalle vähiten hakeneen osan ja jakaa loput muiden maiden kesken. Jonkin verran vaihtelua tarvitaan, jotta varmistetaan, että läheisyysrajoitukset täyttyvät. $n-1$

Single Connected Territory

Jos alue D yhdistetään yksinkertaisesti , käytetään seuraavaa algoritmia:

Etsi Riemannin kartoitus h , joka kuvaa D :n yksikköympyrään siten, että kaikissa maissa minkä tahansa origossa olevan ympyrän arvo on 0 ja minkä tahansa säteen arvo origosta on 0 (sellaisen kuvauksen h olemassaolo on todistettu laskemalla argumentteja).
Pyydämme jokaista maata piirtämään yksikön näytön ympyrään h ( D ) levyn, jonka keskipiste on origossa (levyn keskipiste h ( D )) ja arvon . Tämä on mahdollista johtuen siitä, että kaikkien origoon keskitettyjen ympyröiden arvo on 0. ${\tfrac {1}{n))$
Etsi levy D 1 , jonka säde on pienin r 1 .

Tapauksia on kaksi.

Yksittäinen voittaja

4. Jos D 1 piirtää vain yksi maa, sano C i , annamme levyn maalle C i . Sen arvo muille maille on ehdottomasti pienempi kuin , joten voimme antaa maalle C i pienen ylimääräisen palan varatun levyn viereen. ${\tfrac {1}{n))$

Piirretään tätä varten sektori, joka yhdistää D 1 :n ympyrän D reunaan . Anna jokaisen maan (muu kuin C i ) katkaista tämän sektorin, jotta levyn ja sektorin yhteisarvot eivät ylitä arvoa . Tämä on mahdollista sillä ehdolla, että kaikkien origon säteiden arvot ovat 0. Annetaan maalle C i D 1 : n ja katkaistun sektorin liitto . ${\tfrac {1}{n))$

Jäljelle jäävä alue on yksinkertaisesti yhdistetty ja sillä on arvo ainakin jäljellä oleville maille, joten jakoa voidaan jatkaa rekursiivisesti vaiheesta 1. ${\tfrac {n-1}{n))$ $n-1$

Useita voittajia

Jos osaa D 1 on pyytänyt k > 1 maata, tarvitaan kehittyneempiä huutokauppoja, jotta löydettäisiin maa, jolle voimme antaa levy- ja linkkisektorin.

5. Valitaan mielivaltainen voittajamaa ja kutsutaan sitä ilmoittajaksi , C 1 . Pyydä häntä lisäämään sektori, joka yhdistää D 1 :n nykyiseen alueeseensa ja anna muiden maiden katkaista tämän sektorin, joten:

Minkään häviävän maan osalta D 1 :n arvo plus katkaisusektori ei ole etusijalla (tämä on mahdollista, koska D 1 :n arvo niille on pienempi kuin ). ${\tfrac {1}{n))$ ${\tfrac {1}{n))$
Katkaistun sektorin arvo on missä tahansa voittamassa maassa pienempi kuin . ${\tfrac {1}{n))$

6. Ehdota kukin voittajamaa uutta sädettä r (alkuperäistä ehdotusta pienempää), niin että sektorin katkaistun osan arvo plus säteen r kiekko arvostetaan täsmälleen . Valitsemme pienimmän tällaisen levyn D 2 . Taas on kaksi tapausta: ${\tfrac {1}{n))$

Jos C 1 on yksi D 2 : ta hakeneista maista, annamme sille yksinkertaisesti alueen D 2 (joka on hieman pienempi kuin alkuperäinen hakemus D 1 ) ja yhdistävä sektori. C 1 on samaa mieltä siitä, että arvo on , ja muut maat ovat samaa mieltä siitä, että arvo ei ole suurempi kuin , joten voimme jatkaa rekursiivisesti vaiheesta 1. ${\tfrac {1}{n))$ ${\tfrac {1}{n))$

Muussa tapauksessa C 1 on samaa mieltä siitä, että D 2 : n ja yhdistävän sektorin kokonaisarvo on pienempi kuin . Kaikkien häviäjien on myös hyväksyttävä tämä, koska D 2 on pienempi kuin D 1 . Näin ollen C 1 ja kaikki muut tämän kanssa samaa mieltä olevat maat poistetaan voittajien joukosta. ${\tfrac {1}{n))$

7. Jäljelle jääneiden voittajien joukosta valitsemme uuden hakijan C 2 . Anna hänen lisätä toinen sektori, joka yhdistää D2 : n nykyiseen alueeseen, ja anna muiden maiden katkaista tämä sektori kuten vaiheessa 5.

Huomaa, että nyt alue D 2 on yhdistetty kahteen alueeseen - C 1 ja C 2 . Tämä on ongelma, koska se tekee muusta alueesta epäjohdonmukaista. Tämän ongelman ratkaisemiseksi C 2 saa valita toisen sektorin, jonka pituus on pienempi kuin 1, jotta se ei katkaise yhteyttä [2] . Kaikki maat katkaisivat jälleen tämän kolmannen sektorin, kuten vaiheessa 5. Vastauksena C2 : n on luovutettava takaisin jokin osa D2 : ta C1 : een yhdistävästä sektorista , jonka arvo on yhtä suuri kuin vastaanotetun kolmannen arvo. alalla.

Maan C 2 ehdottama leikkaus sisältää nyt seuraavat osat: D 2 , pituus 1, joka yhdistää D 2 :n C 2 :een , ja kaksi lyhyttä sektoria, jotka eivät saavuta D :n rajaa . Tämän konstruktion arvo C 2 :lle on yhtä suuri kuin , häviäjien arvo on pienempi kuin ja muiden voittajien arvo ei ylitä . ${\tfrac {1}{n))$ ${\tfrac {1}{n))$ ${\tfrac {1}{n))$

Tätä prosessia jatketaan jäljellä olevilla voittajilla, kunnes jäljellä on vain yksi voittaja.

Varmasti yhdistetty alue

Jos alue D on k - kytketty äärellisen k :n kanssa, jako voidaan tehdä induktiolla k :lla .

Jos D on kytketty ja voidaan jakaa käyttämällä edellisen osan protokollaa. $k=1,$

Muussa tapauksessa merkitse D : n ulkoraja B 1 :llä ja sisärajalla . ${\näyttötyyli (k>1)}$ ${\displaystyle B_{2},\dots ,B_{k))$

Löydämme suoran L , joka yhdistää ulkorajan B 1 sisärajaan Bk siten , että kaikkien maiden kohdalla tämän suoran L arvo on 0. Tämä voidaan tehdä seuraavan argumentin valossa. D:ssä on lukematon määrä pareittain ei-leikkautuvia linjoja, jotka yhdistävät B1 : n ja Bk : n . Mutta niiden mitta D :ssä on äärellinen, joten positiivisen suuren juovien lukumäärän on oltava laskettavissa, ja sitten on suora, jolla on nollamitta.

Setti on kytketty . Jaotetaan se rekursiivisesti ja määritetään sitten L mielivaltaisesti mille tahansa maalle, jonka kanssa tämä alue rajoittuu. Tämä ei riko jaon oikeudenmukaisuutta, koska L :n arvo kaikille maille on 0. $D\setminus L$ $(k-1)$

Katso myös

Reilun kakun leikkaamisen haaste

Muistiinpanot

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

Kirjallisuus

Hill TP määrittämällä oikeudenmukaisen rajan // The American Mathematical Monthly. - 1983. - T. 90 , no. 7 . - doi : 10.2307/2975720 . — .
Beck A. Reilun rajan rakentaminen // The American Mathematical Monthly. - 1987. - T. 94 , no. 2 . - doi : 10.2307/2322417 . — .
Muita ratkaisuja ongelmaan on kohdassa 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 .