Den överraskande komplexa konsten att skära kakor

Matematiker älskar en god tårta, så det är knappast en överraskning att problemet med hur man skär och fördelar en Victoria-svamp, till exempel, har ansträngt dem hårt. Idag kommer tårtälskare att bli glada över att höra om ett betydande genombrott.

Problemet är detta: hur skär man en tårta och delar den rättvist mellan n människor när varje person kan ha olika åsikter om värdet av varje bit?

1980 bevisade Walter Stromquist vid Swarthmore College nära Philadelphia att det fanns en avundsfri lösning på problemet. Det går med andra ord att skära en tårta i n bitar använder n −1 skär och att tilldela en pjäs till varje person så att alla värderar hans eller hennes pjäs inte mindre än någon annan pjäs.

Men även om en lösning kan vara möjlig är det svårt att hitta den. Den öppna frågan i dag är om det finns en effektiv algoritm som hittar en sådan bit av kakan, säger Xiaotie Deng vid City University of Hong Kong och ett par kompisar.

Deras bidrag till problemet är att hitta en sådan algoritm, om än med ett par mindre varningar. Imponerande nog fungerar deras algoritm i polynomtid, vilket gör att en lösning alltid kan hittas någorlunda snabbt.

Förbehållen? Algoritmen fungerar när man delar en tårta enbart mellan tre personer och då endast för det speciella fallet som involverar matematiska objekt som kallas mätbara nyttofunktioner, och resultatet är bara ungefär avundsfritt.

Ändå borde det fortfarande vara praktiskt när en tvist uppstår vid nästa teparty för juniorrum.

Ref: arxiv.org/abs/0907.1334 : Om komplexiteten i avundsfri kakskärning

Dölj