Matemáticas aplicadas a los puzzles
Publicado: 17 Nov 2012 17:49
MATEMATICAS APLICADAS A LOS PUZZLES
Dos propuestas de menor a mayor nivel:
1) ¿Cuántas piezas del borde tiene un puzzle?
Las clasificaciones nunca son perfectas. Cuando estás separando el montón grande en otros más pequeños, siempre hay alguna descolocada: en un repaso más detallado aparece alguna que no debería estar, y falta alguna que sí debería estar. Esto es así incluso en la clasificación más sencilla de todas: la de las piezas del borde, las que tienen uno de los lados completamente recto. Siempre queda la duda de si estarán todas. Una solución fácil es contarlas. Pero ¿Cuántas debería haber, para empezar? Si no sabemos esto, no podemos saber si nos falta alguna.
La respuesta viene de saber que los puzzles habitualmente están troquelados en filas y columnas. El que el límite entre filas, y entre columnas, tenga una forma irregular, y que el cruce entre ambas sea lo que haga que las piezas tengan la forma que tienen, no quita para que las filas y las columnas sean perfectamente distinguibles.
Dicho lo cual, el número de piezas del borde viene dado por la fórmula
B = 2xF + 2xC – 4
Siendo:
B = número de piezas del borde
F = número de filas
C = número de columnas
Por ejemplo, un puzzle de 1500 piezas está compuesto por 30 filas y 50 columnas (si es apaisado; si es vertical serán 50 filas y 30 columnas; pero eso no cambia el resultado final). Aplicando la fórmula
B = 2x30 + 2x50 – 4 = 60 + 100 – 4 = 156 piezas
Para un puzzle de 2000 piezas (40 filas x 50 columnas), el resultado es
B = 2x40 + 2x50 – 4 = 176 piezas
La fórmula no es más que sumar las piezas de los dos lados largos, los dos lados cortos, y quitar 4 de las esquinas, que han sido contadas por duplicado.
2) Tiempo de resolución en función de las piezas restantes.
Es un modelo que explica algo que es intuitivo y que todos hemos experimentado: cuantas menos piezas quedan por poner, más rápido se ponen. El ritmo de resolución se acelera exponencialmente conforme se acerca el final, sea del puzzle al completo, o de una subsección cuyas piezas hemos separado (por ejemplo una sección de un determinado color). Al principio se va muy lento: las primeras diez piezas entresacadas de entre una población de cuatrocientas, pueden llevar toda una noche. Cuando quedan doscientas, se pone mucho más rápido, una cada minuto, de promedio. Las últimas cien se ponen en media hora. Las últimas veinte, en el último minuto. Las últimas cinco, en los últimos cinco segundos.
Este modelo se basa en los siguientes supuestos:
a) El que busca, lo hace a un ritmo uniforme entre la población de piezas disponibles.
b) La población de piezas disponibles está ordenada en una secuencia (generalmente extendida en filas y columnas en una mesa o un folio), de forma que se puedan repasar todas por orden, sin repetir ninguna ni saltar ninguna.
c) No hay ninguna distribución de probabilidad dentro de la población, es decir, el orden dentro de ella es al azar. Por ejemplo, si estoy buscando en una población de cuatrocientas piezas blancas, la pieza que en concreto estoy buscando tiene la misma probabilidad de estar la primera de la secuencia, que en la posición 137, que en la 218, que en la última. Todas las posiciones tienen la misma probablidad de contener la pieza buscada; para el ejemplo de 400 piezas, esta probabilidad es del 0.25%.
Con todo lo anterior, el tiempo para encontrar una pieza es, en promedio:
T = P / (2xR)
Siendo
T = tiempo necesario para encontrar la pieza
P = población entre la que se busca
R = ritmo de búsqueda
Por ejemplo si tengo mi población de 400 piezas, y busco entre ellas a un ritmo constante por el que voy revisando 50 piezas / minuto, el tiempo promedio para encontrar la pieza que busco es
T = 400 / (2x50) = 400 / 100 = 4 minutos
Lógico: si la pieza que busco está la primera de las 400, no tardo nada. Si la pieza que busco está la última, tardo 8 minutos en llegar a ella (400 piezas a 50 el minuto, son 8 minutos). En promedio, estadísticamente tardo 4 minutos en llegar a una pieza que puede estar en cualquier posición (y por tanto, probabilísticamente, está justo en el centro de la secuencia). Y conforme saco más piezas, más cierto es el promedio (porque la media real de los tiempos tenderá a la media teórica).
Con esto, el tiempo para colocar las cuatrocientas piezas sería
400 x 4 = 1600 minutos = 26 horas 40 minutos
¿Correcto? Pues evidentemente no. ¿Por qué? Porque el hecho de encontrar una pieza reduce el tamaño de la población. La siguiente ronda de búsqueda no es entre 400 piezas, es entre 399, porque la acabo de encontrar la he puesto en el puzzle y ya no está en la secuencia de búsqueda. La probabilidad de cada una de las posiciones de la serie se ha incrementado, ya no es 0,25% sino 0,2506%, y el tiempo promedio de búsqueda es
T = 399 / (2x50) = 3.99 = 3 minutos 59.4 segundos
Poca diferencia con la anterior. Pero es que solamente hemos puesto una de las cuatrocientas. ¿Qué pasa cuando hemos puesto diez? El tiempo estadístico de resolución de esa pieza es
T = 390 / 100 = 3.9 = 3 minutos 54 segundos.
Aunque no es un cálculo muy muy preciso (me faltan recursos matemáticos para la formulación exacta de la suma de la serie; tal vez alguien con más conocimientos de matemáticas que yo pueda en un comentario formalizar la suma de la serie de un modo exacto; si hay alguien que sepa, animo a que lo haga), sí puedo hacer una aproximación: si en las diez primeras piezas, la más lenta en promedio llevó 4 minutos, y la más rápida 3.9 minutos, esas diez piezas en promedio me han consumido:
(4+3.9)/2 = 3.95 minutos
Lo que en total para las 10 piezas son 39.5 minutos = 39 minutos 30 segundos. Sigue sin ser una gran diferencia respecto a la estimación inicial de 40 minutos: solo hemos gastado medio minuto menos. Pero es que seguimos colocando solo una parte mínima del total: son las primeras 10 de cuatrocientas.
¿Qué pasa cuando hemos puesto 200, y hemos alcanzado la mitad? Que el tiempo esperado para esta pieza ya va por
T = 200 / 100 = 2 minutos.
Y el promedio de las 200 piezas que ya hemos puesto ha sido:
(4+2)/2 = 3 minutos.
Lo que nos da un total de 600 minutos = 10 horas. Teniendo en cuenta que el cálculo inicial era de 4 minutos por pieza, nos llevaba a 800 minutos para las 200 primeras piezas, lo que era 13 h 20 minutos. Ahora sí que empiezan a verse los efectos de la aceleración: vamos 3 h 20 minutos por delante de la previsión.
A partir de aquí la cosa se acelera todavía más: cuando faltan 100 piezas el tiempo de búsqueda es 1 minuto. El tiempo de búsqueda promedio al poner el tramo que va de 200 a 100 piezas es de 1 minuto y medio, lo que da de tiempo total dos horas y media. Para las últimas 100, el promedio es medio minuto, y el tiempo total, 50 minutos. Los tiempos totales serían, para este cutre cálculo hecho con promedios por tramos:
Primeras 200 piezas: 10 horas
Siguientes 100: 2 horas 30 minutos
Ultimas 100: 50 minutos
TOTAL = 13 horas 20 minutos
Todo esto para explicar como llego a la fórmula de aproximación de la duración total de una resolución:
T = Px((P/(2xR))+(1/(2xR)))/2
Es decir, el total de piezas multiplicado por el tiempo promedio de resolución de las mismas, que es el promedio entre el tiempo de resolución de la más lenta (la primera) y la más rápida (la última).
Aplicando la fórmula a nuestro ejemplo:
T = 400 x ((400/100))+(1/100)))/2 = 400 x 4.02/2 = 400 x 2.01 = 804 minutos = 13 horas 24 minutos
La diferencia de 4 minutos respecto al cálculo anterior viene de que esta fórmula le asigna tiempo de resolución incluso a la última pieza: 0,02 minutos, lo que incrementa el promedio en 0,01 minutos; eso, multiplicado por las 400 piezas, da los 4 minutos de diferencia.
Dos propuestas de menor a mayor nivel:
1) ¿Cuántas piezas del borde tiene un puzzle?
Las clasificaciones nunca son perfectas. Cuando estás separando el montón grande en otros más pequeños, siempre hay alguna descolocada: en un repaso más detallado aparece alguna que no debería estar, y falta alguna que sí debería estar. Esto es así incluso en la clasificación más sencilla de todas: la de las piezas del borde, las que tienen uno de los lados completamente recto. Siempre queda la duda de si estarán todas. Una solución fácil es contarlas. Pero ¿Cuántas debería haber, para empezar? Si no sabemos esto, no podemos saber si nos falta alguna.
La respuesta viene de saber que los puzzles habitualmente están troquelados en filas y columnas. El que el límite entre filas, y entre columnas, tenga una forma irregular, y que el cruce entre ambas sea lo que haga que las piezas tengan la forma que tienen, no quita para que las filas y las columnas sean perfectamente distinguibles.
Dicho lo cual, el número de piezas del borde viene dado por la fórmula
B = 2xF + 2xC – 4
Siendo:
B = número de piezas del borde
F = número de filas
C = número de columnas
Por ejemplo, un puzzle de 1500 piezas está compuesto por 30 filas y 50 columnas (si es apaisado; si es vertical serán 50 filas y 30 columnas; pero eso no cambia el resultado final). Aplicando la fórmula
B = 2x30 + 2x50 – 4 = 60 + 100 – 4 = 156 piezas
Para un puzzle de 2000 piezas (40 filas x 50 columnas), el resultado es
B = 2x40 + 2x50 – 4 = 176 piezas
La fórmula no es más que sumar las piezas de los dos lados largos, los dos lados cortos, y quitar 4 de las esquinas, que han sido contadas por duplicado.
2) Tiempo de resolución en función de las piezas restantes.
Es un modelo que explica algo que es intuitivo y que todos hemos experimentado: cuantas menos piezas quedan por poner, más rápido se ponen. El ritmo de resolución se acelera exponencialmente conforme se acerca el final, sea del puzzle al completo, o de una subsección cuyas piezas hemos separado (por ejemplo una sección de un determinado color). Al principio se va muy lento: las primeras diez piezas entresacadas de entre una población de cuatrocientas, pueden llevar toda una noche. Cuando quedan doscientas, se pone mucho más rápido, una cada minuto, de promedio. Las últimas cien se ponen en media hora. Las últimas veinte, en el último minuto. Las últimas cinco, en los últimos cinco segundos.
Este modelo se basa en los siguientes supuestos:
a) El que busca, lo hace a un ritmo uniforme entre la población de piezas disponibles.
b) La población de piezas disponibles está ordenada en una secuencia (generalmente extendida en filas y columnas en una mesa o un folio), de forma que se puedan repasar todas por orden, sin repetir ninguna ni saltar ninguna.
c) No hay ninguna distribución de probabilidad dentro de la población, es decir, el orden dentro de ella es al azar. Por ejemplo, si estoy buscando en una población de cuatrocientas piezas blancas, la pieza que en concreto estoy buscando tiene la misma probabilidad de estar la primera de la secuencia, que en la posición 137, que en la 218, que en la última. Todas las posiciones tienen la misma probablidad de contener la pieza buscada; para el ejemplo de 400 piezas, esta probabilidad es del 0.25%.
Con todo lo anterior, el tiempo para encontrar una pieza es, en promedio:
T = P / (2xR)
Siendo
T = tiempo necesario para encontrar la pieza
P = población entre la que se busca
R = ritmo de búsqueda
Por ejemplo si tengo mi población de 400 piezas, y busco entre ellas a un ritmo constante por el que voy revisando 50 piezas / minuto, el tiempo promedio para encontrar la pieza que busco es
T = 400 / (2x50) = 400 / 100 = 4 minutos
Lógico: si la pieza que busco está la primera de las 400, no tardo nada. Si la pieza que busco está la última, tardo 8 minutos en llegar a ella (400 piezas a 50 el minuto, son 8 minutos). En promedio, estadísticamente tardo 4 minutos en llegar a una pieza que puede estar en cualquier posición (y por tanto, probabilísticamente, está justo en el centro de la secuencia). Y conforme saco más piezas, más cierto es el promedio (porque la media real de los tiempos tenderá a la media teórica).
Con esto, el tiempo para colocar las cuatrocientas piezas sería
400 x 4 = 1600 minutos = 26 horas 40 minutos
¿Correcto? Pues evidentemente no. ¿Por qué? Porque el hecho de encontrar una pieza reduce el tamaño de la población. La siguiente ronda de búsqueda no es entre 400 piezas, es entre 399, porque la acabo de encontrar la he puesto en el puzzle y ya no está en la secuencia de búsqueda. La probabilidad de cada una de las posiciones de la serie se ha incrementado, ya no es 0,25% sino 0,2506%, y el tiempo promedio de búsqueda es
T = 399 / (2x50) = 3.99 = 3 minutos 59.4 segundos
Poca diferencia con la anterior. Pero es que solamente hemos puesto una de las cuatrocientas. ¿Qué pasa cuando hemos puesto diez? El tiempo estadístico de resolución de esa pieza es
T = 390 / 100 = 3.9 = 3 minutos 54 segundos.
Aunque no es un cálculo muy muy preciso (me faltan recursos matemáticos para la formulación exacta de la suma de la serie; tal vez alguien con más conocimientos de matemáticas que yo pueda en un comentario formalizar la suma de la serie de un modo exacto; si hay alguien que sepa, animo a que lo haga), sí puedo hacer una aproximación: si en las diez primeras piezas, la más lenta en promedio llevó 4 minutos, y la más rápida 3.9 minutos, esas diez piezas en promedio me han consumido:
(4+3.9)/2 = 3.95 minutos
Lo que en total para las 10 piezas son 39.5 minutos = 39 minutos 30 segundos. Sigue sin ser una gran diferencia respecto a la estimación inicial de 40 minutos: solo hemos gastado medio minuto menos. Pero es que seguimos colocando solo una parte mínima del total: son las primeras 10 de cuatrocientas.
¿Qué pasa cuando hemos puesto 200, y hemos alcanzado la mitad? Que el tiempo esperado para esta pieza ya va por
T = 200 / 100 = 2 minutos.
Y el promedio de las 200 piezas que ya hemos puesto ha sido:
(4+2)/2 = 3 minutos.
Lo que nos da un total de 600 minutos = 10 horas. Teniendo en cuenta que el cálculo inicial era de 4 minutos por pieza, nos llevaba a 800 minutos para las 200 primeras piezas, lo que era 13 h 20 minutos. Ahora sí que empiezan a verse los efectos de la aceleración: vamos 3 h 20 minutos por delante de la previsión.
A partir de aquí la cosa se acelera todavía más: cuando faltan 100 piezas el tiempo de búsqueda es 1 minuto. El tiempo de búsqueda promedio al poner el tramo que va de 200 a 100 piezas es de 1 minuto y medio, lo que da de tiempo total dos horas y media. Para las últimas 100, el promedio es medio minuto, y el tiempo total, 50 minutos. Los tiempos totales serían, para este cutre cálculo hecho con promedios por tramos:
Primeras 200 piezas: 10 horas
Siguientes 100: 2 horas 30 minutos
Ultimas 100: 50 minutos
TOTAL = 13 horas 20 minutos
Todo esto para explicar como llego a la fórmula de aproximación de la duración total de una resolución:
T = Px((P/(2xR))+(1/(2xR)))/2
Es decir, el total de piezas multiplicado por el tiempo promedio de resolución de las mismas, que es el promedio entre el tiempo de resolución de la más lenta (la primera) y la más rápida (la última).
Aplicando la fórmula a nuestro ejemplo:
T = 400 x ((400/100))+(1/100)))/2 = 400 x 4.02/2 = 400 x 2.01 = 804 minutos = 13 horas 24 minutos
La diferencia de 4 minutos respecto al cálculo anterior viene de que esta fórmula le asigna tiempo de resolución incluso a la última pieza: 0,02 minutos, lo que incrementa el promedio en 0,01 minutos; eso, multiplicado por las 400 piezas, da los 4 minutos de diferencia.
