Hay una mesa con celdas infinitas. Una hormiga comienza desde la celda $(1,1)$ y cada vez puede moverse una celda hacia arriba o hacia la derecha. Antes de comenzar a moverse, se le da una secuencia infinita de números de celdas como $<(x_{1},y_{1}) , (x_{2},y_{2}), ... , (x_{n}, y_{n}) , .... >$. Después del paso $k$, la celda número $(x_{k},y_{k})$ estará envenenada y si la hormiga va allí o ya está allí, morirá. Demuestra por inducción que la hormiga puede vivir para siempre si conoce los elementos de la secuencia desde el principio :)
Respuesta
¿Demasiados anuncios?
sewo
Puntos
58
Pista: Considera para cada nivel del grafo la cantidad de celdas posibles a las que la hormiga puede llegar con vida, menos la cantidad de celdas en niveles posteriores que ya están envenenadas en ese momento.
Demuestra que este número no puede disminuir.
Concluye que hay celdas alcanzables en cada nivel.
0 votos
¿Cuál es la suma de las coordenadas $x$ y $y$ de la hormiga en el paso $k$? ¿Cuántas celdas puede alcanzar la hormiga en el paso $k$? ¿Cuántas de ellas pueden ser envenenadas antes o en el paso $k$?
0 votos
@didgogns Hay un número infinito de células. Después de cada paso, una célula queda envenenada, por lo tanto K-1 células pueden quedar envenenadas antes del paso k.