Combinatoria - caminos

Avatar de Usuario
Martín Vacas Vignolo
Mensajes: 404
Registrado: Mié 15 Dic, 2010 6:57 pm
Nivel: Exolímpico

Combinatoria - caminos

Mensaje sin leer por Martín Vacas Vignolo »

Voy a usar algunas cosas básicas de combinatoria de que pueden leer del post de Mariano (http://omaforos.com.ar/viewtopic.php?f=5&t=7) para aplicarlas a algunos problemas.


Problema 1

Se tiene una cuadrícula de 4x4 (que tiene 5 líneas horizontales y 5 verticales). Sea X el vértice inferior izquierdo y Y el vértice superior derecho. Se tiene que caminar siempre por las líneas y siempre para la derecha o para arriba.

a) ¿Cuántos caminos hay desde X hasta Y?

Bueno, notemos que al ir siempre para la derecha y para arriba, en total (en cualquier camino) voy a ir 4 veces para la derecha y 4 veces para arriba. Entonces en los distintos caminos que tenga para ir desde X hasta Y voy a tener que ir eligiendo direcciones cada vez que llego a un vértice, pero no cualesquiera, sino que las tengo fijas (en total 4 para arriba y 4 para la derecha).
Luego, el problema lo podemos pensar como los anagramas (ver apunte Mariano) de la palabra AAAADDDD donde A es elegir ir para arriba y D es elegir ir para la derecha. Finalmente la cantidad de caminos será [math].

b) ¿Cuántos caminos hay desde X hasta Y recorriendo exactamente 8 segmentos?

Esto es equivalente al a), ya que al recorrer exactamente 8 segmentos, tendrán que ser 4 para arriba y 4 para la derecha.

c) Sea Z el vértice (2,3) ¿Cuántos caminos hay desde X hasta Y, pasando por Z?

[Z es el vértice (2,3) o sea es la intersección (donde se chocan) de la segunda fila y la tercera columna]

Este ítem lo podemos pensar como dos partes por separado. Al tener que pasar sí o sí por Z, podemos calcular la cantidad de caminos que hay para LLEGAR a Z desde X y la cantidad de caminos que hay para llegar a Y desde Z. Luego multiplicaremos esas cantidades, ya que por cada camino para llegar a Z (desde X) voy a tener todos los caminos para llegar a Y (desde Z).

La cantidad de caminos para llegar desde X hasta Z es un nuevo problema, donde tendríamos una cuadrícula de 3x2 (con 4 líneas horizontales y 3 verticales).

Luego esa cantidad es la cantidad de anagramas de la palabra AAADD, pues siempre voy a tener que hacer dos pasos para la derecha y 3 para arriba. Esos anagramas son [math].

La cantidad de caminos para llegar a Y desde Z será, pensando de la misma forma en una cuadrícula de 1x2, [math].

Finalmente, la cantidad de caminos que hay para ir desde X hasta Y, pasando por Z, serán [math].

d) ¿Cuántos caminos hay desde X hasta Y, sin pasar por Z?

Bueno, un camino que une X con Y, puede pasar por Z o puede NO pasar por Z (y no hay otra posibilidad), por lo tanto la cantidad total de caminos (que eran 70) serán los que pasan por Z (30) más los que no pasan. Finalmente los que no pasan por Z serán 40.

e) Supongamos que la CASILLA [2,3] tiene fuego, o sea si caminás por esa casilla te quemás, te morís y no podés seguir caminando (y sí, si estoy muerto no puedo caminar... :) ). ¿Cuántos caminos hay para ir desde X hasta Y?

Bueno, la casilla [2,3] es la casilla que tiene como vértices los (2,3), (2,4), (3,3) y (3,4).

Al no poder caminar por ahí, el problema sería equivalente a un problema donde tendría un tablero de 4x4 con una L de 4x4 y un cuadrado de 3x3 (ya que los 8 caminos que llegan a la casilla [2,3] y los caminos de esa casilla se tachan).

Notemos que el tablero ahora es simétrico y que una vez que lleguemos al vértice (1,2) ó al (4,5) no tenemos otra chance que seguir de una única forma. Por lo tanto lo único que hay que hacer es calcular cuántos caminos tengo para llegar desde X hasta, por ejemplo el vértice (1,2). Esos caminos son los anagramas de la palabra AAAAD que son 5 (la D puede ir en cualquiera de los 5 lugares). Y como es simétrico, también tendré 5 caminos para ir desde X hasta el vértice (4,5).

Finalmente tengo 10 caminos para llegar desde X hasta Y sin morirme.
2  
[math]
crimeeee
Mensajes: 41
Registrado: Jue 03 Feb, 2011 1:14 am
Nivel: Exolímpico

Re: Combinatoria - caminos

Mensaje sin leer por crimeeee »

Un problema para practicar:

*Una hormiga camina por las líneas de un tablero como el de la figura, con 4 casillas de ancho y 5 casillas de alto. ¿De cuántas diferentes maneras puede ir desde A hasta B, sin pasar dos veces por un mismo punto?
Responder