Selfridge-Conway-menettely

Selfridge - Conway- menettely on erillinen toimenpide, joka mahdollistaa kateudettoman kakunleikkauksen kolmelle osallistujalle [1] . Menettely on nimetty John Selfridgen ja John Conwayn mukaan . Selfridge löysi menetelmän vuonna 1960 ja ilmoitti siitä Richard Guylle , joka kertoi siitä monille ihmisille, mutta Selfridge itse ei julkistanut löytöään virallisesti. John Conway löysi myöhemmin menetelmän itsenäisesti eikä myöskään julkaissut [2] . Tämä oli ensimmäinen kateudeton erillinen kakunleikkausmenettely kolmelle osallistujalle, ja se tasoitti tietä edistyneemmille toimenpiteille n osallistujalle (katso kateellinen kakun leikkaaminen ).

Menettely antaa tuloksen ilman kateutta siinä tapauksessa, että jokainen prosessiin osallistuja uskoo, että kukaan muu osallistuja (hänen subjektiivisen arvionsa mukaan) ei saa enempää kuin hän. Tässä menettelyssä leikkausten enimmäismäärä on viisi. Osallistujille annettavat kakun osat eivät aina ole jatkuvia (ne voivat koostua useista erillisistä paloista).

Toimenpide

Oletetaan, että meillä on kolme osallistujaa, , ja . Jos menettely tarjoaa kriteerin päätökselle, se on pelaajalle optimaalinen. $P1$ $P2$ $P3$

$P1$ jakaa kakun kolmeen osaan, joita hän pitää samana.
Olkoon se suurin pala, mukaan . $A$ $P2$
$P2$ leikkaa palan pois , jotta se on yhtä suuri kuin toiseksi suurin pala. Nyt jaettu ja leikattu pala . Laitetaan sivuun toistaiseksi. $A$ $A$ $A1$ $A2$ $A2$
- Jos hän katsoo, että kaksi suurinta nappulaa ovat yhtä suuret (joten leikkausta ei tarvita), kukin pelaaja valitsee nappulansa seuraavassa järjestyksessä: , ja lopuksi . $P2$ $P3$ $P2$ $P1$
$P3$ valitsee palan kahden jäljellä olevan palan joukosta. $A1$
$P2$ valitsee kappaleen rajoituksella, jos se ei valitse , täytyy ottaa se. $P3$ $A1$ $P2$
$P1$ ottaa jäljellä olevan palan ja jättää kappaleen edelleen jaettavaksi. $A2$

Vielä on jaettava kappale . Kappaleen valitsi joko pelaaja tai pelaaja . Nimetään pelaaja, joka otti tämän nappulan , ja anna nimi toiselle pelaajalle . $A2$ $A1$ $P2$ $P3$ $PA$ $PB$

$PA$ tai (mutta välttämättä ) leikkaa kolmeen yhtä suureen (hänen mielestään) osaan. $PB$ $P3$ $A2$
$P1$ ottaa pois osan palasta , anna sen olla . $A2$ $A22$
$P2$ (olkoon ) ottaa pois osan kappaleesta , nimittäin . $PA$ $A2$ $A21$
$P3$ (meidän tapauksessamme se on ) ottaa loput palasta , merkitään se nimellä . $PB$ $A2$ $A23$

Analyysi

Katsotaanpa, miksi tällainen jako ei sisällä kateutta. On osoitettava, että kunkin pelaajan tuloksena oleva osuus ei ole pienempi (hänen mielestään) kuin muiden pelaajien osat. Yleisyyttä menettämättä voimme kirjoittaa (katso yllä oleva kuva):

$PA$ saanut . $A1+A21$
$PB$ saanut . $B+A23$
$P1$ saanut . $C+A22$

Seuraavassa analyysissä "suurin" tarkoittaa "suurin pelaajan tuloksen mukaan":

