Bill GatesBill Gates es mundialmente conocido por, entre otras cosas, ser uno de los fundadores de Microsoft (y, por tanto, uno de los responsables de Windows) y por las donaciones millonarias que ha realizado a través de la Fundación Bill y Melinda Gates, que comparte con su esposa Melinda. Estas cuestiones y otras muchas de su vida relacionadas con la informática son de dominio público, y se puede encontrar información sobre ellas muy fácilmente a través de internet. Lo que posiblemente no sea muy conocido es su faceta investigadora en lo que se refiere a publicaciones científicas. Y es normal, ya que solamente hay una publicación de este tipo en la que Bill Gates aparezca como autor (coautor en este caso, junto con Christos H. Papadimitriou). Curiosamente, el contenido de dicho artículo tiene como temática central las matemáticas, y en esta entrada vamos a contar la historia del mismo. Matemáticas, tortitas y Bill Gates…ahhh, y Los Simpson, que parece que están en todos sitios. ¿Se puede pedir más?

Comencemos con el origen del problema que trata la publicación científica de Gates y Papadimitriou. En 1975, el matemático estadounidense Jacob E. Goodman se encontraba colocando toallas en su casa. Al ver que la pila de toallas que había quedado estaba algo desordenada decidió recolocarlas en orden según su tamaño: la más grande abajo y la más pequeña arriba. Y fue durante estos cambios de posición de las toallas cuando le vino a la cabeza la siguiente cuestión: ¿Cuál sería el número de cambios que tendría que hacer?

Goodman pensó que el problema era suficientemente interesante como para enviarlo a American Mathematical Monthly, pero lo de las toallas no le convencía. Pensó que cambiando las toallas por tortitas («pancakes» en inglés) la cosa quedaría mejor, y con este cambio nació el problema conocido como pancake sorting problem.

Por otra parte, parece que no tenía muy claro eso de que se le asociara con esa pregunta (quizás por si el tema acababa siendo demasiado trivial y le acababa perjudicando). Por ello no quiso arriesgar y utilizó un seudónimo, concretamente Harry Dweighter, que pronunciado en inglés como harried waiter significa camarero agobiado. Vamos con el enunciado que creó Goodman para ilustrar este problema:

El chef de nuestro negocio es descuidado, y cuando prepara una pila de tortitas, todas son de distintos tamaños. Por tanto, cuando las servimos a los clientes, de camino a la mesa las ordeno un poco, de modo que las más pequeñas queden encima, las de mayor tamaño debajo de todo cogiendo varias de encima e intercalándolas, y lo repito (variando el número de las que cambio) tantas veces como sea necesario. Si hay n tortitas, ¿cuál es el máximo número de cambios (como una función de n) que tendré que hacer para ordenarlas?

Bueno, pues parece que el problema que planteó Goodman sí que despertó el interés de cierta cantidad de matemáticos, tanto por enfrentarse al problema en sí como por las aplicaciones que podría tener (por ejemplo, en informática).

Vamos a analizar un poco el problema para cantidades pequeñas de tortitas, y vamos a llamar T_n al número de cambios que tendríamos que hacer para reordenar de la forma comentada nuestra torre de tortitas en el peor de los casos:

\bullet Supongamos que tenemos una tortita nada más. En este caso es evidente que la torre ya está ordenada, por lo que no hay que hacer ningún cambio. Por tanto, T_1=0.

\bullet Supongamos ahora que tenemos dos tortitas. Aquí podría ocurrir que la más grande estuviera abajo y la más pequeña arriba, por lo que no habría que cambiar nada (la torre ya viene ordenada). Pero puede ocurrir lo contrario, que la más grande venga arriba y la más pequeña abajo, por lo que habría que hacer un único cambio para ordenar la torre: dar la vuelta a las dos tortitas a la vez para que queden en el orden correcto. Por tanto, en este caso tenemos que T_2=1.

\bullet ¿Qué ocurre si tenemos tres tortitas? Aquí la cosa se complica un poco. La torre nos puede llegar de seis formas distintas, y analizando cada una de ellas vemos que el máximo número de cambios necesarios son tres. Aquí tenéis las seis opciones y el número de cambios que harían falta para ordenar cada una de ellas:

En este punto vamos a pararnos un momento para explicar más detenidamente cómo se realizan estos cambios. El camarero estará agobiado, pero es limpio, y realiza los cambios con una espátula, por lo que la forma de hacer cada cambio es meter la espátula por una zona concreta de la pila y dar la vuelta a todas las que en ese momento están encima de la espátula, cambiando totalmente la posición de éstas. En la siguiente imagen podéis ver los tres cambios que habría que hacer para ordenar la torre que aparece en la imagen anterior abajo a la izquierda:

