Les dejo un problema que leí hace tiempo y me gustó.
En cada casilla de un tablero de 2010x2010 se coloca una flecha en alguna de las direcciones arriba, derecha, izquierda o abajo. Un gato cae en alguna casilla del tablero, y en cada paso camina una casilla en la dirección marcada en la casilla que está. Al hacer esto, la flecha de la casilla que abandona rota 90 grados en sentido horario.
Si la dirección le dice que camine fuera del tablero, el gato no se mueve, pero la flecha sí rota, a menos que esté en la esquina inferior derecha del tablero y la flecha le dice que camine hacia abajo, en cuyo caso el gato sale del tablero.
Determina si el gato siempre sale del tablero.
sábado, 5 de junio de 2010
Suscribirse a:
Comentarios de la entrada (Atom)
9 comentarios:
Jajaja, oye Leo, de casualidad ese no es el famosísimo señor gato?
Jeje. No, en este caso es algún otro gato.
En caso de que no se pudiera.
El gato podria estar dando vueltas y vueltas en el tablero infinitamente.
probe gato, vaga infinitamente en un tablero, solo por eso, yo creo que siempre sale, jaja. se escucha muy interesante el problema, lo intenare
solución:
supongamos que no sale, entonces como en a lo mas en 3 pasos cambia de casilla(en el peor caso en el que llegue a una esquina distinta de la de inferior derecha) estara cambiando de casillas infinitamente, por lo tanto el gato pasara por al menos una casilla P una infinidad de veces, ahora nos fijamos en una casiila Q que comparta lado con P. como la flecha en P girara infinitamente abra infinitas veces en las que este apuntando a Q y cuando el gato vuelva a caer en P ira a Q por lo tanto pasara infinitas veces por Q. por lo tanto si el gato pasa infinitas veces por una casilla pasara infinitas veces por las casiilas con las que comparta un lado. De esta manera podemos ver que pasara infinitas veces por todas las casillas y en particular por la inferior derecha. pero a lo más a la cuarta vez que llegue a esta casilla tendra que salir, lo que nos lleva a una contradicción, por lo tanto siempre sale
Bien Daniel! Nota que no era necesario argumentar que cambiaba de casilla, pues si no tu argumento sigue funcionando.
Tampoco importan las dimensiones del tablero.
No he intentado este problema porque me atoré con el "nasty" problema que puso David, el N4 que puse yo y también estuve intentando la desigualdad de hoy, pero espero que mañana ya pueda poder poner una solución :)
Supongamos que el gato esta eternamente dentro del tablero. Entonces a lo mas el gato pudo estar en 3 pasos en el cuadro inferior derecho.
El gato a lo mas puede estar 3 pasos consecutivos en el mismo cuadro (solo en las esquinas), por tanto despues del paso a, al menos existe un cuadro donde a estado en al menos parte entera de a/3[(2010)^2] pasos en algun cuadro.
Si a estado en b pasos en un cuadro, entonces ha estado por lo menos en parte entera de b/(3)4 pasos en cada cuadro que comparte un lado con el primero.
Despues de al menos[(2010)^2]3[(4)^2009][(3)^2009]4 pasos, el gato a estado al menos ((4)^2009)((3)^2009)4 pasos en algun cuadro c_0.
Si a cada cuadro del tablero le asigno un c_i con i la minima cantidad de cuadros por las que hay que moverse de manera horizontal o vertical para llegar a c_0. Y sea x_i tal que al menos el gato ha estado x_i veces en cualquier cuadro c_i.
x_i ≥ parte entera de x_{i-1}/3(4) ≥ parte entera de x_0/[(3)^i][(4)^i] para i≥1.
Si al cuadro inferior derecho le corresponde c_j, j≤2009(2). Por tanto x_j≥x_2009(2) ≥4, lo cual es una contradiccion.
Esta muy padre la configuración del problema.
Tengo basicamente la misma solución que la de Daniel.
Publicar un comentario