miércoles, 2 de febrero de 2005
El problema 8 del PQRST 12 me recordó un viejo método que sirve para contar caminos que quizá les interese.
No es exactamente la misma idea ya que este método solo sirve para contar caminos de longitud mínima. Sin embargo, igual les va a gustar y puede que a alguno le inspire para encarar el P8.
En la siguiente figura: ¿De cuántas maneras se puede ir de A a B?
Entendemos por camino de "longitud mínima" aquel que en ningún momento nos aleja de nuestro objetivo. En este caso, vale avanzar únicamente hacia la derecha y hacia abajo.
No son tantos caminos y los podrán contar rápidamente por su cuenta. Hagan la prueba antes de seguir leyendo.
Lo que debemos hacer es ir numerando los vértices de la siguiente manera
En A colocamos un "1" ya que hay una única manera de llegar allí. (ya estamos allí)
Avanzamos al siguiente vértice (a la derecha o hacia abajo) y también les colocamos un "1" ya que solo hay una manera de hacerlo.
Avanzamos un lugar más y colocamos un "2" ya que hay dos maneras de llegar allí: Derecha / Abajo o Abajo / Derecha.
No es casual que 2 sea la suma de 1+1.
Justamente, de lo que se trata el método es de ir completando los vértices con la suma de los valores con que están numerados los vértices más cercanos que conducen a el
en el ejemplo, seguimos numerando así:
No les será difícil seguir rotulando los vértices hasta poner un "13" en "B" que nos da la cantidad total de maneras que hay de llegar de A a B.
Quienes se interesen por este problema, pueden intentar responder una pregunta aparentemente más complicada, pero muy simple de responder siguiendo este método:
¿De cuantas maneras diferentes puede llegar una torre de ajedrez desde la esquina superior izquierda a la esquina inferior derecha?
Recuerden que la torre solo avanza en horizontal o en vertical, nunca en diagonal; además, los recorridos deben ser de longitud mínima, es decir, solo se mueve hacia la derecha o hacia abajo.
Quienes se sienten a resolverlo y tengan además un mínimo de formación matemática, recibirán una pequeña sorpresa (o no tanto) cuando vayan por la mitad del algoritmo.
Para el desarrollo de este texto me base mayormente en el libro "Inspiración AJA" de Martin Gardner
Suscribirse a:
Enviar comentarios (Atom)
15 comentarios:
Una forma que involucra de alguna manera lo mismo (porque los 1 por ej se deben a que no se puede ir ni para atrás ni para la izquierda) pero que es más fácil y rápida es que se deben hacer 4 movimientos hacia la derecha y dos hacia abajo. Entonces se tiene 6!/(2!*4!)=15. Las únicas combinaciones que no se pueden son AADDDD y DDDDAA, asà que son 13 en total. Para el de la torre, ésta debe hacer 7 movimientos hacia la derecha y 7 para abajo. Puede llegar de C(14,7)=3432 maneras.
Ajá! Y esa "sorpresa" es conocida con dos nombres (dos apellidos, para ser exacto) distintos...
Ok jean paul, pero lo que proponés se puede hacer siempre y cuando las reticulas sean simples como las que propuse. Si la reticula es un poco más compleja y los caminos imposibles son tantos como los posibles, ya no serÃa tan fácil calcularlos
Lorena: efectivamente. ¿curioso, no? (en realidad, no es tan extraño y parece que tiene su justificación matemática)
La justificación matemática esta es el comentario de Jean Paul...
Va de nuevo, con un poco más de atención:
La justificación matemática está en el comentario de Jean Paul
En el caso del primer problema para transladarse del punto A al punto B se tienen 13 caminos diferentes....Una pregunta adicional interesante es ¿Cuantar rutas hacen mÃnima la distancia recorrida ?...¿Exite un algoritmo para resolver este problema para casos no triviales?
210+252 = 462
Girando el tablero 45 grados en sentido horario toma una forma 'triangular' un poco más conocida (al menos para mÃ). Me está faltando el segundo apellido.
JAJAJAJAJAJA. ¡Qué idiota!
Gracias por la correción... igual no entiendo la sorpresa... da lo mismo, usualmente mi cerebro decide dormir en ciertas épocas.
JP, uno de ellos lo ocuparon como nombre para un lenguaje de programación y el otro era de un tartamudo. (HabrÃa que averiguar el origen de este triángulo, creo que ya lo conocÃan mucho antes los chinos).
Hay un tercer apellido que también entra en esta configuración. Tiene que ver con una sucesión numérica famosa.
..... Taaaannntoooooo!!!
Este problema puede resolverse en forma general, si solo podemos avanzar en nuestro camino, y el metodo de resolucion es de lo mas curioso.
El ejemplo tipico es el del rey de ajedrez, que partiendo de e1, desea llegar a e8 en la menor cantidad posible de movimientos (obviamente, 7), y queremos conocer el numero de caminos distintos. Definiremos una variable por cada posible direccion de movimiento, en este caso dos (el rey solo se movera un paso hacia arriba en la direccion "y", que combinara con un movimiento hacia el costado en direccion "x"; un movimiento inicial Re1->f2 se escribira en forma de producto: xy, donde un movimiento hacia la derecha tendra exponente igual a 1, y hacia la izquierda igual a -1).
Recapitulando: los movimientos posibles son: y (un paso hacia adelante), xy (del tipo e1-f2) y x(-1)y (del tipo e1-d2).
Se forma el polinomio (y + xy + x(-1)y), y, como queremos 7 movimientos, elevamos este polinomio a la septima potencia. (x(-1) significa x elevado a la -1).
Como ademas queremos un movimiento del tipo y**7 (y elevado a la septima), al desarrollar el polinomio elevado a la septima potencia, miraremos el termino que corresponde a y**7: sera 393, que es el numero de caminos.
Este metodo puede aplicarse a la torre que llega al angulo opuesto en 13 movimientos, donde da, como alguien dijo antes, el combinatorio C(13,7) por ser este el coeficiente correspondiente en el desarrollo de Newton de (x+y)**13.
No sirve, tal cual esta, para el problema como lo planteaste, porque hay casillas prohibidas (x**2 e y**4), pero lo que se hace en estos casos es restar, en el desarrollo de (x+y)**6, la cantidad de caminos que arrancan en x**4 (1) y de y**2 (1) al combinatorio C(6,4)=15, lo que da los trece caminos que ya se conocen. (¿Por que el combinatorio C(6,4)? Porque buscamos el coeficiente de x**4.y**2 en el desarrollo de (x+y)**6).
Esto pudo no haber sido claro en absoluto. Consulten lo que quieran.
Saludos
Y sigo:
¿De cuantas maneras distintas puede llegar una torre situada en un rincon del tablero, al otro rincon, si solo le imponemos que no retroceda?
Puede llegar en un minimo de 2 movimientos, y en un maximo de 13. Hay que contar TODOS los caminos, y encontrar una forma piola de hacerlo.
Saludos.
José:
Es realmente muy interesante. Supongo que hay muchas otras maneras de encarar el problema. Tengo entendido que también tiene que ver con los llamados "numeros de catalán" (o algo asÃ)
¿No probaste con el problema 8 del PQRST 12?
eleazar usa la piramide de Pascal y suma
Publicar un comentario