Combinatoria
Moscas en un cubo (P1)
En cada uno de los vértices de un cubo hay una mosca. Al sonar el silbato cada una de las moscas vuela a alguno de los vértices del cubo situado en una misma cara del vértice de donde partió, pero diagonalmente opuesto a éste. Al sonar el silbato ¿de cuántas maneras pueden volar las moscas de modo que en ningún vértice queden dos o más moscas?
Coloraciones de puntos en una cuadrícula (Problema 3, OIM)
Sean $n \geq 2$ un número entero y $D_n$ el conjunto de puntos $(x,y)$ del plano cuyas coordenadas son números enteros con $-n \leq x \leq n $ y $-n \leq y \leq n$
Cuadrícula n por 4 (P4)
Sea $n$ un entero positivo. En una cuadrícula $ n\times 4 $, cada renglón es igual a
2 | 0 | 1 | 0 |
Un cambio es tomar tres casillas
- consecutivas en el mismo renglón y
- con dígitos distintos escritos en ellas
y cambiar los tres dígitos de estas casillas de la siguiente manera
0 → 1, 1 → 2, 2→0
Cambios de estado de focos en un tablero (P2)
En cada casilla de un tablero $ n\times n $hay un foco. Inicialmente todos los focos están apagados. En un paso, se permite cambiar el estado de todos los focos en una fila o de todos los focos en una columna (los focos prendidos se apagan y los focos apagados se prenden). Muestra que si después de cierta cantidad de pasos hay uno o más focos prendidos entonces en ese momento hay al menos n focos prendidos.
La amistad es una relación simétrica
En un grupo de personas, cada dos de ellas tiene exactamente un amigo en común en el grupo. Prueba que hay una persona que es amiga de todas las demás personas en el grupo. (Nota: la amistad es mutua, es decir, si X es amigo de Y, entonces Y es amigo de X.)
Combinatoria en el campamento
En un campamento de verano que va a durar n semanas se quiere dividir el tiempo en $3$ períodos de manera que cada período empiece en un lunes y termine un domingo. El primer período se dedicará a labores artísticas, el segundo será para deportes y en el tercero se hará un taller tecnológico. Durante cada período se escogerá un lunes para que un experto en el tema del período dé una plática. Sea $C(n)$ el número de formas en que puede hacerse el calendario de actividades.
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?