• Registro
Foro de preguntas y respuestas de matemáticas, de cualquier nivel. Cuánto más interesantes, divertidas o intrépidas, mejor.
Aviso: Te invitamos a conocer la página de Facebook de la UCIM

Ganas puntos al hacer preguntas, contestarlas y, sobre todo, si tu respuesta es seleccionada como la mejor.
Registrate como usuario para participar en el foro. También puedes utilizar tu identidad de FB Utiliza el botón azul para ingresar (si usas tu identidad de FB y estás logeado en FB, automáticamente te reconoce).

El irracional tiene una página en FB. El Irracional






Mostrar que el número de caminos de (0,0) a (m,n) en el plano latíz que no repiten vertices es menor a $2^{mn}$

+1 voto
Un camino en el plano del punto $(0,0)$ al punto $(m,n)$ es una secuencia de puntos del plano con coordenadas enteras tal que dos puntos consecutivos difieren en exactamente una de las coordenadas y la diferencia entre las coordenadas distintas es uno. También pedimos que el primer vértice sea $(0,0)$ y el último sea $(m,n)$.

 

Si además todos los puntos del camino $(x,y)$ cumplen $0\leq x \leq m$ y $0\leq y\leq n$ y ningún punto se repite decimos que el camino es bueno.

 

Demuestre que el número de caminos buenos es menor o igual a $2^{mn}$.

logré probar que es menor a $\frac{4^{(m+1)(n+1)}}{3}$ puesto que en cada momento hay que moverse en una de las cuatro direcciones y  direcciones. Y hay a lo más $(m+1)(n+1)-1$ movimientos. Usando que le número de caminos de longitud $x$ es a lo mas $x$ y que la longitud es a lo mas $(m+1)(n+1)-1$ nos queda la cota anterior haciendo la suma de la sucesión geométrica. Pero este resultado es mucha mas débil del que se pide.
preguntado por gamamal (2,400 puntos) Jul 24, 2015 en Preguntas
editado por aubin Ago 4, 2015

1 Respuesta

+2 votos
 
Mejor respuesta
Dado un camino bueno $C$ de $(0,0)$ a $(m,n)$ vamos a definir cuales cuadros de la cuadrícula están "debajo" del camino: conectamos los puntos $(0,0), (0,-1/2), (m+1/2,-1/2), (m+1/2,n), (m,n)$ en ese orden con una poligonal $P$; como $C$ es bueno, $P$ junto con $C$ forman una curva cerrada simple y decimos que los cuadros que estén adentro de esa curva están "debajo" de $C$.

Ahora, dos caminos distintos $C$ y $C'$ tienen distintos conjuntos de cuadritos por debajo (porque dado el conjunto de cuadros, podemos recuperar el camino  como la frontera de la figura que forman) así que el número de caminos es a lo más el número de subconjuntos de los $mn$ cuadros de la cuadrícula.
respondido por Omar Antolín (32,640 puntos) Jul 25, 2015
editado por Omar Antolín Jul 25, 2015
Ah ya veo, está muy padre esa idea. Debería ser obvio por qué dos caminos distintos inducen conjuntos de cuadritos disjuntos? No se me ocurre como escribir una prueba de este hecho.
Ok, ya vi como. Muchas gracias, te importa si escribo esta solución en mathlinks? Es de un nacional de canadá y ahí no tiene ninguna solución.
Dado el conjunto de cuadritos, el camino se puede recuperar como la frontera de la unión de los cuadros. Si quieres poner esta solución en mathlinks, adelante!
Licencia Creative Commons
Este obra está bajo una Licencia Creative Commons Atribución-NoComercial-CompartirIgual 2.5 México.

powered by UCIM

...