Robertson-Webb mozgó kés eljárás

Robertson-Webb „Moving Knife” eljárása egy kétdimenziós torta irigykedéssel három résztvevőre való feldarabolása [1] . Az eljárás csak két vágást végez, így minden résztvevő egy egész darabot kap.

Az eljárás fő előnye Stromqvist korábbi "Moving Knife" eljárásával és a későbbi Barbanel-Brahms "Moving Knife" eljárással hogy csak egy mozgó kést használ. Ehhez a torta kétdimenziósságát használják fel.

Eljárás

Kezdetben minden résztvevő függőleges vágást végez, így a résztvevő a bal oldali tortát pontosan 1/3-ra becsüli. A bal szélső vágás van kiválasztva. Tegyük fel, hogy Alice csinálta ezt a vágást. Ezután Alice megkapja a bal oldali darabot, amit pontosan 1/3-ra értékel. A maradékot fel kell osztani a megmaradt tagok (Bob és Carl) között.

Ne feledje, hogy Alice részesedését Bob és Carl is legfeljebb 1/3-ra, a maradékot pedig legalább 2/3- ra becsüli . Így ha Bob és Carl az egyenleg legalább felét megkapja, nincs okuk féltékenykedni. A probléma Alice, hogyan lehet őt féltékennyé tenni.

A megoldás a következő megfigyelésen alapul: Alice bármelyik szögbe állíthatja a kést, és szemében két egyenlő részre vághatja a megmaradt darabot . Ez azt jelenti, hogy Alice elforgathatja a kést a torta többi részén, hogy a kés mindkét oldalán a szemében a darabok egyenlőek legyenek.

Amikor a kés 0-n áll, Bob (gyengén) vagy a kés feletti darabot, vagy a kés alatti darabot részesíti előnyben (a gyenge azt jelenti, hogy a darabok egyenlőnek tűnhetnek vele, és ő mindkét darabot egyformán preferálja). Ha a kés ferdén áll , a darabok megfordulnak. Ezért a köztes érték tétele szerint kell lennie egy szögnek, amelyben Bob úgy gondolja, hogy a kés mindkét oldalán lévő darabok azonosak. Amikor a kés beveszi ezt a szöget, Bob felkiált: "Állj!". A tortát felvágják, Carl kiválaszt egy darabot, Bob pedig elveszi a maradék darabot.

Elemzés

Alice nem féltékeny, mert neki mindhárom darab pontosan 1/3-ot ér.

Bob és Carl nem irigylik Alice-t, mivel az ő darabját legfeljebb 1/3-ra, a darabját pedig legalább (1/2)*(2/3) = 1/3-ra értékelik.

Bob nem féltékeny Carlra, mert a darabjaik (az ő szemében) egyformák. Carl nem féltékeny Bobra, mivel a darabok közül a legjobbat választotta.

A "rossz" torta felosztása

A „mozgó kés” eljárás adaptálható feladatmegosztásra , azaz negatív összpontszámú tortára [2] . Ebben az esetben a kezdeti szakaszban nem a bal oldali darab kerül kiválasztásra, hanem a jobb oldali.

Lásd még

• Kés mozgatási eljárás
• A szendvics tétel

Jegyzetek

1. ↑ Robertson, Webb, 1998 , p. 77–78.
2. ↑ Robertson, Webb, 1998 , p. gyakorlat 5.10.

Irodalom

• Jack Robertson, William Webb. Tortavágási algoritmusok: Legyen igazságos, ha tud. - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .