Hace poco estaba viendo un video en la academia Khan , donde resuelve un problema sobre cómo encontrar todos los caminos posibles en una cuadrícula n X n desde la posición superior izquierda hasta la posición inferior derecha, solo yendo hacia abajo o hacia la derecha.
Básicamente, el enfoque que toma se basa en usar el triángulo pascal y contar las formas de llegar a una determinada posición y agregarlas al número de formas hasta el momento.
Me interesé en esto y traté de generalizar una fórmula para encontrar la cantidad de caminos posibles en una cuadrícula de X m.
Mi idea es la siguiente: supongamos una cuadrícula de 2 x 3. Comenzamos en la parte superior izquierda y necesitamos ir a la parte inferior derecha (asumiendo que solo podemos movernos a la derecha/abajo). Un camino posible sería
Resulta que todos los caminos posibles en una cuadrícula de 2 x 3 tendrán una longitud de n + m = 5 en este caso.
Si vemos el movimiento a través de la cuadrícula como una especie de serie de comandos (abajo/derecha), podemos encontrar todas las permutaciones posibles de abajo/derecha calculando Por ejemplo, en la cuadrícula de 2 x 3 calculamos , que nos daría todas las permutaciones posibles de
Sin embargo, eso también contaría down2, down1, ... como combinación válida, que no lo es, puede ir como máximo 2 veces hacia abajo, pero debe comenzar con down1 desde la posición inicial. La fórmula refinada se ve así (para obtener combinaciones únicas de comandos):
)
En una cuadrícula cuadrática de 5 x 5, lo anterior se evaluaría a 252, en una cuadrícula de 2 x 3 serían 10 caminos. Por lo que puedo ver, parece un enfoque correcto, al menos por algunos ejemplos que probé.
Mi siguiente paso fue tratar de escribir una prueba para esto, pensé que tal vez sería posible una prueba por inducción. Pero mi pregunta es, ¿qué es en este caso (¿pasos? ¿tamaño de cuadrícula?) si me gustaría escribir una prueba para esto. ¿O no es posible la inducción en este caso?
Tal vez este ejemplo satisfaga su necesidad.
Suponer que de los números en debe ser seleccionado.
Podemos comenzar escribiendo los números en todos los órdenes posibles, y luego escoger el extrema izquierda como los seleccionados. Hay pedidos y obtenemos algo como:
Ahora observe que, por ejemplo, los pedidos 12345 y 12354 dan como resultado la selección 123. Ahora pregúntese cuántos pedidos se pueden encontrar que dan como resultado la selección 123. Para el orden de los números 1,2,3 hay posibilidades y para el orden de los números 4,5 hay posibilidades. Eso significa que la selección 123 es el resultado de del preparativos. Para reparar este conteo en exceso dividimos por y terminamos con selecciones distintas.
Sugerencias para su prueba:
rightsy
lefts.rightsson equivalentes y todos downsson equivalentes , es decir, down1es lo mismo quedown2
q el ornitorrinco
drhab