Las tortitas de Gates

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í.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

16 Comentarios

  1. Aunque es distinto, el planteamiento me recuerda algo al problema de las Torres de Hanoi que hasta dónde yo sé está más estudiado y hay un algoritmo muy intuitivo de resolución (desconozco si es el mejor en cuanto a número de pasos para todas las configuraciones iniciales).

    Publica una respuesta
  2. Hola,

    Lo primero que me ha llamado la atención es la imagen de la sartén, con sus 6 posibilidades. Y lo digo porque lo primero que he pensado es que en un cíclico, el de cero cambios es el elemento neutro sería el de 0 cambios y el inverso el del (1,2,3) el (1,3,2), que es el de máximos cambios.

    Publica una respuesta
  3. Disculpad pero o no lo entiendo o veo que para T20 serían necesarios 24 pasos. Si nos imaginamos 20 tortitas, necesitamos 2 movimientos a lo sumo para colocar en la parte inferior la tortita mayor. A partir de entonces concebimos la torre que falta como una de 19. En ese caso ya sabremos que faltan 22 movimientos.
    La recurrencia sería Tn=T(n-1)+2
    T20=22+2=24.

    Publica una respuesta
  4. Biel,

    Si no entendí mal el problema la dificultad está en saber el máximo número de pasos, de cambios.
    Según tu razonamiento has demostrado que el máximo número de pasos tiene que ser como mucho 24 pero no has demostrado que no pueda ser 23 ó 22 en lugar de 24.
    Está claro que menos de 22 no puede ser, la sucesión debe ser creciente ya que poder hacerlo en menos pasos con más tortitas significaría que todas las configuraciones de N+1 tortitas que tengan la tortita grande abajo y N arriba podrían hacerse con menos y serían equivalentes a configuraciones de N tortitas.

    Según tu planteamiento una cota superior sería del tipo 2*N pero la cota de Gates es del orden de 5/3 * N que es mejor (más baja) que 2*N

    Publica una respuesta
  5. La solución de Biel Mateu nos da, para 20 tortitas, una cota superior más baja que la de Gates-Papadmitriou. Entre 20 y 53 tortitas esta cota “Biel Mateu”, que se puede representar como T(n)=2*n-16, sigue siendo más restrictiva. A partir de 54 tortitas sigue siendo más favorable la de (5*n+5)/3.
    Lo interesante sería descubrir que para 20 tortitas se puede resolver con 23 movimientos. Mi intuición me sugiere que debe ser posible.

    Publica una respuesta
  6. Biel, por que no lo entiendes? Tu correcta relacion establece un limite superior:
    Tn =19
    usando la endrada n=19 de la tabla.
    Este limite es claramente peor que el de Bill Gates:
    Tn<= 5(n+1)/3
    para n grandes

    Publica una respuesta
  7. Tal como habeis comentado TnT(n-1) asi que no tenemos mas posibilidades que o bien:
    a) Tn=T(n-1)+1
    b) Tn=T(n-1)+2

    Definiendo Ai = 2 si Ti-T(i-1)=2 (caso b)
    Y Ai = 1 en el otro caso (a)

    De ahi los primeros terminos de la sucesion Ai quedarían:

    A2=1
    A3=2
    1
    1
    2
    1
    1
    1
    1
    2
    1
    1
    1
    1
    1
    1
    1
    1
    A19=2

    Estudiando esta sucesion quiza se podria dar con una pista…
    primero hay 2 unos seguidos, un dos, luego 4 unos… otro dos y por ultimo hasta donde sabemos 8 unos seguidos hasta el siguiente 2…

    ¿Potencias de 2?
    Os lo dejo a los listos para que le deis vueltas!

    Publica una respuesta
  8. PD: creo que me he liado un poquito con los indices pero bueno, me parece que se entiende la idea!

    Publica una respuesta
  9. Lo que dices es que A_n vale 2 si n es de la forma 2^k+k para algún k, y 1 en caso contrario. Pero entonces, una cota superior sería n+log_2n, que es menor que la cota inferior que se da en el artículo.

    Publica una respuesta
  10. Creo Askas que sí te has liado. Según la lista tenemos que valen 2 A3, A6, A11 y A19.
    Entre A3 y A6 hay dos unos y entre A6 y A11 hay cuatro unos, pero entre A11 y A19 solo hay siete unos. Tu sugerencia falla.
    Curiosamente en la serie 3, 6, 11, 19,.. las diferencias son, sucesivamente, 3, 5, 8, …
    Podrían ser términos sucesivos de la sucesión de Fibonacci? El siguiente 2 estaría en el lugar 19+13=32, el siguiente sería 32+21=53 y así sucesivamente.
    En este caso la cota sería T(n)=n+2L(n). Demasiado optimista.

    Publica una respuesta
  11. Jugando con los numeros me da una sucesión de cotas dependiendo de n:
    Para n menores o iguales a 7; Tn= (8n-6)/6 (por tentativa)
    Para n mayores a 7 y menores o iguales a 19; Tn= (7n+1)/6 (tiene base matemática)
    Ya no tenemos más datos para continuar con la serie.

    Publica una respuesta
  12. Bueno y que esperaos para considerarlo enserio tíos y escribir algo al respecto.
    Se agradecería su contribución.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com Valora en Bitacoras.com: Bill Gates es mundialmente conocido por, entre otras cosas, ser uno de los fundadores…
  2. Las tortitas de Gates - […] Las tortitas de Gates […]

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *