Combinatoria

Se deben colorear casillas de un tablero de $1001\times 1001$ de acuerdo a las reglas siguientes:

• Si dos casillas tienen un lado común, entonces al menos una de ellas se debe colorear.
• De cada seis casillas consecutivas de una fila o de una columna, siempre se deben colorear al menos dos de ellas que sean adyacentes.

Determinar el número mínimo de casillas que se deben colorear.

Sea $M =\{1,2,\ldots,49\}$ el conjunto de los primeros 49 enteros positivos. Determine el máximo entero $k$ tal que el conjunto $M$ tiene un subconjunto de $k$ elementos en el que no hay 6 números consecutivos. Para ese valor máximo de $k$, halle la cantidad de subconjuntos de $M$, de $k$ elementos, que tienen la propiedad mencionada.

• (a) Se tienen dos sucesiones de números, con 2003 enteros consecutivos y una tabla de dos renglones y 2003 columnas. Decida si siempre es posible distribuir los números de la primera sucesión en el primer renglón y la segunda sucesión en el segundo renglón, de tal manera que la sucesión obtenida de las 2003 sumas por columna forman una nueva sucesión de 2003 enteros consecutivos.
• (b) Misma pregunta si hubiera 2004 columnas.

En ambos casos, si la respuesta es afirmativa, explique cómo se distribuirían los números, y si es negativa explicar por qué.

Un policía intenta capturar a un ladrón en un tablero de $2001\times 2001$. Ellos juegan alternadamente y cada jugador, en su turno, debe moverse una casilla en uno de los tres siguientes sentidos:

($\downarrow$, abajo); ($\rightarrow$, derecha); ($\nwarrow$, diagonal arriba a la izquierda).

Si el policía se encuentra en la casilla de la esquina inferior derecha, puede usar su jugada para pasar directamente a la casilla de la esquina superior izquierda (el ladrón no puede hacer esta jugada). Inicialmente el policía está en la casilla central y el ladrón está en la casilla vecina diagonal superior derecha al policía. El policía comienza el juego. Demuestre que:

Dado cualquier conjunto de 9 puntos en el plano de los cuales no hay tres colineales, demuestre que para cada punto $P$ del conjunto, el número de triángulos que tienen como vértices a tres de los ocho puntos restantes y a $P$ en su interior, es par.

Demostrar que es imposible cubrir un cuadrado de lado 1 con cinco cuadrados iguales de lado menor o igual que 1/2.

En un tablero de $2000 \times 2001$ cuadros de coordenadas enteras $(x,y)$, $0\leq x \leq 1999$ y $0 \leq y\leq 2000$, una nave se mueve de la siguiente manera:

Hay un montón de 2000 piedras. Dos jugadores juegan alternadamente, de acuerdo a las siguientes reglas:

• (a) En cada jugada se pueden retirar 1, 2, 3, 4 ó 5 piedras del montón.
• (b) En cada jugada esá prohíbido que el jugador retire la misma cantidad de piedras que retiró su oponente en la jugada previa.
• (c) Pierde el jugador que en su turno no pueda realizar una jugada válida.

Determinar cuál jugador tiene estrategia ganadora y encontrarla.

Se construye un polígono regular de $n$ lados ($n\geq 3$) y se enumeran sus vértices del 1 al $n$. Se trazan todas las diagonales del polígono. Demostrar que si $n$ es impar, se puede asignar a cada lado y a cada diagonal un número entero del 1 al $n$, tal que se cumplan simultáneamente las siguientes dos condiciones:

• (a) El número asignado a cada lado o diagonal es distinto a los asignados a los vértices que une.
• (b) Para cada vértice, todos los lados y diagonales que compartan dicho vértice
  tienen números diferentes.

Sean $n$ puntos distintos, $P_1, P_2,\ldots, P_n$, sobre una recta del plano ($n \geq 2$). Considere todas las circunferencias de diámetro $P_iP_j$ ($1\leq i \leq j\leq n$) y coloreadas cada una con uno de $k$ colores dados. Llamamos $(n-k)$-nube a esta configuración.

Para cada entero positivo $k$, determine todos los $n$ para los cuales se verifica que toda $(n-k)$-nube contiene dos circunferencias tangentes exteriormente del mismo color.
Nota: Para evitar ambigüedades, los puntos que pertenecen a más de una circunferencia no llevan color.