Selfridge–Conway-procedur

Selfridge –Conway-proceduren är en diskret procedur som producerar en avundsfri kakskärning för tre partners. Den är uppkallad efter John Selfridge och John Horton Conway . Selfridge upptäckte det 1960 och berättade det för Richard Guy , som berättade för många människor, men Selfridge publicerade det inte. John Conway upptäckte det senare självständigt och publicerade det heller aldrig. Detta förfarande var det första avundsfria diskreta förfarandet som utformats för tre partners, och det banade väg för mer avancerade förfaranden för n partners (se avundsfri kakskärning) .

Ett förfarande är avundsfritt om varje mottagare anser att (enligt sitt eget mått) ingen annan mottagare har fått en större andel. Det maximala antalet snitt i proceduren är fem. Bitarna är inte alltid sammanhängande.

Proceduren

Selfridge–Conway division

Anta att vi har tre spelare P1 , P2 och P3 . Där proceduren ger ett kriterium för ett beslut innebär det att kriteriet ger ett optimalt val för spelaren.

1. P1 delar kakan i tre delar som de anser vara lika stora.
2. Låt oss kalla A för den största pjäsen enligt P2 .
3. P2 skär av lite A för att få samma storlek som den näst största. Nu A uppdelad i: den klippta biten A1 och klipporna A2 . Lämna beslag A2 åt sidan tills vidare.
   • Om P2 tycker att de två största delarna är lika (så att ingen trimning behövs), så väljer varje spelare en del i denna ordning: P3 , P2 och slutligen P1 .
4. P3 väljer en bit bland A1 och de två andra bitarna.
5. P2 väljer en pjäs med begränsningen att om P3 inte valde A1 måste P2 välja den .
6. P1 väljer den sista biten och lämnar bara beslag A2 som ska delas.

Det återstår att dela upp beslag A2 . Den trimmade biten A1 har valts av antingen P2 eller P3 ; låt oss kalla spelaren som valde det PA och den andra spelaren PB .

1. PB skär A2 i tre lika stora bitar.
2. PA väljer en bit A2 - vi kallar den A21 .
3. P1 väljer en bit av A2 - vi kallar den A22 .
4. PB väljer den sista återstående biten av A2 - vi kallar den A23 .

Analys

Låt oss se varför proceduren är avundsfri. Det ska visas att varje spelare anser att ingen annan spelare fått en större andel. Utan förlust av allmänhet kan vi skriva (se illustrationen ovan):

• PA mottagen: A1 + A21 .
• PB mottaget: B + A23 .
• P1 mottagen: C + A22 .

I följande analys betyder "störst" "störst enligt den spelaren":

• PA fick A1 + A21 . För dem är A1 ≥ B och A1 ≥ C . Och de anser att deras val A21 är den största delen av A2 . Så ingen annan spelare fick en större andel: A1 + A21 ≥ B + A23 , C + A22 .
• PB fick B + A23 . För dem, B ≥ A1 och B ≥ C eftersom de valde B . Det är också de som skär A2 i 3 delar, så för dem är alla delarna lika.
• Pl mottog C + A22 . För dem C ≥ A1 och C = B .
  • P1 menar att PB inte fick någon större andel. Med andra ord: C + A22 ≥ B + A23 . Kom ihåg att P1 valde sin del av A2 före PB , alltså A22 ≥ A23 i deras uppfattning.
  • P1 menar att PA inte fick en större andel. Med andra ord: C + A22 ≥ A1 + A21 . Kom ihåg att för P1 är C lika med A eftersom de skar kakan i första omgången . Dessutom är A = Al + A2 = Al + ( A21 + A22 + A23 ); därför C ≥ A1 + A21 . (Även om PA tog hela A2 och P1 inte fick A22 , skulle P1 inte avundas PA .)

Generaliseringar

Observera att om allt vi vill ha är en avundsfri uppdelning för en del av kakan (dvs vi tillåter fri omhändertagande ), så behöver vi bara använda den första delen av Selfridge–Conway-proceduren, dvs:

• P1 delar kakan i tre lika stora delar;
• P2 klipper högst ett stycke så att de två största delarna är lika;
• P3 tar en bit, sedan P2 , sedan P1 .

Detta garanterar att det inte finns någon avundsjuka.

Denna procedur kan generaliseras till 4 partners på följande sätt:

• P1 delar kakan i 5 lika stora bitar;
• P2 trimmar högst 2 stycken, så att de 3 största delarna är lika;
• P3 klipper högst 1 stycke, så att de 2 största delarna är lika;
• P4 tar en bit, sedan P3 , sedan P2 , sedan P1 .

Detta garanterar att det inte finns någon avundsjuka.

Genom induktion kan proceduren generaliseras till n partners, den första delar kakan till $2^{n-2}+1$ lika delar och de andra partnerna följs av trimning. Den resulterande uppdelningen är avundsfri.

Vi kan tillämpa samma procedur igen på resten. Genom att göra det ett oändligt antal gånger får vi en avundsfri uppdelning av hela tårtan. En förfining av denna oändliga procedur ger en finit avundsfri divisionsprocedur: Brams–Taylor-proceduren .