Non so se avete presente le frittelle che gli americani si mangiano a colazione (i pancakes, per la precisione): quelle robe più o meno spesse e tonde che già non sono dietetiche di loro ma poi vengono completate con generose dosi di sciroppo d’acero. Qua però le frittelle le uso solo come spunto per un problema matematico. Supponiamo di avere un certo insieme di frittelle, tutte di dimensioni diverse, e volerle mettere in ordine di diametro, con la più piccola in alto e la più grande in fondo. L’unica operazione che ci è concessa fare, però, è prendere una spatola, infilarla in un punto qualsiasi della pila di frittelle, sollevarne alcune e lanciarle in aria, riprendendole rovesciate. Detto in maniera meno cuciniera, se abbiamo la stringa abcdefghijk possiamo scegliere un punto qualunque (ad esempio, e) e rovesciare la sottostringa che termina lì, ottenendo così edcbafghijk. Al crescere del numero n di frittelle, come varia il numero minimo P(n), il pancake number, di operazioni da fare nel caso peggiore?
Con una sola frittella non occorre fare nulla, quindi P(1)=0. Con due frittelle, i casi sono due: o sono già in ordine oppure basta rovesciarle entrambe in un colpo, quindi P(2)=1. Con tre frittelle la cosa si inizia a fare un po’ complicata: però si può vedere che partendo dalla disposizione 132, entrambe le mosse iniziali possibili (girare le prime due frittelle arrivando alla disposizione 312, oppure girarle tutte arrivando a 231) richiedono altre due operazioni: insomma, P(3)=3. Al crescere delle frittelle, la cosa diventa molto complicata: è abbastanza semplice vedere che aggiungendo una frittella il numero minimo di operazioni cresce almeno di 1 (aiutino: se la configurazione peggiore nel caso di n-1 frittelle è C, immaginate la configurazione nC’, dove C’ è la configurazione ottenuta invertendo C), è abbastanza semplice vedere che P(n) ≤ 2n-3 (aiutino: va’ a leggere la pagina relativa di Wikipedia, da cui tra l’altro ho preso il disegno). Che una formula non sia così semplice da trovare, lo si può notare anche guardando la tabella dei valori di P(n) per n che va da 1 a 13:

e i valori computati negli ultimi anni da un gruppo di informatici giapponesi usando cluster di computer:

Se non si sa andare più avanti di così, significa che c’è davvero qualcosa di complicato. E in effetti, i limiti teorici trovati nel 1975 e pubblicati nel 1979 – che 5(n+1)/3 inversioni sono sempre sufficienti, e nel caso peggiore ne servono almeno 17n/16 – sono rimasti imbattuti fino al 1997, quando Mohammad H. Heydari e I. Hal Sudborough alzarono il limite inferiore a 15n/14, e a quest’ultimo settembre, dove Sudborough e un gruppo di suoi studenti ha abbassato il limite inferiore a (18/11)n.

Che c’entra tutto questo con Bill Gates, mi staranno chiedendo i pochi pazzi che sono arrivati fin qua? Semplice. L’articolo del 1979, Bounds for Sorting by Prefix Reversal, è stato scritto da nientemeno che William Henry Gates III, insieme al suo allora professore Christos Papadimitriou. Un lato inaspettato del multimiliardario, insomma!
Bibliografia:
♦ http://it.wikipedia.org/wiki/Ordinamento_delle_frittelle
♦ http://www.maa.org/mathtourist/mathtourist_10_9_08.html
♦ http://www.npr.org/templates/story/story.php?storyId=92236781

Ultimo aggiornamento: 2008-11-10 12:12