Zaskakująco złożona sztuka krojenia ciasta

Matematycy uwielbiają dobre ciasto, więc trudno się dziwić, że problem z krojeniem i porcjowaniem, powiedzmy, biszkoptu Victoria, bardzo ich męczył. Dziś miłośnicy ciast będą podekscytowani słysząc o znaczącym przełomie.

Problem w tym: jak pokroić ciasto i podzielić je sprawiedliwie między n ludzi, kiedy każda osoba może mieć inne zdanie na temat wartości każdego kawałka?

W 1980 roku Walter Stromquist z Swarthmore College pod Filadelfią udowodnił, że istnieje rozwiązanie tego problemu bez zazdrości. Innymi słowy, można pokroić ciasto na n kawałki używające n −1 cięć i przydzielić po jednym kawałku każdej osobie, tak aby każdy cenił swój kawałek nie mniej niż jakikolwiek inny kawałek.

Ale chociaż rozwiązanie może być możliwe, znalezienie go jest trudne. Otwarte pytanie brzmi dziś, czy istnieje wydajny algorytm, który znajdzie taki kawałek ciasta, mówi Xiaotie Deng z City University of Hong Kong i kilku kumpli.

Ich wkład w problem polega na znalezieniu takiego algorytmu, choć z kilkoma drobnymi zastrzeżeniami. Imponujące jest to, że ich algorytm działa w czasie wielomianowym, co oznacza, że ​​zawsze można znaleźć rozwiązanie w miarę szybko.

Zastrzeżenia? Algorytm działa przy podzieleniu ciasta tylko między trzy osoby i tylko w szczególnym przypadku obiektów matematycznych zwanych mierzalnymi funkcjami użyteczności, a wynik jest tylko w przybliżeniu wolny od zazdrości.

Niemniej jednak powinno to być przydatne, gdy na najbliższym przyjęciu herbacianym w pokoju wspólnym pojawi się spór.

Nr ref.: arxiv.org/abs/0907.1334 : O złożoności krojenia ciasta bez zazdrości

ukryć