domingo, 2 de enero de 2005
El siguiente problema pertenece a Henry Ernest Dudeney, el gran creador inglés de acertijos. Yo lo tomé del libro de Martin Gardner, "Huevos, nudos y otras mistificaciones matemáticas", Editorial Gedisa.
Éranse una ves nueve presos peligrosos que debían ser cuidadosamente vigilados. Cada día de la semana eran sacados a hacer ejercicio, esposados unos a otros, como se indica en el esbozo que hizo uno de los guardianes.
1-2-3
4-5-6
7-8-9
4-5-6
7-8-9
En ningún día de la semana podían ser encadenados los dos mismos hombres.
En el esbozo se muestra la forma en que fueron sacados el día Lunes.
¿Será posible repartir a los 9 hombres en tríos para los cinco días siguientes?
Se entiende que el 1 ya no puede ser encadenado junto al 2, ni por la izquierda ni por la derecha. El 2 no puede volver a ser encadenado ni con el 1 ni con el 3. En cambio, el 1 y el 3 si pueden ser encadenados juntos.
Update:
A Pedido de Jean Paul, les comento la solución que da el libro.
En él no se da una explicación de por qué funciona. Aparentemente, este método sirve para otros problemas similares. La condición del "prisionero central" obliga a utilizar dos ruedas en vez de una.
Un par de ruedas Lullianas podrían ser las siguientes: (click para agrandar)
Cada disco se hace girar en sentido horario, por ejemplo, a razón de tres pasos por vez. En cada paso, los vértices de los tres triángulos generan una terna. Cada terna ha de tener en el centro el número indicado con el asterisco.
Cada disco genera tres grupos:
día 1 día 2 día 3
413 746 179
276 519 843
598 832 265
día 4 día 5 día 6
124 457 781
739 163 496
586 829 253
La disposición para el primer día no es igual a la dada, pero se lo puede modificar fácilmente.
Cada grupo es cíclico en el sentido de que si se le suma 3 (módulo 9) al primer trío, obtenemos el segundo, si se lo sumamos al segundo, obtenemos el tercero y del tercero volvemos al primero.
Como para ir terminando, les comento que Dudeney propuso disponer 21 presos durante 15 días en las mismas condiciones, un problema difícil, para mantener al lector embebido durante los meses de invierno. :-)
Suscribirse a:
Enviar comentarios (Atom)
35 comentarios:
Bueno, una solución puramente matemática y no demasiado razonada (es muy temprano por aquà y la Navidad está acabando con casi todas mis neuronas =oS )
El numero de parejas que se pueden formar con nueve personas, no teniendo en cuenta el orden, si no recuerdo del todo mal es lo que denomina "Combinaciones de 9 elementos tomados de 2 en dos", que se puede obtener (entre otras formas), con la fórmula:
C(n,m) = n!/[ m! x (n-m)! ]
Siendo ! el factorial del número.
Para n=9 y m=2 nos darÃa 32 combinaciones distintas. Ahora bien, cada dÃa "gastarÃamos" 12 de ellas (6 "laterales" y 3 "centrales"), con lo cual al acabar el tercer dÃa habrÃamos acabado con todas ellas, y deberÃamos repetir una.
Joer que tostón me ha quedado.
Salu2,
deibyz
P.D.: Feliz Navidad y todas esas cosas que se dicen por estas fechas.
Hasta el quinto dÃa se pueden haces trÃos, por ejemplo
-1----2---3----4----5
123 341 516 264 248
456 576 274 791 596
789 829 839 853 731
El sexto dÃa ya es imposible ya que no puede quedar ninguno al medio.
Vale, acabo de encontrar el fallo en mi razonamiento...
Cada dÃa no se "gastan" 12 parejas como yo decÃa, sino sólo 6, ya que hemos quedado en que son parejas en las que el orden no importa. Con lo cual, habrÃa para 6 dÃas (Antes también me equivoqué en las cuentas, son 36, no 32).
Con los 5 primeros dÃas del ejemplo de alejo no se podrÃa formar un sexto grupo, aunque sà quedarÃan 6 parejas libres (17, 18, 25, 36, 49 y 68). HabrÃa que ver si hay alguna combinación que llegue hasta el sexto dÃa (en principio podrÃa haberla) o demostrar que no existe.
Deibyz, hay un error en tu planteamiento porque se tocan un montón de números, por ejemplo el 41 del primer dÃa se repite 14 para el segundo, y asà con varios.
Recordá que no pueden repetirse ni por derecha ni por izquierda.
Casi al unÃsono, alejo
Ya que lo pedÃs, deibyz, te corrijo (o te muestro la falla). Los dos primeros dÃas están juntos 1 y 4, los siguientes dos dias estan juntos 1 y 7, los ultimos dos dias salen emparejados 7 y 4.
Eso se llama resonancia acertijera Lorena.:)
Pues sÃ, sabÃa yo que tenÃa que comprobar antes de postear pero...
Bah, no voy a buscar excusas, no me apetecÃa =oP. La idea básica es la del post anterior, hay 36 parejas distintas, lo cual a priori deberÃa darnos para llenar 6 dÃas (6 parejas por dÃa). Aunque puede que la restricción de grupos de 3 con uno en el medio haga que no se pueda hacer. Si a última hora me aburro mucho puede que me ponga a programar algo que pruebe todas las combinaciones... Pero solo si me aburro mucho.
Cada preso puede estar con otros 8. Cuando está en un extremo se elimina uno de ellos y cuando está en el medio se eliminan dos. Como son 6 dÃas en total, cada preso puede estar a lo sumo 2 dÃas en el medio. Además, la cantidad de lugares a ocupar en los extremos es el doble que los lugares a ocupar en le centro. Entonces cada preso debe estar efectivamente 2 dÃas en el centro porque más no puede como ya fue mencionado y si estuviera menos no podrÃan ocuparse los 18 lugares centrales que habrÃa en 6 dÃas. Por lo tanto, serÃa posible repartir los hombres. Es decir, yo creo que se puede.
Soy de la opinión de Jean Paul, a priori no veo ningún impedimento lógico para que sea posible encontrar la combinación pero se hace bastante pesado hallarla. Suerte
jean paul eres un crack diciendo, yo creo k se puede, sin mirar el problema hay dos posibilidades: "yo creo k se puede" o "yo creo k no se puede", asi k tampoco t as arriesgado muxo, podrias aber buscado los numeritos para demostrarlo, como hizo alejo.
Obviamente los busqué pero no encontré una solución para 6 dÃas. El comentario ese iba a que se habÃa mencionado que no se podÃa. Si querés la próxima vez digo que se puede y listo, aunque no esté demostrado. Si leyeras bien lo que dice, te darÃas cuenta que se refiere a lo mismo que dicen deibyz y yole. "A priori se puede encontrar una solución para 6 dÃas". Ahà te gusta más?
¿Con este problema y el del arbolito llegaremos a fin de año?
Me gusta cuando se preguntan y se contestan solos... ¡Asà me ahorro trabajo!
La idea de demostrar la imposibilidad de un problema es siempre tentadora. En este caso, les ayudo diciéndoles que no se gasten ya que el problema si tiene solución.
Por supuesto, el segundo razonamiento de Deibyz y el de Jean Paul son correctos.
La idea de que cada número debe ir en el centro 2 veces es perfecta y sirve para eliminar un montón de casos. Claro que todavÃa falta el pequeño detalle de encontrar la solución :-)
las cosas que estan escritas de manara ordenada son y es que los numeros son conpatibles en todo momento y aparanta ser que si, poro tiene sus limitaciones en cuanto a si se pueden estar repitiendo y si lo multiplicas o lo divides o simplemente le restas , esta es una prueba de ordenacion cronologuia no repetitiva
¿qué?
ya no tiene solucion esto, parece...
Bueno, parece que tenìa que venir yo para terminar con este problema, despues de 2 horas de provar combinaciones, y 1/2 hora chequeando estoy seguro de que lo logre :) ya me estaba encabronando :P
Bueno, seria asi:
Dias:
1er--- 2do--- 3er
417--- 528--- 639
743--- 851--- 962
273--- 486--- 195
213--- 546--- 879
324--- 657--- 981
538--- 167--- 492
Acepto felicitaciones :P
ja, lo plantie mal ahi, los dias son los que estan en horizontal :P = se entiende ;P
se ve que era la emocion de averlo resuelto :P
si, la verdad a mi despues de dar tantas vueltas y cambiar todo, me habia quedado de cualquier manera, y ya me tenian tan cansado los numeritos que los deje como estaban, pero asi se ve mejor :)
Mis felicitaciones Punker. Yo en lo personal no habÃa encontrado la solución y todavÃa no tego en claro si existe alguna metodologÃa para resolverlo sin probar uno por uno (me hacer acordar, salvando las distancias, a cierto problema P7...).
He probado "mecánicamente" intercalar filas y columnas, rotar los números, alinearlos y desplazarlos cifras consecutivas, los he movido a salto de caballo, los he desplazado uno a uno según un camino prefijado en un esquema de 3x3, etc.
No pude encontrar ninguna secuencia automática que me tire la solución.
Gracias.
mira, yo despues de analizarlo vi que cada numero devia ir 2 veces en el medio y 4 a los costados. A base de mis errores vi que si en uno de los dias utilizaba en el medio a determinado numero, los otros 2 numeros que habia ubicado en el medio ese mismo dia, deverian ser diferentes a los que use la siguiente vez que ubique ese mismo numero en el medio.
Asi fue como primero coloque los 3 que irian en el medio cada dìa, y luego mitad razonando, y mitad por tanteo fui hubicando los otros hasta que quedo bien.
no se si se entiende bien, es +o- la idea que segui yo, pero no es del todo clara, espero que la entiendan
bueno, como de costumbre, llegué tarde, solo puedo decir que lo hice por tanteos, un poco como la ultima de Punker.
Y como veran, ya tengo mi Giga Mail de Gmail :-)
Feliz anio a todos y todas
Sà Punker, desde ya yo utilicé el mismo razonamiento, es decir con la base que cada número debÃa estar en el centro dos veces y en los costados 4.
Probé también dejar al medio los números 258, luego 147 y finalmente 369 (hasta aquà la mitad de los dÃas), y después los mismos trÃos pero desplazados 1 ó 2 lugares. Los costados no pude evitar ponerlos al tanteo, sólo algún criterio de evitar que me queden demasiados números juntos por descartar.
Por si sirve de algo para encontrar un método ahà va o que he estado probando
Este esquema corresponde a la solución de Punker. El primer dÃa (123,456,789) son las parrillas (#). Se trata de conservar 'grosso modo' la paridad en las parejas correspondientes a cada número por eso forman dibujos con cierta simetrÃa.
Con esta tabla casi llego a una solución pero no lo he podido rematar. A ver si a alguien le ilumina para que este problema no que de en un mero problema de tanteo. Suerte
1
2
#
2
3
#
*
3
4
+
*
@
4
5
@
+
&
#
5
6
&
@
+
#
*
6
7
+
%
%
@
*
&
7
8
*
+
&
%
@
%
#
8
9
%
&
+
&
%
@
#
*
9
lo siento, ahora vi cómo quedó. Voy a intentar recomponerlo
Por si sirve de algo para encontrar un método ahà va o que he estado probando
Este esquema corresponde a la solución de Punker. El primer dÃa (123,456,789) son las parrillas (#). Se trata de conservar 'grosso modo' la paridad en las parejas correspondientes a cada número por eso forman dibujos con cierta simetrÃa.
Con esta tabla casi llego a una solución pero no lo he podido rematar. A ver si a alguien le ilumina para que este problema no que de en un mero problema de tanteo. Suerte
_ | 1
2 | # | 2
3 | # | * | 3
4 | + | * | @ | 4
5 | @ | + | & | # | 5
6 | & | @ | + | # | * | 6
7 | + | % | % | @ | * | & | 7
8 | * | + | & | % | @ | % | # | 8
9 | % | & | + | & | % | @ | # | * | 9
Muy bien Punker. Felicitaciones.
En el libro comentan un método que permite obtener la solución.
Utiliza unos discos (ruedas llulianas) con unos triángulos dibujados que, al irlos girando, nos van dando las ternas que solucionan la cuestión.
Funciona. Pero debo reconocer que no se por que.
Si este fin de semana hago tiempo despues de los brindis, subiré la explicación para que vean si es entendible.
ola a rod@s
Markelo, esperamos que lo hagas. Por mi parte me resistÃa a ponerme a hacer este acertijo porque probando inicialmente parecia difÃcil y porque el tanteo suele ser aburrido. Pero al final no lo fue tanto. Como ya dijo Punker, no pueden aparecer dos mismos prisioneros en el medio dos dÃas distitnos. Es muy fácil demostrar. Como cada prisionero aparece 2 dÃas en el medio y 4 en los costados, está en contacto con cada uno de los otros prisioneros. De estar dos mismos dÃas en el medio, como el resto de los dÃas estarÃan en los extremos, no estarÃan encadenados entre sà y no podrÃan completarse los 6 dÃas. Asà se arman con un poco de tanteo los 6 grupos del medio. Después si por ej. se tienen incialmente como en este caso los prisioneros 2, 5 y 8 en el medio, como después cada uno de estos números aparece una vez en el medio, 3 de los 6 espacios que en total tienen a sus costados deben ser ocupados por estos mismo números. De lo contrario, no estarÃan nunca en cadenados entre sÃ. Probando un poco colocando los 3 números en alguna de esas 6 casillas, ya sea en dos dÃas (los extremos de un números son ocupados por los otros dos números) o en tres (cada número de los del medio está encadenado a uno de los otros), se llega a la solución con bastante poco tanteo.
Gracias Markelo. Al fin dormiré en paz.
mirándolo bien...creo que todavÃa no...
Gracias Markelo por tomarte el trabajo de comentar la explicación del libro. SÃ, lástima que no se explique porque funciona o más bien como se llega a ese método.
Curiosamente el gráfico circular fue una de las formas que usé yo para abordar el problema.
Primero construà una tabla que acabó en triángulo como el de Yole. Luego vi que con la tabla-triángulo me era difÃcil ir cogiendo parejas que contuviesen todas las cifras...
Y asà fue como hice un cÃrculo con todas las cifras y me bastaba con ir cogiendo tres ángulos con vértice en el cÃrculo para tener una combinación para un dÃa. Adiferencia del diagrama aquà expuesto yo usé ángulos y no triángulos, lo acual, por un lado me evitó pintar asteriscos para diferenciar... y por otro (que era en realidad mi razón principal) los segmentos indicaban caminos o "enlaces" que no se podÃan volver a repetir. Si en una combinación de un dÃa se enlazaban el 1 y el 3, en otro dÃa no se podÃan enlazar. A partir de ahà empecé a probar combinaciones pero fue por tanteo y no llegué a nada.
Me faltó darme cuenta que una forma fácil de conseguir combinaciones que no repitiesen los enlaces era "girar la rueda". Aparte, también debÃa haber llegado a la conclusión de que eran necesarias dos ruedas... y que debÃan ser dos ruedas especiales: Por un lado, debÃan ser "disjuntas" una con la otra y por otro lado cada una por sà misma debÃa dar lugar a 3 dÃas...
Cuando digo que sean disjuntas me refiero a que no compartan ningún enlace. Las dos ruedas del dibujo parece que compartan algo: ambas tienen el segmento 1-4 y el 8-5 pero si nos fijamos bien, en la segunda el segmento 1-4 no es un enlace directo de presos (y en la primera no lo es el 8-6). (Por eso prefiero mi notación con ángulos en lugar de triángulos)
Puestos a escoger un isomorfismo, escogerÃa las clases de congruencia módulo 9.
Y serÃan vectores de 3D sobre ese mod9
Ej: (3,1,4)
Pues bien, el giro de la rueda no es más que sumar el vector (3,3,3) en ese espacio.
(3,1,4) + (3,3,3) = (6,4,7)
(5,9,8) + (3,3,3) = (8,3,2)
(2,7,6) + (3,3,3) = (5,1,9)
¿cómo sabemos que un giro de la rueda no va a dar un segmento repetido? Fácil. En el primer cÃrculo las distancias entre el centro y los laterales son únicas salvo en un caso:
|3-1| = 2 , |1-4| = 3
|5-9| = 4 , |9-8| = 1
|2-7| = 5 , |7-6| = 1
Por eso basta con verificar que en ese caso no hay problema. Y eso se cumple pues 9+3=3 ,
7+3=1 , 9+6=6 , 7+6=4
En el segundo cÃrculo:
|1-2| = 1 , |2-4| = 2
|7-3| = 4 , |3-9| = 6
|5-8| = 3 , |8-6| = 2
También hay un sólo caso de distancia repetida (2) y tampoco hay problema pues: 2+3=5, 6+3=9=0,
2+6=8, 6+6=12=3
Ingeniosa la solución que da el libro pero a mi criterio demasiado arbitraria.
Yo lo que habÃa probado es rotar los números por triángulos, ejemplo tomando para la posición inicial los triángulos 2-6-7, 8-4-3 y por descarte 1-5-9. Luego, para evitar la repetición de los centros, desplacé una fila primero y luego una columna para luego repetir los triángulos con los nuevos números, pero no llegué a nada.
Me quedo con el aporte de Acid.
Publicar un comentario