Procedury z ruchomym nożem Austina

Austina z ruchomym nożem to procedury sprawiedliwego podziału tortu . Każdemu z n partnerów przydzielają kawałek tortu, który ten partner ceni dokładnie jako ${\ displaystyle 1/n}$ tortu. Kontrastuje to z podziału proporcjonalnego , które dają każdemu partnerowi co najmniej $.$ , ale niektórym partnerom mogą dać

Kiedy ${\ displaystyle n = 2}$ , podział wygenerowany przez procedurę Austina jest podziałem dokładnym i jest również wolny od zazdrości . Ponadto tort można podzielić na dowolną liczbę k kawałków, które obaj partnerzy wyceniają dokładnie na 1/ k . Można więc podzielić tort między partnerów na dowolne ułamki (np. dać 1/3 Alicji i 2/3 George'owi).

Gdy $n> 2} , podział nie$ $displaystyle$ ani dokładny, ani pozbawiony zazdrości, ponieważ każdy partner ceni tylko swój własny element jako może inaczej cenić inne elementy.

Głównym narzędziem matematycznym używanym w procedurze Austina jest twierdzenie o wartości pośredniej (IVT).

Dwóch partnerów i pół ciastka

Podstawowe procedury obejmują partnerów, którzy chcą $ciasto tak$ dostał dokładnie połowę.

Procedura dwóch noży

Na potrzeby opisu nazwijmy dwóch graczy Alicję i Jerzego i załóżmy, że ciasto jest prostokątne.

Alicja kładzie jeden nóż po lewej stronie ciasta, a drugi równolegle do niego po prawej stronie, gdzie ocenia, że dzieli ciasto na dwie części.
Alicja przesuwa oba noże w prawo w taki sposób, że część między dwoma nożami zawsze zawiera połowę wartości ciasta w jej oczach (podczas gdy fizyczna odległość między nożami może się zmienić).
George mówi „stop!” kiedy myśli , że połowa ciasta jest między nożami. Skąd możemy mieć pewność, że George w pewnym momencie powie „stop”? Bo jeśli Alicja dotrze do końca, musi mieć lewy nóż w miejscu, w którym zaczął się prawy nóż. IVT że w pewnym momencie ciasto zostanie podzielone na pół.
Rzuca się monetą, aby wybrać jedną z dwóch opcji: albo George otrzymuje kawałek między nożami, a Alicja dwa kawałki z boków, lub odwrotnie. Jeśli partnerzy są prawdomówni, to zgadzają się, że kawałek między nożami ma wartość dokładnie 1/2, a więc podział jest dokładny.

Procedura jednego noża

Ten sam efekt można osiągnąć jednym nożem.

Alicja obraca nóż nad ciastem o 180°, trzymając połówkę z każdej strony.
George mówi „stop!” kiedy się zgodzi.

Alicja musi oczywiście zakończyć turę nożem na tej samej linii, na której się rozpoczęła. Ponownie, na IVT, musi istnieć punkt, w którym George czuje, że dwie połówki są równe.

Dwóch partnerów i ułamki ogólne

${$ $displaystyle k \ geq 2}$ znaleźć jeden kawałek ciasta, który obaj cenią dokładnie dla dowolnej liczby całkowitej . Wywołaj powyższą procedurę ${\ Displaystyle \ operatorname {Cięcie} _ {2} (1/k)$ :

Alicja tworzy $tak określone$ znaki na torcie tak, że $displaystyle$ mają wartość dokładnie $1/k}$ .
Jeśli istnieje element, który George również ceni jako ${\ displaystyle 1/k}$ , to koniec.
W przeciwnym razie musi istnieć figura, którą George ocenia na mniej niż ${\ displaystyle 1/k}$ i sąsiednia figura, którą George ocenia na więcej niż ${\ displaystyle 1/k}$ .
$je$ równolegle, utrzymując wartość między nimi na dokładnie , drugiego kawałka. Według IVT musi istnieć punkt, w którym George zgadza się, że wartość między nożami wynosi dokładnie ${\ displaystyle 1/k}$ .

Stosując rekursywnie $dwaj$ partnerzy mogą podzielić cały tort na $\ displaystyle 1/k}$ $z$ każdy jest wart dokładnie dla obu z nich:

Użyj $wycięcia kawałka,$ wart dokładnie $k}$ dla obojga
Teraz pozostałe ciasto jest warte dokładnie ${\ Displaystyle (k-1) / k}$ dla obojga partnerów; $_$ / _ $_ k}$ dla obojga partnerów.
Kontynuuj w ten sposób, dopóki nie będzie kawałków ${\ displaystyle k}$ .

Dwóch partnerów może osiągnąć dokładny podział z dowolnym racjonalnym stosunkiem uprawnień nieco bardziej skomplikowaną procedurą.

Wielu partnerów

Łącząc z protokołem Finka $n$ możliwe jest podzielenie ciasta na $\ displaystyle n}$ otrzymał kawałek warty dokładnie ${\ Displaystyle 1/n}$ dla niego:

$1/2$ 1 i nr 2 używają, nich kawałek warty dokładnie
$\ Displaystyle \ operatorname {Cięcie} _ {2} (1/3)$ nr 3 używa z partnerem udziału, a następnie ${\ Displaystyle \ operatorname {Cięcie} _ {2} (1/3)}$ z partnerem nr 2, aby uzyskać dokładnie 1/3 jej udziału. Pierwsza figura jest warta dokładnie 1/6 dla partnera nr 1, więc partner nr 1 pozostaje z dokładnie 1/3; to samo dotyczy partnera nr 2. Jeśli chodzi o partnera nr 3, podczas gdy każdy kawałek może być większy lub mniejszy niż 1/6, suma dwóch kawałków musi wynosić dokładnie 1/3 całego tortu.

$,$ że dla $wygenerowany$ podział nie jest dokładny, ponieważ kawałek jest wart a niekoniecznie dla innych partnerów Od 2015 r. Nie jest znana $dokładna$ partnerów tylko prawie dokładne procedury podziału.

Zobacz też

Procedura Austina jest stosowana w procedurze Bramsa – Taylora – Zwickera .
Inne procedury i wyniki dotyczące równego podziału i dokładnego podziału .

Linki zewnętrzne

Fiszer, Daniel. „Konsensusowy podział tortu na dwie osoby w dowolnych proporcjach” . Matematyka SE . Źródło 23 czerwca 2015 r .