Procedura cuțitului în mișcare Robertson-Webb

Procedura „Moving Knife” a lui Robertson-Webb este o procedură pentru tăierea cu invidie a unui tort bidimensional în trei participanți [1] . Procedura face doar două tăieturi, astfel încât fiecare participant primește o bucată întreagă.

Principalul avantaj al procedurii față de procedura anterioară „Moving Knife” a lui Stromqvist și procedura ulterioară Barbanel-Brahms „Moving Knife” utilizarea unui singur cuțit în mișcare. Pentru aceasta se folosește bidimensionalitatea tortului.

Procedura

Inițial, fiecare participant face o tăietură verticală, astfel încât participantul estimează tortul din stânga la exact 1/3. Este selectată tăietura din stânga. Să presupunem că Alice a făcut această tăietură. Apoi Alice primește piesa din stânga, pe care o evaluează la exact 1/3. Restul trebuie împărțit între membrii rămași (Bob și Carl).

Rețineți că cota lui Alice este estimată la cel mult 1/3, iar restul de cel puțin 2/3 de către Bob și Carl. Astfel, dacă Bob și Carl obțin cel puțin jumătate din sold, nu au niciun motiv să fie geloși. Problema este Alice, cum să o faci să nu fie geloasă.

Soluția se bazează pe următoarea observație: pentru orice Alice poate plasa cuțitul într-un astfel de unghi și poate tăia bucata rămasă în două jumătăți egale în ochi . Aceasta înseamnă că Alice poate roti cuțitul peste restul prăjiturii, astfel încât pe ambele părți ale cuțitului din ochi bucățile să fie egale.

Când cuțitul este la 0, Bob (slab) preferă fie piesa de deasupra cuțitului, fie piesa de sub cuțit (slab înseamnă că piesele pot apărea egale cu el și el preferă ambele piese în mod egal). Când cuțitul este înclinat , piesele sunt inversate. Prin urmare, după teorema valorii intermediare , trebuie să existe un unghi în care Bob crede că piesele de pe ambele părți ale cuțitului sunt aceleași. Când cuțitul ia acest unghi, Bob exclamă „stop!”. Tortul este tăiat și Carl alege o bucată, iar Bob ia bucata rămasă.

Analiză

Alice nu este geloasă, pentru că pentru ea toate cele trei piese valorează exact 1/3.

Bob și Carl nu o invidiază pe Alice, deoarece piesa ei este evaluată cel mult la 1/3 și piesa lui cel puțin la (1/2)*(2/3) = 1/3.

Bob nu este gelos pe Carl pentru că piesele lor sunt (în ochii lui) aceleași. Carl nu este gelos pe Bob, deoarece a ales cele mai bune piese.

Împărțirea tortului „rău”

Procedura „cuțit în mișcare” poate fi adaptată pentru împărțirea sarcinilor , adică o prăjitură cu un punctaj general negativ [2] . În acest caz, în stadiul inițial, nu este selectată piesa din stânga, ci cea dreaptă.

Vezi și

• Procedura cuțitului în mișcare
• Teorema sandvișului

Note

1. ↑ Robertson, Webb, 1998 , p. 77–78.
2. ↑ Robertson, Webb, 1998 , p. exercițiul 5.10.

Literatură

• Jack Robertson, William Webb. Algoritmi de tăiere a prăjiturii: fiți corect dacă puteți. - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .