In questi giorni in alcune parti del mondo stiamo uscendo dai festeggiamenti del Carnevale, a cui spesso sono associati dei dolci tipici, fatti appositamente per questo periodo.
Alcuni di questi dolci sono omogenei, mentre altri rappresentano delle particolarità, come può essere la presenza di un candito o di una fragola, oppure forti differenze nella struttura a seconda della porzione che si mangia. Quante volte è capitato che i presenti non fossero d’accordo su come spartire la torta o su quale pezzo scegliere?
Ecco quindi che ritorna un problema di vita quotidiana piuttosto ricorrente, come dividere una torta in modo equo tra i presenti? Per torte omogenee il problema è presto risolto, si fa una divisione in parti uguali e nessuno invidierà il pezzo scelto da un altro, ovvero nessuno vorrà scambiare il proprio pezzo con uno già scelto.
Come fare invece per una torta non omogenea? Esiste un modo di dividere una torta in parti in modo che la scelta di ogni pezzo da parte dei presenti sia senza invidia reciproca? La risposta è, sorprendentemente, si, e l’algoritmo di divisione fa uso del Lemma di Sperner, strumento di combinatoria di teoria dei grafi.
Il problema è stato esaustivamente trattato da S. J. Brams e A. D. Taylor nel 1996, e la risoluzione non solo dimostra l’esistenza dell’ottimo, ovvero di una divisione che non scontenta nessuno, ma presenta anche un algoritmo operativo per arrivarci, o quantomeno, approssimarla.
Immaginiamo che la torta sia vista dall’alto e che si decidano dei tagli paralleli. Un numero N di porzioni corrisponderà a una scelta di come applicare N-1 tagli paralleli. La prima porzione quindi corrisponde al pezzo di torta individuato tra il bordo sinistro della torta e il primio taglio. La seconda porzione corrisponderà al pezzo di torta individuato tra il primo taglio e il secondo taglio e così via. La scelta di come fare le N porzioni si può ridurre quindi semplicemente a come decidere a che distanza dal bordo sinistro fare gli N-1 tagli. Possiamo quindi pensare adesso alle quantità d1, d2, d3,.., dN, dove d1 è la distanza del primo taglio dal bordo sinistro, d2 è la distanza del secondo taglio dal primo taglio, e così via. Poiché la somma di queste distanze deve essere la lunghezza della torta L, si ha d1+d2+d3+…+dN=L. Quindi l’insieme delle scelte è un N-1 simplesso, e ogni punto dell’N-simplesso equivale a un modo differente di tagliare la torta (un 2 simplesso è un triangolo, un 3 simplesso è un tetraedro, e così via).
L’algoritmo di selezione del taglio ottimale si ottiene triangolando l’N-1 simplesso ottenuto e interrogando in ogni vertice della triangolazione una persona diversa su quale fetta di torta sceglierebbe in quella determinata divisione. Si mette quindi sulla triangolazione l’etichetta 1 e la persona in quella divisione sceglierebbe il primo pezzo, l’etichetta 2 se sceglierebbe il secondo, e così via, ottenendo una etichettatura con numeri da 1 a N.
Questa è una etichettatura di Sperner e si può applicare il lemma di Sperner per trovare un triangolino dove tutti i vertici hanno etichetta diversa. Questi, se sufficientemente piccolo, corrisponde a un taglio della torta dove ogni persona vuole un pezzo differente dagli altri, quindi una divisione della torta senza invidia.
In figura si vede come individuare il triangolo con etichette diverse, usando il metodo della botola: i lati del triangolo con etichetta 1 e 2 sono le porte da aprire, portano al triangolino o a un altro lato sul bordo con etichetta 1 e 2. Poiché i lati sul bordo sono sempre un numero dispari, almeno uno non uscirà da un altro lato e porterà invece a un triangolino con etichette diverse (nella figura è in verde la strada per il triangolo ottimale, in blu una che esce).
Ti è piaciuto questo articolo? Segui la pagina di Visit Math per altre curiosità matematiche!
0