La coloración de ajedrez suele ser muy útil en problemas de tableros, especialmente cuando te dicen que de una casilla solo te puedes mover a otra con la que comparta lado, por que así te queda la invarianza de que de una casilla negra solo te puedes mover a blanca y viceversa.
Les dejo dos problemas que salen con esta idea.
Problema 1: Considera un tablero de mxn donde m y n son enteros impares. Un movimiento permitido es ir de una casilla a otra con la que comparta lado. Demuestra que no es posible empezar en una casilla, pasar por todas las demas casillas del tablero exactamente una vez y regresar a la casilla inicial.
Problema 2: Se tienen dos triangulos equilateros de lado n con n entero positivo, esos triángulos se pegan de tal forma que compartan un lado. Cada uno de estos triángulos se divide en n^2 triangulos equilateros mediante lineas paralelas a sus lados (por ejemplo si n=2 sería unir los puntos medios de los lados y te quedarían 4 triangulos equilateros). A y B juegan un juego en este tablero, A juega con una ficha roja y B juega con una ficha azul que inicialmente se ponen en esquinas opuestas del tablero (los vértices mas lejanos de cada uno de los triángulos equilateros). En cada turno los jugadores mueven su ficha a una casilla que comparta lado con la casilla en la que estaba. Para ganar el juego un jugador debe mover su ficha a una casilla en la que se encuentre la ficha del otro jugador (comerse la ficha) o llegar a la esquina opuesta de la que estaba. Si A y B juegan alternadamente y A empieza, ¿Quién tiene estrategia ganadora?
¿Si se entiende?
Con esta idea de colorear como ajedrez salía el problema 3 del regional pasado!
el segundo solo tienes que fijarte que para cualquier n, la distancia desde A hasta B es 2b por lo que es par, amm bueno lo coloreas y ves que A empieza en un color y B en otro, despues A avanzara al color de B y B avanzara al color que A no tiene por lo que es facil entender que B jamas tirara a la casilla de A y nunca podra comenselo, asi que la estrategia ganadora para A es avanzar de frente y en caso que se encuentre con B comerselo, si B la esquiva, significa qe no siguio el camino mas corto (el de frente, el que A sigue) y A llegara primero a la casilla contraria. Si eh estado leyendo el blog y si me han salido algunos pero no habia podido escribir.
ResponderBorrarProblema 1 (igual tarde pero aqui esta...)
ResponderBorrarHagamos nuestra coloracion como un tablero de ajedrez, sin perdida de generalidad podemos suponer que las esquinas del tablero son negras( si son blancas se procede de la misma manera). Hagamos las siguientes observaciones:
Tenemos una cantidad de par de cuadros negros, e impar de cuadros blancos.
Queremos que de cada cuadro se vaya a un cuadro adyacente una vez, y se llegue a cada cuadro una vez.
Ahora veamos que si comenzamos en una cuadro negro, la cantidad de veces que se tendra que llegar de un cuadro blanco a uno negro es igual a (mn+1)/2 (que es la cantidad de cuadros negros) pero unicamente tenemos (mn -1)/2 cuadros blancos,y como por cada cuadro blanco se debe ir unicamente a un cuadro negro, no es posible volver al cuadro inicial recorriendo cada cuadro una sola vez, usando el mismo argumento se puede demostrar que no es posible si se inicia en un cuadro blanco, pues la observacion hecha implica que no se podra llegar a todos los cuadros negros sin pasar almenos 2 veces por un mismo cuadro blanco.
Si tienen alguna duda o correcion a la solucion lo escriben como comentario por favor.
ResponderBorrarYo tengo unas soluciones parecidas, solo que no tan formal como la de Raúl, lo explicare como me paso por la mente cuando lo estaba intentando:
ResponderBorrar1.- Tomas tu cuadrícula y coloreas como ajedrez (obviamente,)yo empece con una esquina negra y por esto todas me quedaron negras por ser filas y columnas impares. Se puede saber que siempre vamos a tener x fichas blancas y x+1 fichas negras (si empiezas la coloracion con negras) (x=una cantidad que puede variar depende del tamaño del tablero)
Tenemos que solo hay x movimientos de blancos a negros, como empezamos por uno negro, pasando a uno blanco podriamos descartar un cuadrito negro y ya nos quedarian los mismos negros y mismo blancos, pero sabemos que tenemos que llegar a ese cuadrito negro otra vez. Entonces seguimos teniendo x+1 negros y x blancos y solo tenemos x movimientos de blancos a negros, por lo tanto no se va a poder, siempre va a sobrar almenos un negro(sin ser racista). :D
Ahora que leí la solución de Raúl, se que pude haber expresado x como (mn-1)/2 y x+1 como (mn+1)/2 . Pero no se me ocurrio nada asi para obtener los valores.
2.-Como tenemos que van a ser dos triangulos iguales, entonces sabemos que va a haber un número par de casillas, coloreamos las casillas en blanco y negro sin que se repitan las que comparten lado, en un lado A empieza con un color y B con el otro color en la otra esquina. Si los dos toman los caminos mas cortos, podemos saber que A llega primero por tener el primer movimiento. Se sabe que en cada turno A cambia al color de B y después B se mueve al que era el color de A. Entonces es imposible que B se coma a A, almenos que A no se mueva (no se si vale)porque para que B se coma a A, A tendria que estar del color opuesto, pero como en su turno, siempre cambia al color de B para el turno de B ya son del mismo color. Entonces A tiene la estrategia ganadora.
El del 13 de Septiembre lo saque usando una combinacion del ultimo teorema de fermat y una relacion de los numeros primos con el numero pi. Encontré una solucion muy bonita pero no existe una compu con suficiente memoria para escribir mi solución. (no como creen, no me salió)
Si estan bien las soluciones!
ResponderBorrarLes recuerdo que deben de escribir su solución de todos los problemas, no importa si alguien mas ya publico su solución.
NO se vale que A no se mueva, Diego, A y B siempre se tienen que mover. Y da lo mismo si ponene x o (mn-1)/2
ResponderBorrarok, jaja sigue siendo lo mismo, solo estaba aclarando...
ResponderBorrarPara el problema 2, tenemos nuestra coloración de ajedrez, A inicia en un triángulo negro y B en uno blanco, tenemos que A en todos sus tiros iguala el color del triángulo en el que se encuentra B y que B, en todos sus tiros hace que los triángulos en los que se encuentran A y B sean de diferente color es por esta razón que B nunca se puede pasar al triángulo en el que se encuentra A y B nunca puede ganar de esa manera, A tiene la estrategia de tomar el camino más corto desde su extremo hasta el extremo en el que se encuentra B, y comerselo en caso de tener la oportunidad, el camino más corto es pasar a lo más por 2 triángulos por renglón, en el primer paso, es claro que A pasa directo al renglon de enfrente, pero en su segundo movimiento tiene que pasar por algun triángulo de los que tiene a un lado antes de pasar al renglon de en frente, no importa a donde pasara pero el punto es que vaya lo más rapido posible al renglón de adelante, B independientemente de si sigue un camino igual de largo que A o no, siempre pierde porque A es el que tira primero y pues es fácil observar que si ambos toman un camino igual de largo, llega primero a la meta el que inicia primero. A tiene la estrategia ganadora.
ResponderBorrarPara el problema 1... creo que estoy mal xD pero si tienes tu tablero coloreado de ajedrez, tienes mxn casillas, tomando cualquier casilla dentro de nuestro tablero, tenemos que para pasar por todas las casillas exactamente una vez, para pasar por todas las demás casillas, tenemos que hacerlo en mn-1 pasos ya que son mn-1 casillas las que nos quedan al haber elegido nuestra casilla inicial pero como tenemos que regresar a esta casilla, en total haremos el recorrido en mn pasos pero como de una casilla negra solo pasas a una blanca y viceversa, tomate la casilla inicial, en los pasos impares pasas a casillas de color contrario al inicial y en los pares a casillas del color de la inicial, despues de mn pasos, como mn es impar, estas en una casilla del color contrario al que iniciaste por lo que no es posible regresar a esta casilla.
María estan bien tus dos soluciones!
ResponderBorrarEl problema 1 es un problema medio conocido, y el problema dos es de un selectivo de Argentina para ir a la IMO.
wiii!!!!! estoy bien feliz!!!! wiii
ResponderBorrar