miércoles, 16 de febrero de 2011

Problema del Día: Caballo Generalizado

Hola a Todos. ¡Feliz día de San Valentín!

Les dejo un pequeño problema. Consideren un tablero de ajedrez infinitamente grande hacia todas las direcciones y un caballo generalizado de ajedrez que puede, en un sólo movimiento, brincar $p$ cuadrados en una dirección y $q$ cuadrados en otra (una es horizontal y la otra vertical), con $p$ y $q$ mayores a cero. Muestren que este caballo puede regresar a su posición inicial sólo tras un número par de pasos.

10 comentarios:

Anónimo dijo...

Supongo que tanto $p$ como $q$ son fijos, no?

DANIELIMO dijo...
Este comentario ha sido eliminado por el autor.
DANIELIMO dijo...

Hay 3 casos:
1) Si alguno de p o q es impar y el otro par, es fácil ver que en cada movimiento el caballo cambiara de color (blanco a negro, negro a blanco), en la coloracion de ajedrez y
por lo tanto si empieza en blanco necesitara una cantidad par de pasos para volver a blanco, y lo mismo con negro.

2) Si ambos p y q son impares podemos colorear las filas del tablero alternadamente negro, blanco, negro, blanco, y como ambos son impares al realizar un movimiento, la fila a la que cambien sera de distinta paridad y por lo tanto distinto color(iran deblanco a negro y viceversa com el caso anterir). Y concluimos como en el caso anterior.

3) Si ambos p y q son pares, le damos la coordenada (0,0) a la casilla inicial, podemos observar que el caballo solo se moverá en casillas (x,y) con x,y ambos pares, por lo tanto podemos crear un nuevo tablero infinito en el que a la casilla (a,b) le corresponda la casilla (2a,2b) del primer tablero. (hacemos una biyeccion entre los dos tableros) notamos que en este nuevo tablero los movimientos del caballo seran de la forma p/2, q/2. entonces nos podemos fijar de nuevo en las paridades de p/2 y q/2 (habra de nuevo tres casos) y podemos repetir el proceso anterior tantas veces como sea necesario, sabemos que p y q son finitos, por lo tanto tras dividirlos cierta cantidad de veces entre 2 alguno de los dos sera impar y terminaremos con alguno de los primeros 2 casos.

Flavio dijo...

pues hay ocho tipos de saltos del caballo (si p y q son iguales no afecta, solo son 4 diferentes), supongamos que a1,a2,a3,a4,a5,a6,a7,a8 son las cantidades de cada salto de los saltos que aumentan (p,q),(p,-q),(-p,q),(-p,-q),(q,p),(q,-p),(-q,p),(-q,-p). Luego la coordenada x va a ser (suponiendo que parte del origen)
p(a1+a2-a3-a4)+q(a5+a6-a7-a8)=0 por que acaba en el mismo lugar y la coordenada y es p(a5-a6+a7-a8)+q(a1-a2+a3-a4)=0, porque regresa al mismo lugar. Luego supongamos que eso ocurre para una cantida de pasos impar, o sea que a1+a2+...+a8 es impar y tambien +-a1+-a2+-...+-a8, para cualquier combinacion de los signos. Luego si dividimos ambas ecuaciones entre el mcd(p,q), nos queda lo mismo pero pudiendo suponer que mcd(p,q)=1. Luego sea $x \equiv a_1+a_2+a_3+a_4 \pmod{2}$ y $y \equiv a_5+a_6+a_7+a_8 \pmod{2}$, Luego si vemos las ecuaciones modulo 2, nos queda que $px+qy \equiv 0 \pmod{2}$ y
$py+qx \equiv 0 \pmod{2}$ con
$x+y \equiv 1\pmod{2}$
Luego sumando las primeras dos ecuaciones nos queda $(p+q)(x+y) \equiv 0 \pmod{2}$ pero
$x+y \equiv 1\pmod{2}$, entonces
$p+q \equiv 0 \pmod{2}$, luego como (p,q)=1 entonces $p \equiv q \equiv 1 \pmod{2}$
luego la primera ecuacion se convierte en
$1x+1y\equiv 0 \pmod{2}$ entonces
$x+y\equiv 0 \pmod{2}$ lo cual es contradiccion pues teniamos que x+y era impar. Entonces no puede ser x+y impar, entonces es par, que es lo que queria demostrar.

Anónimo dijo...

