Bill 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
tortitas, ¿cuál es el máximo número de cambios (como una función de
) 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 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:
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,
.
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
.
¿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 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
para
de 1 a 19:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | |
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 para
. 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
en función de
, 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 . Concretamente la siguiente:
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:
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
y
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 y la superior en
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:
- Los Simpson y las matemáticas, libro muy recomendable de Simon Singh.
- Flipping pancakes with mathematics, en The Guardian.
- Pancake sorting, en la Wikipedia en inglés.
- Pancake sorting, en MathWorld.
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í.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
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).
Información Bitacoras.com
Valora en Bitacoras.com: Bill 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ó…
[…] Las tortitas de Gates […]
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.
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.
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… Lee más »
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.
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
se me borro la ecuacion… pero bueno, venia a decir lo mismo que acido y JJgJJG
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… Lee más »
PD: creo que me he liado un poquito con los indices pero bueno, me parece que se entiende la idea!
Lo que dices es que
vale 2 si n es de la forma
para algún k, y 1 en caso contrario. Pero entonces, una cota superior sería
, que es menor que la cota inferior que se da en el artículo.
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.
Uy si, nada nada…
Me he precipitado
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.
Interesante la aplicación en biología.
¿Alguien más sintió hasta el olor de las tortitas mientras leía?
Bueno y que esperaos para considerarlo enserio tíos y escribir algo al respecto.
Se agradecería su contribución.
Si Bill Gates probara algunas de mis tartas se le quitaban las tonterias de tanto numeros
Supongamos que
N= 20
Entonces
T= 38
Extenderiamos las tortitas moviendo 19 y dejando 1 donde estaba luego regresamos 19 ordenandolas por tamaño.
Hola, creo que encontré la solución, el único problema es que no tengo como demostrarla, si alguien lo hace agradezco incluya también mi nombre (Luis Alberto Mata Carvajal desde Anaco, Venezuela), 03 de Abril de 2020, un día de cuarentena por el COVID19. – – – Agrupa 2 términos consecutivos con Tn = n -1 T1 = 0 T2 = 1 – – – Agrupa 3 (2+1) términos consecutivos con Tn = n T3 = 3 T4 = 4 T5 = 5 – – – Agrupa 5 (3+2) términos consecutivos) con Tn = n +1 T6 = 7 T7 =… Lee más »
En mi respuesta anterior indiqué que la pauta propuesta por Luis Mata era equivalente a sumar una escalera progresiva (cuyos rellanos siguen la recurrencia r(i)=r(i-1)+i). Pero también podría responder a otras pautas como una escalera de Fibonacci (cuyos rellanos seguirían la sucesión de Fibonacci (empezando con el par 2, 3). Hasta el valor de n = 20 coincidirían ambas pautas y los valores de la tabla original.
Parece que Luis Alberto Mata Carvajal ha encontrado una pauta para los números conocidos. Se trata de una escalera progresiva fácil de programar e Python: def ep(a,r,s): a -= 1 # descuento de pasos en el rellano if a == 0: s += 1 # escalón (al final del rellano) r += s # rellano progresivo a = r # reinicio de pasos del rellano return a, r, s a = r = 2 # primer rellano s = 0 # contador de escalones e = [] # contenedor de la escalera progresiva for i in range(1,21): # print(i, a, r, s… Lee más »