211service.com
L'arte sorprendentemente complessa del taglio della torta
I matematici adorano una buona torta, quindi non sorprende che il problema di come tagliare e distribuire una spugna Victoria, ad esempio, li abbia messi a dura prova. Oggi, gli amanti della torta saranno entusiasti di sapere di una svolta significativa.
Il problema è questo: come si taglia una torta e la si divide equamente tra? n persone quando ogni persona può avere un'opinione diversa del valore di ogni pezzo?
Nel 1980, Walter Stromquist allo Swarthmore College vicino a Filadelfia dimostrò che esisteva una soluzione al problema senza invidia. In altre parole, è possibile tagliare una torta in n pezzi usando n -1 taglia e assegna un pezzo a ogni persona in modo che ognuno valuti il suo pezzo non meno di qualsiasi altro pezzo.
Ma sebbene una soluzione possa essere possibile, trovarla è difficile. La domanda aperta oggi è se esiste un algoritmo efficiente in grado di trovare una tale fetta della torta, affermano Xiaotie Deng della City University di Hong Kong e un paio di amici.
Il loro contributo al problema è trovare un tale algoritmo, anche se con un paio di avvertimenti minori. Sorprendentemente, il loro algoritmo funziona in tempo polinomiale, il che significa che è sempre possibile trovare una soluzione ragionevolmente rapidamente.
Le avvertenze? L'algoritmo funziona quando si divide una torta solo tra tre persone e quindi solo per il caso speciale che coinvolge oggetti matematici chiamati funzioni di utilità misurabile, e il risultato è solo approssimativamente privo di invidia.
Tuttavia, questo dovrebbe essere ancora utile quando sorge una disputa al prossimo tea party nella sala comune dei ragazzi.
Rif: arxiv.org/abs/0907.1334 : Sulla complessità del taglio della torta senza invidia