Brams–Taylor procedur

Brams –Taylor-proceduren (BTP) är en procedur för avundsfri kakskärning . Det förklarade det första ändliga förfarandet för att skapa en avundsfri uppdelning av en tårta bland alla positiva heltal av spelare.

Historia

1988, före upptäckten av BTP, hävdade Sol Garfunkel att problemet som löstes med satsen, nämligen n-personers avundsfri kakskärning, var bland de viktigaste problemen i 1900-talets matematik.

BTP:n upptäcktes av Steven Brams och Alan D. Taylor . Den publicerades först i januarinumret 1995 av American Mathematical Monthly och senare 1996 i författarnas bok.

Brams och Taylor har ett gemensamt amerikanskt patent från 1999 relaterat till BTP.

Beskrivning

BTP delar upp kakan del för del. Ett typiskt mellantillstånd för BTP är följande:

• En del av kakan, säg $X$ , delas upp på ett avundsfritt sätt mellan alla partners.
• Resten av kakan, säg $Y$ , förblir odelad, men -
• En partner, säg Alice, har en Irrevocable Advantage (IA) över en annan partner, säg Bob, med avseende på $Y$ . Detta betyder att oavsett hur $Y$ är uppdelad, även om vi ger $Y$ helt och hållet till Bob, avundas Alice fortfarande inte Bob.

Som ett exempel på hur en IA kan genereras, överväg det första steget i Selfridge–Conways diskreta procedur :

• Alice delar upp kakan i 3 delar hon anser lika; låt oss kalla delarna $A,B,C$ .
• Bob trimmar den bit han anser vara störst (säg $A$ ) för att göra den lika med den näst största; låt oss kalla trimningarna $Y$ och den trimmade biten $A\setminus Y$ .
• Charlie väljer en bit av $(A\setminus Y),B,C$ ; sedan väljer Bob (han måste ta $(A\setminus Y)$ om det är tillgängligt); och sist Alice.

När detta steg är klart delas hela kakan utom $Y$ på ett avundsfritt sätt. Dessutom har Alice nu en IA över den som tog $(A\setminus Y)$ . Varför? eftersom Alice tog antingen $B$ eller $C$ , och båda är lika med $A$ enligt hennes mening. Så, enligt Alices åsikt, kan den som tog $(A\setminus Y)$ också ha $Y$ – detta kommer inte att göra henne avundsjuk.

Om vi ​​vill försäkra oss om att Alice får en IA över en specifik spelare (t.ex. Bob) så krävs en mycket mer komplicerad procedur. Den delar successivt upp kakan i mindre och mindre bitar, och ger alltid Alice en bit som hon värdesätter mer än Bobs, så att en IA bibehålls. Detta kan ta obegränsad tid – beroende på de exakta värderingarna av Alice och Bob.

Med hjälp av IA-proceduren skapar BTP-huvudproceduren IA:er för alla beställda partnerpar. Till exempel, när det finns 4 partners, finns det 12 beställda partnerpar. För varje sådant par (X,Y) kör vi en underprocedur som garanterar att partner X har en IA över partner Y. Efter att varje partner har en IA över alla andra partner, kan vi bara ge resten till en godtycklig partner och resultatet är en avundsfri uppdelning av hela tårtan.

Se även

• Brams–Taylor–Zwicker-procedur – en rörlig knivprocedur för 4 partners, som använder ett begränsat antal snitt.
• Avundsfri kakskärning – äldre och nyare procedurer för samma problem.
• Justerat vinnarförfarande – förfarande designat av Brams och Taylor som tar itu med det liknande, men distinkta, problemet med att dela upp varor mellan två agenter.