Sería un ejercicio interesante que intentarais ordenar el resto de situaciones que se nos pueden presentar con esas tres tortitas.

Como podéis imaginar, conforme aumenta el número de tortitas de la pila inicial el problema es cada vez más complicado. El número de disposiciones iniciales posibles aumenta considerablemente, y en consecuencia es mucho más difícil encontrar el número de cambios necesarios para ordenarlas todas. Y por si fuera poco parece que los valores de T_n no siguen un patrón determinado, por lo que en principio ni siquiera se podría estimar una expresión para ese número de cambios analizando los valores conocidos. En la siguiente tabla podéis ver el valor de T_n para n de 1 a 19:

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
T_n 0 1 3 4 5 7 8 9 10 11 13 14 15 16 17 18 19 20 22 ¿?

Y en 19 tortitas nos quedamos. No se sabe el valor de T_n para n=20. Ni siquiera mediante el uso de ordenadores se ha podido calcular dicho número, dada la gran cantidad de combinaciones posibles. Posiblemente el principal problema es el comentado anteriormente: no se ha podido encontrar una expresión que calcule exactamente el valor de T_n en función de n, por lo que se puede decir que lo único que tenemos para realizar este cálculo es la fuerza bruta. Y, por desgracia, hasta los ordenadores tienen un límite.

Bueno, ¿y qué tiene que ver Bill Gates con todo esto? Muy sencillo. Hemos dicho que para cantidades de tortitas mayores o iguales que 20 no sabemos cuántos cambios son necesarios, ni parece que tengamos forma de calcular dicho número. En esta situación, calcular una cota superior de dicho valor sí que podría ser interesante. Pues precisamente eso es lo que hicieron Bill Gates y Christos Papadimitriou en su artículo Bounds for sorting by prefix reversal (pdf), publicado en Discrete Mathematics en 1979: establecer una cota superior para T_n. Concretamente la siguiente:

T_n \leq \cfrac{5n+5}{3}

Por ejemplo, si tuviéramos una pila de 200 tortitas (con la que es casi seguro que el camarero estaría realmente agobiado), la peor colocación posible de las mismas se podría reordenar de la manera comentada con, a lo sumo, 335 cambios:

\cfrac{5 \cdot 200 +5}{3}=335

Bueno, en realidad en el artículo, además de dar esa cota superior, plantean una variación del problema y dan también cotas para él. Dicha variación consiste en suponer que cada tortita está algo quemada por uno de sus lados, por lo que es interesante que al presentarlas al cliente cada una de las tortita muestre su «lado bueno» (vamos, que el quemado quede abajo). Por tanto, ahora no solamente hay que ordenar la pila por tamaño, sino que también hay que conseguir que todas ellas estén con su parte quemada mirando hacia abajo. Por ello este problema se denomina burnt pancake problem, y Gates y Papadimitriou establecieron que el número de cambios en este caso estaría entre (3n/2)-1 y 2n+3.

Pero más adelante esas cotas se mejoraron, y uno de los responsables fue David S. Cohen. ¿Os suena? Exacto, uno de los guionistas de Los Simpson (ya lo habíamos citado aquí) y uno de los creadores de Futurama, donde aparece como David X. Cohen. Cohen y el informático venezolano On the problem of sorting burnt pancakes (pdf) en Discrete Applied Mathematics. En él mejoraban las cotas encontradas por Gates y Papadimitriou, dejando la inferior en 3n/2 y la superior en 2n-2. Por ejemplo, para las 200 tortitas que tomamos antes, en este caso necesitaríamos, en el peor de los casos, 398 cambios.

Y parece ser que ahí estamos hasta ahora. Hasta donde yo sé no se han mejorado ninguna de las cotas (si alguien tiene más información al respecto que la deje en un comentario), por lo que podríamos decir que estos dos problemas siguen parados desde que Gates y Papadimitriou por un lado y Cohen y Blum por otro publicaron sus artículos. Y, como decía antes, parece que estos temas tienen interés práctico. En informática, como comentaba más arriba, por el tema de la reordenación de datos que están desordenados. Pero parece ser que también podría tener cierto interés en Biología, en lo que se refiere a cómo se ordenan los genes (algo así como que dos organismos pueden tener los mismos genes pero en distinto orden, y podría haber interés en saber cuántos cambios fueron necesarios para pasar de uno a otro). Si conocéis algún otro campo en el que este problema de las tortitas pueda ser interesante no dudéis en comentarlo.

Fuentes y más información:

La foto de Bill Gates está tomada de aquí, la primera foto de las tortitas de aquí y la segunda de las tortitas de aquí.

Print Friendly, PDF & Email
0 0 votes
Article Rating

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉


Comparte: