Come tagliare equamente una torta

Un grassone e un mingherlino, seduti nella carrozza ristorante di un treno, aspettano il pesce che hanno entrambi ordinato. Quando arriva il cameriere, il grassone si impadronisce prontamente del pesce più grande, e il mingherlino si lamenta per l'estrema scortesia di questo comportamento. 
«Che cosa avrebbe fatto lei se avesse potuto scegliere per primo?» chiede il grassone irritato.
«Mi sarei comportato in modo gentile e avrei preso il pesce più piccolo» dice con sussiego il mingherlino.
«Bene: è proprio ciò che ha avuto! »

Come mostra la vecchia storiella, certa gente è difficile da accontentare.
Negli ultimi 50 anni, i matematici si sono spesso cimentati con problemi relativi alla divisione equa, in genere formulati in termini di torte anziché di pesci; d'altra parte, il compito di dividere una torta in modo che tutti siano contenti è solo apparentemente semplice. Jack Robertson e William Webb hanno pubblicato di recente un libro affascinante, Cake Cutting Algorithms (AK Peters, Natick, Massachusetts, 1998), che passa in rassegna l'argomento.

Il caso più semplice riguarda due sole persone che vogliono spartirsi una torta in modo che ciascuno sia convinto di aver ricevuto la quantità giusta. «Giusta», in questo caso, significa «metà o più della metà secondo il mio giudizio», e i due possono non essere d'accordo sul valore attribuibile a una data porzione della torta. Anna, per esempio, può amare le ciliegie, mentre Bruno preferisce la glassa. Stranamente, è più facile dividere la torta quando i commensali sono in disaccordo sul valore delle sue parti.

E’ facile rendersene conto in questo caso, perché se diamo a Bruno la glassa e ad Anna le ciliegie, siamo sulla buona strada per accontentare entrambi. Se tutti e due volessero la glassa, il problema < sarebbe più arduo. Non troppo arduo, però, se i commensali sono solo due.

La soluzione «Anna taglia, Bruno sceglie» ha quasi 3.000 anni di storia! E’ una soluzione equa nel senso che nessuno dei due ha diritto di lamentarsi del risultato. Se Anna non apprezza la porzione lasciata da Bruno, deve dare la colpa a se stessa per non essere stata più attenta a dividere in parti uguali (secondo il suo giudizio). Se a Bruno non piace la sua fetta, vuol dire che ha scelto male.

Il problema comincia a diventare interessante con tre partecipanti. Per cominciare, Robertson e Webb analizzano una risposta plausibile ma scorretta. Paolo, Dino e Giulio vogliono dividere la torta in modo che ciascuno sia soddisfatto e ritenga di averne ricevuto almeno un terzo. Detto per inciso, si presuppone che la torta sia sempre divisibile all'infinito (anche se la teoria funziona se la torta ha «atomi» valutabili, ovvero singoli punti a cui almeno uno dei commensali attribuisce valore non nullo). L'algoritmo procede così:

PASSO 1: Paolo taglia la torta in due fette x e w, con x che, a suo giudizio, è pari a 1/3 e w a 2/3.

PASSO 2: Dino taglia w nelle fette y e z, che ritiene ciascuna pari a 1/2 di w.

PASSO 3: Giulio sceglie la porzione che preferisce tra x, y e z. Poi Paolo sceglie tra le altre due fette e infine Dino prende quella che rimane.

E’ chiaro che Giulio rimarrà soddisfatto perché sceglie per primo. Anche Paolo è soddisfatto, per ragioni leggermente più complesse. Se Giulio prende x, allora Paolo può scegliere, tra y e z, la fetta che giudica di maggior valore. Dato che le considera pari a 2/3 nel loro insieme, deve ritenere che almeno una delle due valga 1/3. D'altra parte, se Giulio sceglie y o z, allora Paolo può scegliere x.

Dino, invece, potrebbe non rimanere contento. Se non è d'accordo con Paolo sul primo taglio, potrebbe pensare che w valga meno di 2/3, e quindi l'unica fetta che lo soddisfa è x. Ma Giulio potrebbe scegliere, diciamo, y e Paolo x, obbligando Dino a prendere z, che lui non vuole.

La prima divisione equa fu individuata nel 1944 da Hugo Steinhaus, membro di un gruppo di matematici polacchi che si incontravano regolarmente in un caffè di Leopoli. Il metodo prevede una tecnica dei «ritagli».

PASSO 1: Paolo taglia la torta in due fette x e w, con x che è a suo giudizio pari a 1/3 e w a 2/3.

PASSO 2: Dà x a Dino e gli chiede di tagliarne una fettina se ritiene che sia più di 1/3 o, in caso contrario, di lasciarla com'è. Chiamiamo x' la fetta risultante, pari a x o più piccola.

PASSO 3: Dino passa x' a Giulio, che può scegliere se prenderla o no.

PASSO 4: (a) Se Giulio accetta x', allora Paolo e Dino mettono insieme quello che rimane - w più gli eventuali ritagli di x - e lo considerano un'unica torta, che dividono con il metodo «Io taglio, tu scegli».

