Problemas - Combinatoria
P7. OMM 1988. Subconjuntos ajenos de {1,2,...,m}
Si $A$ y $B$ son subconjuntos ajenos del conjunto $\{1,2,\ldots,m\}$ y la suma de los elementos de $A$ es igual a la suma de los elementos de $B$, pruebe que el número de elementos de $A$ y también de $B$ es menor que $m/\sqrt{2}$
P4. OMM 1988. Ocho enteros entre uno y ocho
¿Cuántas maneras hay de escoger ocho enteros $a_1,a_2,a_3,\ldots,a_8$ no necesariamente distintos, tales que $1\leq{a_1}\leq\ldots\leq{a_8}\leq8$?
Embaldosado de un patio
Se desea embaldosar un patio cuadrado de lado $N$ entero positivo. Se dispone de dos tipos de baldosas: cuadradas de $5\times5$, y rectangulares de $1\times3$. Determine los valores de $N$ para los cuales es posible hacerlo. Nota: el patio debe quedar completamente cubierto sin que las baldosas se sobrepongan.
Mover una ficha en un tablero
Un jugador coloca una ficha en una casilla de un tablero $m\timesn$ dividido en cuadrados de tamaño $1\times1$. El jugador mueve la ficha de acuerdo a las siguientes reglas:
- En cada movida, el jugador mueve la ficha a un cuadrado que comparte un lado con el cuadrado en que se encuentra.
- El jugador no puede mover la ficha a un cuadrado que ha ocupado previamente.
- Dos movimientos consecutivos no pueden tener la misma dirección.
El juego termina cuando el jugador no puede mover la ficha. Determine todos los valores de $m$ y $ n $ tales que, al colocar la ficha en algún cuadrado, todos los cuadrados pueden ser ocupados durante el juego.
No podrían saludar sólo a uno
Cada uno de los 61 competidores en el concurso estatal saludó de mano al menos a otro competidor. Demostrar que alguno de ellos saludó de mano al menos a dos competidores.
Problema 2
Sea S el conjunto de puntos (i,j) de coordenadas enteras en el plano, con i,j=0,1,2,...,9.
Coloración de vertices
Demuestra que una gráfica $G$ es bipartita si y sólo si su número cromático $\chi(G)$ es 2.
Cuadrados en el primer cuadrante
Sea $S$ el conjunto de puntos $(i,j)$ de coordenadas enteras en el plano, con $i,j=0,1,2,\ldots,n$.
- a) ¿De cuántas formas se pueden elegir cuatro puntos de $S$ de manera que formen un cuadrado con lados paralelos a los ejes de coordenadas?
- b) ¿De cuántas formas se pueden elegir cuatro puntos en $S$ de manera que formen un cuadrado?
Problema 5
Cuantos números de 3 cifras, que la suma de sus cifras sea par se pueden formar con los digitos 1,2,3...9
Famosas decadentes adictas al bisturí
En una muestra de 50 famosas, 35 han recurrido a la mamoplastia, 20 a la rinoplastia y 15 a la liposucción. Se logró averiguar también que 15 se habían practicado mamo y rinoplastia, 12 rinoplastia y liposucción, y 10 liposucción y mamoplastia. Se supo adicionalmente que 8 se habían sometido a las tres intervenciones estéticas.