Después de cada paso, el caballo avanza $p$ cuadros en una dirección y $q$ en otra, de modo que si a cada cuadrito le damos una coordenada de la forma $(x,y)$ donde tanto $x$ como $y$ son enteros, donde el cuadro donde el caballo inicio es $(0,0)$ entonces sabemos que $x=ap+bq$ y $y=cp+dq$ con $a$, $b$, $c$, $d$ todos enteros. Ahora veams que siempre se cumple que $2|a+b+c+d$, ya que en cada movimiento el caballo hace un movimiento en algún sentido horizontal y en algún sentido vertical, de modo que dos valores de $a$, $b$, $c$ o $d$ aumentan o se reducen en uno, y en todos los casos posibles, el cambio en la suma sigue siendo par, y como en un inicio se tenía que la suma de éstos era 0, siempre se conserva esa paridad. De manera similar podemos ver que $2|a+d$ ya que hay un movimiento de $p$ y otro de $q$ entonces si en un movimiento $a$ cambia, entonces $d$ también cambia y viceversa. Como aumentan o disminuyen en uno, se conserva la paridad en todos los casos. Análogamente $2|b+c$.
Supongamos que $x=0$ y que $a=0$ con esto podemos ver fácilmente que $b=0$ de modo que como $2|a+b+c+d$ entonces $2|c+d$ y como podemos ver en cada movimiento se modifica el valor de $c$ o $d$, de uno y sólamente uno, por lo que para que $2|c+d$ significa que ha pasado una cantidad par de movimientos desde el principio, ya que comenzamos con que $c+d=0$ y se ha conservado la paridad de la suma, con lo que conlcuimos que en el caso espefíco en que $x=0$ y $y=0$ también, han transcurrido una cantidad par de movimientos. Similarmente si $c$ o $d$ son cero, se puede probar lo mismo. Y de hecho, por una idea similar, si $2|a+b$ se usó una cantidad par de pasos.
Supongamos que $a\neq 0$, lo que significa que $b\neq 0$, veamos que $x=0 \Leftrightarrow ap=-bq \Leftrightarrow \dfrac{p}{q}=\dfrac{-b}{a}$ y análogamente, $c\neq 0$ y $d\neq 0$ por lo que $y=0 \Leftrightarrow \dfrac{p}{q}=\dfrac{-d}{c}$. Si $mcd \{p,q\}=k$ entonces podemos ver que para algunas $m$ y $n$ en los enteros diferentes de cero, $-b=\dfrac{np}{k}$, $a=\dfrac{nq}{k}$ mientras que $-d=\dfrac{mp}{k}$ y $c=\dfrac{mq}{k}$. Ahora, sabemos que al menos uno de los dos: $\dfrac{p}{k}$ o $\dfrac{q}{k}$ es impar. Supongamos sin pérdida de generalidad que el primero lo es, esto quiere decir que como $2|a+d$ entonces $2|\dfrac{nq}{k}-\dfrac{mp}{k}$ y como supusimos que $\dfrac{p}{k}$ era impar, entonces vemos que $2|n-m$. Como ya vimos, si $n$ y $m$ son pares, eso significaría que $a$, $b$, $c$ y $d$ son pares y es un caso que ya analizamos atrás, por lo que supondremos que ambos son impares. Además, como queremos que $a+b$ sea impar, entonces $a$ o $b$ es par y el otro es impar. Supongamos sin pérdida de generalidad que el par es $a$. Esto implica que $d$ también es par, sin embargo, $a=\dfrac{nq}{k}$ y $-d=\dfrac{mp}{k}$, con $m$ y $n$ impares, por lo que $2|\dfrac{q}{k}$ y $2|\dfrac{p}{k}$ pero eso contradice nuestra hipótesis de que $mcd\{p,q\}=k$ ya que sabemos que $2k|mcd\{p,q\}$ por lo que es una contradicción y entonces $2|a+b$ y por lo mismo, se requiere de una cantidad par de movimientos para regresar al origen.

Unknown dijo...
Este comentario ha sido eliminado por el autor.
Unknown dijo...

