Den overraskende komplekse kunst at skære kage

Matematikere elsker en god kage, så det er næppe en overraskelse, at problemet med, hvordan man skærer og fordeler en Victoria-svamp, f.eks. har øvet dem hårdt. I dag vil kageelskere være glade for at høre om et betydeligt gennembrud.

Problemet er dette: hvordan skærer du en kage og deler den retfærdigt imellem n mennesker, når hver person kan have en anden mening om værdien af ​​hvert stykke?

I 1980 beviste Walter Stromquist ved Swarthmore College nær Philadelphia, at der var en misundelsesfri løsning på problemet. Det er med andre ord muligt at skære en kage i n stykker ved hjælp af n −1 skærer og tildeler én brik til hver person, så alle værdsætter hans eller hendes brik ikke mindre end enhver anden brik.

Men selvom en løsning kan være mulig, er det svært at finde den. Det åbne spørgsmål i dag er, om der er en effektiv algoritme, der finder sådan en del af kagen, siger Xiaotie Deng ved City University of Hong Kong og et par venner.

Deres bidrag til problemet er at finde sådan en algoritme, dog med et par mindre forbehold. Imponerende nok virker deres algoritme i polynomisk tid, hvilket betyder, at en løsning altid kan findes rimelig hurtigt.

forbeholdene? Algoritmen virker, når man kun deler en kage mellem tre personer og så kun for det specielle tilfælde, der involverer matematiske objekter kaldet målbare brugsfunktioner, og resultatet er kun tilnærmelsesvis misundelsesfrit.

Ikke desto mindre burde det stadig være praktisk, når der opstår en tvist ved det næste teselskab for juniorer i fællesrummet.

Ref: arxiv.org/abs/0907.1334 : Om kompleksiteten af ​​misundelsesfri kageskæring

skjule