lunes, 6 de septiembre de 2004
Publicado por
Markelo
en
20:21
Etiquetas: Acertijos de lógica, cruce en bote
Etiquetas: Acertijos de lógica, cruce en bote
Continuando con esta serie de acertijos...
¿Qué pasa si aumentamos la cantidad de Misioneros y Caníbales a cuatro?
Con un bote para solo dos personas es imposible completar el cruce. Alguna vez vi una demostración, pero confieso que mucho no la entendí. Quizá alguno de ustedes encuentre una explicación clara y simple.
¿y con un bote más grande en el que quepan tres personas?
Ahora si. Entonces:
¿Cual es la cantidad mínima de viajes que se deben realizar para que cuatro caníbales y cuatro misioneros crucen de una a otra orilla? Los viajes deben ser hechos de forma tal que en ningún momento, ni en las orillas, ni en el bote, los caníbales superen en número a los misioneros.
Suscribirse a:
Enviar comentarios (Atom)
17 comentarios:
A mi me da que se precisan nueve viajes.
Si no hubiera restricciones necesitamos 7 viajes, los mismos que si, con restricciones, traemos un nuevo misionero. Sin embargo solo necesitarÃamos 5 viajes si hubiera un canÃbal menos. (Por favor que nadie piense que le estoy dando ideas a los misioneros)
1. CCC
2. C
3. CC
4. C
5. MMM
6. MC
7. MMC
8. M
9. MC
También puede ser 8. C y 9. CC para que el C vaya a buscar a su compañero.
A Anibal creo que le falla el paso 7 pq en la 1ª orilla se le comerÃa al pobre misionero.
Alternativa:
1. CCC
2. C
3. MMC
4. MC
5. MMM
6. C
7. CCC
8. C
9. CC
a mà tambien me da en 9 viajes.
mmmmcccc
mmmmc......»ccc
mmmmc...................ccc
mmmmc......«cc..........c
mmmmccc.................c
mmcc.......»mmc.........c
mmcc....................mmcc
mmcc.......«mc..........mc
mmmccc..................mc
ccc........»mmm.........mc
ccc.....................mmmmc
ccc........«c...........mmmm
cccc....................mmmm
c..........»ccc.........mmmm
c.......................mmmmccc
c..........«c...........mmmmcc
cc......................mmmmcc
...........»cc..........mmmcc
........................mmmmcccc
aunque esto lo hice por tanteo, creo esta bien.
creo que a Anibal le falla el viaje 5, al dejar en la primera orilla a un misionero con dos canibales. Y al dejado por el anonimo creo le falla el viaje 3, por que en la otra orilla lo estan esperando dos canibales mas el que viene en la canoa son 3, y solo son dos misioneros.
A Anonimo Ocasional le falla el viaje 3 (3C contra 2M en orilla destino).
Los 9 viajes de ervr están OK.
Pero me están saboteando la agencia de viajes!
Me cuestionan el viaje 5 y 7, yo no le veo error.
Despues del 5º, quedan 1M,1C y 3M,3C
Despues del 7º, quedan 1C y 4M,3C
Disculpa el atrevimiento de mà parte, un novato como yo (solo tengo 3 dias visitando esta página)dudando de tu solución, tus 9 viajes están bién.
De nuevo disculpa esta..... y las que vendrán.
Para el caso de 4M y 4C, con un bote chico (capacidad: 2 personas) es imposible, como dice Markelo. Para demostrarlo, armé el grafo del que hablaba en mi comentario del acertijo anterior. Es un poco engorroso, pero con paciencia sale.
Trataré de explicarlo:
Cada nodo lo represento con 3 valores: (c,m,b), donde c es la cantidad de canibales en la costa A (c=0,1,2,3 o 4) , m es la cantidad de misioneros en esa costa (m=0,1,2,3 o 4) y b es la cantidad de barcas en esa orilla (b=0 o 1). En total tenemos 5.5.2=50 potenciales nodos. En seguida, eliminamos aquellos en que m es distinto de cero y c>m... Porque los canibales se engullen a los m misioneros. Hecho ésto, 26 nodos, pero tambien eliminamos (4,4,0) y (0,0,1)-> todas las personas en una orilla, la barca en la otra, por ser una situación no factible. Quedan 24 nodos. Luego, se trazan los arcos qeu conectan un nodo con otro, tal qeu se pueda pasar de una situacion a otra con un viaje. Por ejemplo, desde el nodo (3,4,1) se puede ir a (1,4,0), (2,4,0) o (3,3,0), mediante el cruce en barca de 2 c, 1 c o 1 m respectivamente (el cruce de 1c y 1c me dejaria la otra orilla peligrosa para los m).
Uf, esto se está haciendo largo...
Finalmente, se ve claramente que el grafo obtenido es disconexo (se puede dividir en dos subgrafos independientes) y la situación de salida (4,4,1) está en un subgrafo y la situación de llegada (0,0,0) en el otro subgrafo.
Me expliqué? Perdón por la extensión, pero en el acertijo anterior Markelo me incitó a que explique cómo funciona la estrategia.
Omità algo:
Cuando digo "eliminamos los nodos tal que m distinto de cero y c>m," debemos eliminar tambien los nodos donde m no es 4 (hay algún misionero en la orilla B) y cOmità algo:
Cuando digo "eliminamos los nodos tal que m distinto de cero y c>m," debemos eliminar tambien los nodos donde m no es 4 (hay algún misionero en la orilla B) y cOmità algo:
Cuando digo "eliminamos los nodos tal que m distinto de cero y c>m," debemos eliminar tambien los nodos donde m no es 4 (hay algún misionero en la orilla B) y cOmità algo:
Cuando digo "eliminamos los nodos tal que m distinto de cero y c>m," debemos eliminar tambien los nodos donde m no es 4 (hay algún misionero en la orilla B) y cOmità algo:
Cuando digo "eliminamos los nodos tal que m distinto de cero y c>m," debemos eliminar tambien los nodos donde m no es 4 (hay algún misionero en la orilla B) y cOmità algo:
Cuando digo "eliminamos los nodos tal que m distinto de cero y c>m," debemos eliminar tambien los nodos donde m no es 4 (hay algún misionero en la orilla B) y cOmità algo:
Cuando digo "eliminamos los nodos tal que m distinto de cero y c>m," debemos eliminar tambien los nodos donde m no es 4 (hay algún misionero en la orilla B) y cOmità algo:
Cuando digo "eliminamos los nodos tal que m distinto de cero y c>m," debemos eliminar tambien los nodos donde m no es 4 (hay algún misionero en la orilla B) y c<m (en la orilla B, los c aventajan a los m)
ervr, no es necesario pedir disculpas.
Si asi fuera, yo tendrÃa que pedir disculpas a los matemáticos que se rompieron el bocho con sus "matrices de adyacencia" y "grafos dirigidos" por no usar ninguno de sus métodos (pensar que mis canÃbales y misioneros eran monedas de un peso y 10 centavos, respectivamente; y el bote era mi dedo)
Hay otra versión para aumentar el número de canÃbales / misioneros, que consiste en poner islas intermedias en vez de aumentar la capacidad del bote.
Para el caso de 4 y 4 con un bote para 2 personas:
1. No pueden ir 2 misioneros en el bote. Si hay 2 misioneros en el bote, las únicas distribuciones posibles son:
MM -MM-> CCCC (se los comen al llegar)
MM MC (si después vuelven 2 canÃbales se comen los misioneros, 2 misioneros dijimos no pueden volver, si vuelven uno y uno estamos en la misma situación por lo que no tiene sentido)
De modo que es imposible cruzar.
En 1. me sobran dos M
Efectivamente, la cantidad mÃnima es de 9 viajes.
No revisé las soluciones que propusieron, pero parece que están bien.
Gracias Lorena por tomarte el trabajo. La verdad no se si alguien apreciará ese tipo de razonamientos, pero te aseguro que yo disfruto mucho leyéndolos.
Anibal: Obviamente, para resolver los problemas de pequeños enigmas, no hace falta conocer de grafos ni de matrices, pero cuando uno intenta generalizar la cuestión, este tipo de abordaje teórico es interesante. A veces, el problema deja de ser "manejable" (PE: 348 M, 348 C y un bote para 143 personas) y la teorÃa nos da estrategias para buscar solucines computacionales.
Juan Pablo: Efectivamente, las variantes son muchas... y pienso seguir usufructuando de ellas cuando no se me ocurra que otros problemas proponer :-)
JP: parece una explicación sencilla aunque aun estoy tratando de entenderla (sobre todo el primer caso)
como es que se puede hacer para que sea cualquier cantidad de canibales y misioneros
si lo tienes escribir a frmartell10@yahoo.es
hola! que tal si me resuelven este, tres canibales y tres misioneros pero en la otra orilla hay un canibal mas esperando?
Saludos,
Al igual que Oscar les Agradecerìa resolvieran el de 3 misioneros y 3 canibales con 1 canibal del lado contrario al que estan los misioneros y canibales.
Publicar un comentario