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}$

Question

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.

Answer 1

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.

Comments

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!