211service.com
De verrassend complexe kunst van het snijden van taarten
Wiskundigen houden van een goede cake, dus het is geen verrassing dat het probleem van het snijden en verdelen van een Victoria-spons, bijvoorbeeld, hen zwaar heeft belast. Vandaag zullen taartliefhebbers enthousiast zijn om te horen van een belangrijke doorbraak.
Het probleem is dit: hoe snijd je een cake aan en verdeel je deze eerlijk over? N mensen wanneer elke persoon een andere mening kan hebben over de waarde van elk stuk?
In 1980 bewees Walter Stromquist van het Swarthmore College in de buurt van Philadelphia dat er een afgunstvrije oplossing voor het probleem was. Met andere woorden, het is mogelijk om een cake in te snijden N stukken met behulp van N −1 snijdt en wijst een stuk toe aan elke persoon, zodat iedereen zijn of haar stuk niet minder waardeert dan elk ander stuk.
Maar hoewel een oplossing mogelijk is, is het moeilijk om die te vinden. De open vraag van vandaag is of er een efficiënt algoritme is dat zo'n deel van de taart vindt, zeggen Xiaotie Deng van de City University van Hong Kong en een paar vrienden.
Hun bijdrage aan het probleem is het vinden van een dergelijk algoritme, zij het met een paar kleine kanttekeningen. Indrukwekkend, hun algoritme werkt in polynomiale tijd, wat betekent dat er altijd redelijk snel een oplossing kan worden gevonden.
De waarschuwingen? Het algoritme werkt bij het verdelen van een taart onder drie personen en dan alleen voor het speciale geval van wiskundige objecten die meetbare nutsfuncties worden genoemd, en het resultaat is slechts bij benadering vrij van jaloezie.
Toch zou dat nog steeds handig moeten zijn als er een geschil ontstaat op de volgende junior common room tea party.
Referentie: arxiv.org/abs/0907.1334 : Over de complexiteit van het snijden van taarten zonder afgunst