Supongamos que el caballo empieza y termina en $(0,0)$.
Sin perdida de generalidad, $p$ y $q$ son primos relativos ya que las coordenadas de donde pise el caballo seran combinación lineal de $p$ y $q$ por lo tanto seran múltiplos de $mcd(p,q)$.
Digamos que el caballo se mueve $a\in \mathbb{Z}$ pasos de $p$ arriba y $q$ derecha, $b$ de $p$ arriba y $q$ izquierda, $c$ de $q$ arriba y $p$ derecha y finalmente $d$ de $q$ arriba y $p$ izquierda. (Si $a$ es negativo significa que dio $-a$ pasos de $p$ abajo y $q$ izquierda).
Lo que queremos demostrar es equivalente a demostrar que $a+b+c+d$ es par.
Tenemos que la coordenada $x$ al final de recorrido es $0=(a+b)p+(c+d)q$ y la coordenada $y$ es $0=(c-d)p+(a-b)q$.
Si $p$ y $q$ son impares entonces $a+b+c+d\equiv (a+b)p+(c+d)q\equiv 0$ $mod$ $2$.
Si uno es par, el otro es impar ya que son primos relativos, porlotanto $p+q$ seria impar. Por lo que $a+b+c+d\equiv (p+q)(a+b+c+d) \equiv (a+b)p+(c+d)p+(a+b)q+(c+d)q\equiv ((a+b)p+(c+d)q)+((c-d)p+(a-b)q)\equiv 0+0\equiv 0$
Entonces $a+b+c+d$ es par y tenemos que el numero de pasos necesarios para regresar al inicio es par.

Georges dijo...

Si p,q son impares ambos, entonces es claro que tiene que ser un número par de movidas.

Si exactamente uno de los dos es par entonces aplicamos la tecnica de colorear como tablero de ajedrez, y entonces se necesita un número par de movimientos.

Ahora si los dos son pares sea x la maxima potencia de dos que divida a los dos, entonces las casillas a donde se puede llegar van a ser solamente las que sus dos coordenadas sean multiplos de 2 a la x.

Por lo tanto si nos olvidamos de las casillas donde no nos podemos mover y "juntamos" las casillas donde si nos podemos mover, entonces la coordenada de cada casilla si era de la forma "2^xa,2^xb" se transforma en "a,b" y entonces ahora nuestros posibles movimientos van a ser p/2^x y q/2^x.

Como x es la maxima potencia de dos que divide a los dos entonces alguno de estos dos nuevos números es impar y por los primeros casos acabamos.

Manuel Alejandro dijo...

Separaré en dos casos:

CASO 1: Si $2^{k}\Vert p\neq2^{l}\Vert q$, entonces hacemos una coloración tipo tablero de ajedrez, pero van a pintarse del mismo color cada cuadro de $2^{min(k,l)}$. De este modo, podemos ver que sólo se caerá en casillas “homotéticas” a la del cuadro mayor en la que se encuentra, solo que irá cambiando de color blanco a negro y de negro a blanco, nunca de blanco a blanco o de negro a negro, entonces necesita una cantidad par de movimientos para llegar al mismo color.

CASO 2: Si $2^{k}\Vert p,q$, entonces lo que haremos es colorear cada $2^{k}$ columnas consecutivas de color blanco, luego las próximas $2^{k}$ de negro, y así alternadamente, entonces, siempre va a cambiar de color al desplazarse de una posición a otra posible, entonces necesita una cantidad par de pasos para llegar al mismo color de columna.

Enrique dijo...

Le asignamos coordenadas al tablero, done $(0,0)$ es la posición inicial del caballo. Ahora, desde una casilla $(a,b)$, el caballo puede llegar a las siguientes posiciones: $(a+p,b+q),(a-p,b+q),(a+p,b-q),(a-p,b+q),(a+q,b+p),(a-q,b+p),(a+q,b-p),(a-q,b+p)$
Tenemos que la paridad de $a+p$ es igual a la de $a-p$ para cualquier entero $a$.
Sea $p=2^{k}x$ y $q=2^{k}y$, donde $2^{k}\Vert p,q$. Tenemos que o ambos $x$ y $y$ son impares o que uno es par y el otro impar. Ahora, demostraremos que sólo en una cantidad de par pasos se puede llegar a $(0,0) \pmod{2^{k+1}}$.
Caso 1: $x,y$ son impares
Aquí es evidente que sólo después de sumar $x$ o $y$ un número par de veces podremos llegar a $(2^{k}(2),2^{k}(2))$, que es lo mismo que $(0,0)$ módulo $2^{k+1}$
Caso 2: Sin pérdida de generalidad, $x$ es impar y $y$ es par.
Tenemos que tanto las sumas en el elemento izquierdo como en el elemento derecho tienen que tener un número impar de $x$, y como $y$ es par, al sumar $y$ no se cambia la paridad de la suma, luego son necesarios un número par de sumandos.
Así, se necesita un número par de pasos para regresar a la posición inicial.

Publicar un comentario