Si lo quieres compartir o guardar
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)
Suscribirse a:
Enviar comentarios (Atom)
Entradas
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
ResponderEliminar1 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
Exacto Pablo.
ResponderEliminarOtra 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