jueves, 1 de agosto de 2013

1189 - Recorridos

¿De cuántas formas diferentes se puede ir de A hasta B, en este tablero de 8 x 8 si se puede ir de izquierda a derecha, de abajo a arriba y en diagonal de abajo hacia arriba y hacia la derecha? (No es válido retroceder)



Si lo quieres compartir o guardar
Share/Bookmark

2 comentarios:

  1. Si contamos los vertices de cada cuadrado, tenemos una matriz de 9*9 vertices, Si hacemos un recorrido para arriba o derecha salvo los de los bordes se puede llegar desde 3 puntos distintos entonces haciendo la matriz de 9*9 queda

    1 17 145 833 3649 13073 40081 108545 265729
    1 15 113 575 2241 7183 19825 48639 108545
    1 13 85 377 1289 3653 8989 19825 40081
    1 11 61 231 681 1683 3653 7183 13073
    1 9 41 129 321 681 1289 2241 3649
    1 7 25 63 129 231 377 575 833
    1 5 13 25 41 61 85 113 145
    1 3 5 7 9 11 13 15 17
    1 1 1 1 1 1 1 1 1

    Por lo tanto hay 265.729 caminos distintos de A a B

    ResponderEliminar
  2. Exacto Pablo.
    Otra forma de resolverlo es la siguiente, si no hubiera diagonales, hay que hacer 8 pasos horizontales y 8 verticales, 16 en total, 8 en cada dirección, esto puede hacerse en C(16;8)=12870 formas

    Con diagonales cada vez que se hace una diagonal, se debe hacer un paso menos en horizontal y uno menos en vertical.
    Entonces con una vertical hay que hacer, 7h, 7v y 1d = 15 pasos que se pueden hacer en C(15;7,7)=
    15! / 7! x 7! = 51480 formas
    Con dos diagonales, tenemos 6h, 6v 2d = C(14;6,6)=84084 formas

    3 diagonales: C(13;5,5)=72072 formas
    4 diagonales: C(12;4,4)=34650 formas
    5 diagonales: C(11;3,3)=9240 formas
    6 diagonales: C(10;2,2)=1260 formas
    7 diagonales: C(9;1,1)=72 formas
    8 diagonales: 1 forma

    Total 265729

    ResponderEliminar

Si quieres deja un comentario, si la entrada tiene mas de 15 dias deberás esperar a que la autorice y por favor si no tienes gmail deja tu nombre si no quedas como anónimo. Gracias!