Problemas - Combinatoria
Cambios de estado en cuadrícula 6X6 --con luciérnagas
En cada cuadrado de una cuadrícula de $6\times6$ hay una luciérnaga apagada o encendida. Una movida es escoger tres cuadrados consecutivos, ya sean los tres verticales o los tres horizontales, y cambiar de estado a las tres luciérnagas que se encuentran en dichos cuadrados. (Cambiar de estado a una luciérnaga significa que si está apagada se enciende y si está encendida se apaga.) Muestra que si inicialmente hay una luciérnaga encendida y las demás apagadas, entonces no es posible hacer una serie de movidas tales que al final todas las luciérnagas estén apagadas.
Caballos en el tablero
Considera un tablero de ajedrez. Los números del 1 al 64 se escriben en las casillas del tablero como en la figura:
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
P3 OMM 2006. Números 1..2n en cuadrícula 2Xn
Sea $ n $ un número entero mayor que 1. ¿De cuántas formas se pueden acomodar todos los números $1,2,\ldots,2n$ en las casillas de una cuadrícula de $2 \times n$, uno en cada casilla, de manera que cualesquiera dos números consecutivos se encuentren en casillas que comparten un lado de la cuadrícula?
P5 OMM 2005. Con cualquiera de las restantes se completa
Sea $N$ un entero mayor que 1. En cierta baraja de $N^3$ cartas, cada carta está pintada de uno de $N$ colores distintos, tiene dibujada una de $N$ posibles figuras y tiene escrito un número entero del 1 al $N$ (no hay dos cartas idénticas). Una colección de cartas de la baraja se llama completa si tiene cartas de todos los colores, o si entre sus cartas aparecen todas la figuras o todos los números. ¿Cuántas colecciones no completas tienen la propiedad de que, al añadir cualquier otra carta de la baraja, ya se vuelven completas?
P6 OMM 2004. Cambios de dirección en cuadrícula 2004X2004
¿Cuál es el mayor número posible de cambios de dirección en un recorrido sobre las líneas de una cuadrícula de $2004\times 2004$ casillas, si el recorrido no pasa dos veces por el mismo lugar?
P4 OMM 2004. Número de equipos en un torneo
Al final de un torneo de futbol en el que cada par de equipos jugaron entre si exactamente una vez y donde no hubo empates, se observó que para cualesquiera tres equipos $A, B, C,$ si $A$ le ganó a $B$ y $B$ le ganó a $C$ entonces $A$ le ganó a $C$. Cada equipo calculó la diferencia (positiva) entre el número de partidos que ganó y el número de partidos que perdió. La suma de todas estas diferencias resultó ser 5000. ¿Cuántos equipos participaron en el torneo? Encuentra todas las respuestas posibles.
P4 OMM 2002. Hileras de dominó --con suma impar
Una ficha de dominó tiene dos números (no necesariamente diferentes) entre 0 y 6. Las fichas se pueden voltear, es decir, $[4,5]$ es la misma ficha que $[5,4]$. Se quiere formar una hilera de fichas de dominó distintas, de manera que, en cada momento de la construcción de la hilera, la suma de todos los números de las fichas puestas hasta ese momento sea impar. Las fichas se pueden agregar de la manera usual a ambos extremos de la hilera, es decir, de manera que en cualesquiera dos fichas consecutivas aparezca el mismo número en los extremos que se juntan.
P1 OMM 2002. Operaciones sobre cuadrícula 32X32
En una cuadrícula de $32\times32$ se escriben los números del 1 al 1024 de izquierda a derecha: los números del 1 al 32 en el primer renglón, los del 33 al 64 en el segundo, etc. La cuadrícula se divide en cuatro cuadrículas de $16\times16$ que se cambian de lugar entre ellas como sigue:
Problema 5, IMO 2010
En cada una de las seis cajas $B_1,B_2,B_3,B_4,B_5,B_6$ hay inicialmente sólo una moneda. Se permiten dos tipos de operaciones:
- Tipo 1: Elegir una caja no vacía $B_j$ , con $1 \leq j \leq 5$. Retirar una moneda de $B_j$ y añadir dos monedas a $B_{j+1}$.
- Tipo 2: Elegir una caja no vacía $B_k$, con $1 \leq k \leq 4$. Retirar una moneda de $B_k$ e intercambiar los contenidos de las cajas (posiblemente vacías) $B_{k+1}$ y $B_{k+2}$.
Determine si existe una sucesión finita de estas operaciones que deja a las cajas $B_1,B_2,B_3,B_4,B_5$ vacías y a la caja $B_6$ con exactamente $2010^{2010^{2010}}$ monedas. (Observe que $a^{b^c} = a^{(b^c)}$.)
P2 OMM 2001. Un problema pelotudo
Se tienen algunas pelotas de colores (son por lo menos tres colores), y por lo menos tres cajas. Las pelotas se ponen en las cajas de manera que no quede vacía ninguna caja y que no haya tres pelotas de colores distintos que estén en tres cajas distintas. Prueba que hay una caja con todas las pelotas que están fuera de ella son del mismo color.