Download problemas de coloración e invarianza

Entrenamiento para la 27° OMM, San Luis Potosí.
PROBLEMAS DE COLORACIÓN
Las siguientes piezas se llaman tetraminos tipos
la y se pueden reflejar y obtener piezas distintas.
y cuadrado, repectivamente. Observa que
1. A un tablero de ajedrez se le quitan dos esquinas opuestas, ¿puede el resto ser llenado con
fichas de x ?
2. Una hormiga camina por un tablero de ajedrez de modo que siempre va de la casilla en la que
está a una casilla adyacente (dos casillas son adyacentes si tienen un lado en común). Si la hormiga
comienza en la casilla inferior izquierda y quiere visitar cada casilla exactamente una vez, ¿será
posible que la última casilla que visite sea la casilla de la parte superior derecha?
3. En un tablero de 2013x2013 se quiere hacer un recorrido con un caballo que inicie en cualquier
casilla y que, después de haber visitado cada casilla exactamente una vez, termine en la casilla en
que inició, ¿es posible hacerlo?
4. Totoro y Aldonza juegan el siguiente juego: hay una fila de 4026 cajas y en cada una de ellas hay
algunas galletas. En cada turno, Totoro toma una de las cajas que están en los extremos de la fila;
luego, Aldonza hace lo mismo. El juego continua hasta que se terminan todas las cajas y gana el
que tenga la mayor cantidad de galletas. ¿Quién de ellos tiene una estrategia no perdedora y cuál
es?
Nota: Una estrategia no perdedora es tal que le permita, no importando las condiciones iniciales
del juego, al menos empatar.
5. Totoro y Aldonza van a jugar otro juego: se tiene un tablero de 2013x2013, en cada turno
Totoro colorea de rojo un cuadrado de 2x2 dentro del tablero (de los que no están coloreados ya),
si es que puede hacerlo, y después Aldonza colorea de azul un cuadrito de 1x1 del tablero (de los
que no están coloreados ya). El juego continua hasta que se han coloreado todos los cuadritos y
gana el que haya coloreado la mayor cantidad de ellos. ¿Quién tiene una estrategia ganadora y
cuál es?
6. En un tablero de 9×9 se colocan 65 insectos cada uno en el centro de una casilla. Los insectos
empiezan a moverse al mismo tiempo y a la misma velocidad a una casilla que comparte lado con
la casilla en la que están. Al llegar a siguiente casilla dan un giro de 90 grados y siguen con su
camino (sin salirse del tablero). Demuestra que en algún momento hay dos insectos en la misma
casilla. (Nota: Los giros pueden ser a la derecha o a la izquierda)
7. ¿Es posible cubrir un tablero de 10x10 con piezas tetramino tipo
salgan del tablero? (Nota: es posible reflejarlas y girarlas).
sin que se encimen ni se
8. En un tablero de x un camino es una sucesión de casillas de manera que dos casillas
consecutivas tienen un lado en común. Muestra que si
, hay un camino que empieza y
termina en la misma casilla y pasas por todas las otras casillas exactamente una vez si y sólo si
alguno de o es un número par.
9. Un piso rectangular está cubierto por mosaicos de 1x4 y de 2x2. Uno de los mosaicos se rompió
y sólo hay disponible un mosaico del otro tipo. Muestra que no es posible reacomodar los
mosaicos para poder cubrir el piso nuevamente.
10. ¿Es posible cubrir un tablero de 10x10 con 21 tetraminos de tipo
pueden reflejar y girar los tetraminos).
y 4 de tipo ? (Nota: se
11. ¿Es posible formar un rectángulo usando un tetramino de cada uno de los 5 tipos exactamente
una vez?
12. Un cuadrado de 7x7 está cubierto por 16 fichas de 3x1 y una de 1x1. ¿En qué lugares puede
estar la ficha de 1x1?
PROBLEMAS DE INVARIANZA
1. Se colorean una fila de cuadritos de dos colores, de modo que el primero y el último tienen
distinto color. Muestra que la cantidad de parejas de cuadritos adyacentes que están coloreados
de distinto color es un número impar.
2. En una fiesta algunos niños y niñas se sientan en círculo. Cuando están todos sentados, cada
niño le da un regalo a las niñas que estén a su lado (si está entre dos niñas le da un regalo a cada
una, si está entre un niño y una niña le da un regalo sólo a la niña que está a su lado y si está entre
dos niños no da regalos). Muestra que la cantidad de regalos que se dieron en esa fiesta es un
número par.
3. En un pizarrón se escriben los números del 1 al 2013. Totoro escoge dos números, escribe la
diferencia positiva de ellos en el pizarrón y borra los números que escogió. Luego hace lo mismo
con los números que quedan en el pizarrón y continúa hasta que le queda un solo número, ¿es
posible que este número sea el 6?
4. Se tienen en un círculo los números 1,0,1,0,0,0 en ese orden. En cada paso se permite tomar
dos números consecutivos y sumarle 1 a ambos o restarle 1 a ambos. ¿Es posible, después de un
número finito de pasos, lograr que los seis números sean iguales?
5. Se tiene un tablero de ajedrez con la coloración usual.
a) En cada paso se puede elegir un renglón o una columna y cambiar el color de todos los
cuadritos en ese renglón o columna (blanco cambia a negro y negro cambia a blanco).
b) En cada paso se permite elegir un subtablero de 2x2 y cambiar el color de esos cuadritos.
c) En cada paso se permite elegir un renglón, una columna o un subtablero de 2x2 y cambiar el
color de los cuadrados elegidos.
Responde si en cada uno de los tres casos es posible, después de un número finito de pasos, tener
solamente un cuadrito negro.
6. Tachamos el primer dígito de
y se lo sumamos al número que queda. Este proceso se
repite hasta que queda un número muestra que el número que queda tiene dos dígitos iguales.
7. Tres números
se escriben en un pizarrón. En un movimiento se elige uno y se cambia por
la suma de los otros dos menos uno. Esta operación se repite varias veces hasta que se obtienen
los números 17, 1967, 1983. ¿Los números iniciales pudieron haber sido 3,3,3 ó 2,2,2?