Pochi forse sanno che il nostro amato chief software architect è anche il coautore di un davvero bellissimo risultato di combinatorica sul cosìdetto problema delle frittelle :-) (in inglese "pancake problem") insieme al vincitore del Premio Knuth per 2002 (una specie di Nobel per l'informatica teorica), il Prof. Christos H. Papadimitriou. Insieme, sono riusciti all'inizio del 1978 (Bill aveva appena compiuto 22 anni) a dimonstrare che per fare il sorting di una permutazione di ordine n ci vogliono non più di (5*n+5)/3 flip (o prefix reversal) e non meno di 17*n/16 flip. Vale la pena di scaricare (e leggere) il PDF della fotocopia dell'articolo originale (sono quasi 5 MB):
W.H. Gates, C.H. Papadimitriou, "Bounds for Sorting by Prefix Reversal", Discrete Mathematics, 27 (1979) 47-57
Il limite inferiore è stato frattempo migliorato nel 1992, a 15*n/14, grazie a David S. Cohen (non mi crederete però ha scritto anche The Simpsons) e al Prof. Manuel Blum (quest'ultimo vincitore del Premio Turing per 1995 - il premio è la più alta onorificenza per computer science).
Il problema originale è stato proposto dal Prof. Jacob E. Goodman nel 1975 (si è firmato però Harry Dweighter) e suscita tuttora interesse dopo 30 anni, soprattutto per le sue varie applicazioni pratiche. Il nostro Bill nello stesso articolo, oltre al risultato sopra menzionato, propone e risolve un altro problema leggermente modificato: quello delle frittelle bruciate ("burnt pancake problem"). Lascio adesso a voi il piacere di gustarle :-)
P.S.: Sembra che il valore del limite maggiore, (5*n+5)/3, sia stato ottenuto indipendentemente sempre nel 1978, anche da due ungheresi (vedi la nota della pagina 7 di questo articolo del mitico Neil J.A. Sloane):
E. Györi, G. Turán, "Stack of pancakes", Studia Sci. Math. Hungar., 13 (1978),133-137