$PA$ saanut . Hänelle ja _ Ja hän uskoo valinneensa teoksen suurimmaksi osaksi . Joten kukaan muu pelaaja ei saanut enempää kuin hän: . $A1+A21$ $A1\geqslant B$ $A1\geqslant C$ $A21$ $A2$ $A1+A21\geqslant B+A23,C+A22$
$PB$ saanut . Hänelle ja koska hän valitsi . Hän myös leikkasi osan 3 osaan, joten hänelle kaikki nämä palat ovat samoja. $B+A23$ $B\geqslant A1$ $B\geqslant C$ $B$ $A2$
$P1$ saanut . Hän ei voi verrata kappaleita samalla tavalla kuin tai , koska kappaleet ja on jo valittu ja hän sai viimeisen kappaleen , mutta: $C+A22$ $PA$ $PB$ $A$ $B$ $C$
- $P1$ uskoo, ettei hän saanut enempää kuin sai. Toisin sanoen ,. Muista, että hän valitsi osansa aiemmin , joten hänen näkökulmastaan. $PB$ $C+A22\geqslant B+A23$ $P1$ $A2$ $PB$ $A22\geqslant A23$
- $P1$ luulee, ettei hän tajunnut sitä enää. Toisin sanoen ,. Muista, että hän valitsi osansa aiemmin , joten hänen näkökulmastaan. $PA$ $C+A22\geqslant A1+A21$ $P1$ $A2$ $PA$ $A22\geqslant A21$
- $P1$ ajattelee niin eikä saanut enempää kuin hän, koska pala on yhtä suuri ja myös yhtä suuri , koska hän leikkasi kakun heti alussa. Sitten ,. Vaikka jompikumpi otti koko palan eikä saanut sitä, hän ei loppujen lopuksi kadehdi ). $PA$ $PB$ $C$ $A$ $B$ $A=A1+A2=A1+(A21+A22+A23)=B=C$ $PA$ $PB$ $A2$ $P1$ $A22$ $P1$ $A=B=C$

Yleistykset

Huomaa, että jos haluamme vain reilun leikkauksen ilman kateutta kakunpalalle (eli sallimme kakunpalan hylkäämisen), meidän on vain käytettävä toimenpiteen ensimmäistä osaa, eli:

$P1$ jakaa kakun kolmeen identtiseen (hänen mielestään) osaan;
$P2$ leikkaa enintään yhden kappaleen saadakseen vähintään kaksi (hänen mielestään) identtistä kappaletta.
$P3$ ottaa palan, sitten , sitten . $P2$ $P1$

Tämä menettely voidaan yleistää 4 osallistujalle seuraavasti [3] :

$P1$ jakaa kakun 5 osaan, jotka ovat hänen mielestään identtisiä;
$P2$ leikkaa enintään 2 kappaletta, joten nyt on hänen mielestään 3 kolme identtistä kappaletta;
$P3$ leikkaa enintään 1 kappaleen, joten nyt on 2 kappaletta, jotka ovat samat hänelle;
$P4$ ottaa palan, sitten , sitten , sitten . $P3$ $P2$ $P1$

Induktiolla menettely voidaan yleistää n osallistujalle, joista ensimmäinen jakaa kakun osiin, joista jokainen on yhtä suuri kuin kakku, ja muut osallistujat noudattavat leikkausmenettelyä. Tuloksena oleva leikkaus on vailla kateutta, ja jokainen kumppani saa vähintään koko kakun arvoa vastaavan arvon. $2^{n-2}+1$ $1/2^{{n-1}}$

Voimme soveltaa samaa menettelyä jäännöksiin. Kun teemme tämän äärettömän monta kertaa, saamme osion ilman kateutta koko kakulle [4] . Tämän äärettömän menettelyn parannus johtaa rajalliseen kateudettomaan osiointimenettelyyn , Brahms-Taylor-menettelyyn .

Muistiinpanot

↑ Robertson, Webb, 1998 , s. 13-14.
↑ Brams ja Taylor 1996 , s. 116-120.
↑ Brams ja Taylor 1996 , s. 131-137.
↑ Brams ja Taylor 1996 , s. 137.

Kirjallisuus

Jack Robertson, William Webb. Kakunleikkausalgoritmit: Ole reilu, jos pystyt... - CRC Press, 1998. - ISBN 978-1-56881-076-8 .
Steven J. Brams, Alan D. Taylor. Reilu osasto: Kakun leikkaamisesta riitojen ratkaisuun . - Cambridge University Press, 1996. - ISBN 0521556449 .