(b) Se Giulio non accetta x', e Dino ha tagliato una fettina di x, allora Dino prende x', mentre Paolo e Giulio fanno a «Io taglio, tu scegli» con il resto.

(C) Se Giulio non accetta x', e Dino non ha tagliato una fettina di x, Paolo prende x, mentre Dino e Giulio fanno a «Io taglio, tu scegli» con il resto.

Questa è una possibile soluzione (a voi verificarne la logica). In sostanza, se qualcuno non è soddisfatto di ciò che ha avuto deve aver fatto una cattiva scelta oppure deve aver tagliato in una fase precedente, nel qual caso non può incolpare che se stesso.

Nel 1961 Lester E. Dubins ed Edwin H. Spanier proposero una soluzione che prevedeva un coltello in movimento. Ammettiamo di far passare un coltello sulla torta, lentamente e gradualmente, a partire da sinistra. A qualsiasi istante dato, s è la porzione a sinistra del coltello. Paolo, Dino e Giulio sanno di dover dire «ferma!» non appena s, a loro giudizio, raggiunge 1/3. Il primo che parla si prende s, e gli altri due si dividono il resto con il sistema «Io taglio, tu scegli» o continuando a spostare il coltello finché uno giudica che si sia arrivati a 1/2. (Che cosa succede se due dicono «ferma! »insieme? Pensateci.)

Questo metodo si estende facilmente a n partecipanti. Basta muovere il coltello e avvertire tutti di parlare appena s raggiunge il valore stimato di 1/n. La prima persona che parla prende s e i restanti n - 1 partecipanti continuano il procedimento su quanto rimane della torta, con l'intesa, ovviamente, che ora devono intervenire quando il valore stimato raggiunge 1/(n - 1), e così via.

Devo dire che non amo molto gli algoritmi del coltello mobile, perché la reazione dei commensali comporta inevitabilmente uno scarto temporale. Per ovviare al problema bisogna muovere il coltello molto lentamente.

Definiamo il primo tipo di soluzione un algoritmo a coltello fisso, e il secondo un algoritmo a coltello mobile. Esiste un algoritmo a coltello fisso per la divisione fra tre persone che si può estendere facilmente a n persone. Paolo se ne sta per conto suo a osservare la «sua» torta, quando arriva Dino che chiede di dividere. Paolo taglia la torta in quelle che giudica due metà e Dino sceglie una delle due porzioni. Prima che inizino a mangiare, arriva Giulio e chiede di avere anche lui una porzione equa. Paolo e Dino, ciascuno per conto suo, tagliano le loro fette in tre parti che ritengono dello stesso valore. Giulio sceglie una delle fettine di Paolo e una di quelle di Dino.

Non è difficile capire perché questo algoritmo di coppie successive funziona, e l'estensione a un numero qualsiasi di partecipanti è relativamente agevole. Anche il metodo dei ritagli può essere esteso a n persone, offrendo a tutti la possibilità di «rifinire» una porzione se sono disposti ad accettare il risultato.

Qual è il metodo che richiede un minor numero di tagli? Il metodo del coltello in movimento prevede n - 1 tagli per arrivare a n porzioni, e questo è il minimo che si possa ottenere. I metodi a coltello fisso sono più complessi. Con n persone, una generalizzazione dell'algoritmo dei ritagli utilizza (n² - n)/2 tagli, mentre quello a coppie successive ne utilizza n! - 1, dove n! = n(n - 1)(n - 2) ... 3 x 2 x 1 è un fattoriale. Il numero di tagli è maggiore rispetto a quello dell'algoritmo precedente, tranne quando n = 2.

Un metodo a coltello fisso più efficiente è l'algoritmo «dividi e conquista», che funziona più o meno cosi: cercate di dividere la torta con un taglio tale per cui circa metà dei commensali sarebbero contenti di avere una porzione equa del primo pezzo, e gli altri sarebbero contenti di avere una porzione equa dell'altro pezzo.

Ripetete poi lo stesso procedimento con le due sottotorte separate. Il numero di tagli necessario in questo caso è circa nlog2n. La formula esatta è nk - 2k + 1, dove k è l'unico numero intero tale per cui 2k - 1 < n £ 2k. Questo può essere il miglior risultato possibile con un algoritmo a coltello fisso.

In linea di principio, i metodi per dividere una torta si possono applicare a situazioni della vita reale. Quando, alla fine dell'ultima guerra, la Germania venne divisa tra blocco occidentale e blocco orientale, il primo tentativo creò un avanzo (Berlino) che si dovette dividere in una fase successiva. I negoziatori applicarono intuitivamente il metodo della divisione di una torta. Qualcosa di simile inceppa oggi le relazioni tra israeliani e palestinesi: Gerusalemme è il principale «avanzo» e la Cisgiordania è un altro terreno di contesa.

Si potrebbe far partecipare ai negoziati qualche matematico esperto in divisioni eque? Sarebbe bello vivere in un mondo sufficientemente razionale da utilizzare questo metodo.

da Le Scienze N° 369 del maggio 1999

Pagina contenuta nel sito www.polesine.com