Problemas - Combinatoria
Policías y ladrones --en un tablero
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:
Nueve puntos en el plano
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.
Cobertura imposible
Demostrar que es imposible cubrir un cuadrado de lado 1 con cinco cuadrados iguales de lado menor o igual que 1/2.
Naves marcianas en una cuadrícula
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:
Juego con un montón de piedras
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.
Polígono regular de n lados
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.
Nubes de circunferencias coloreadas
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.
Distancias entre pares de puntos en el plano
Hallar el máximo valor posible de $n$ para que existan puntos distintos $P_1, P_2, P_3,\ldots,P_n$ en el plano y números reales $r_1, r_2,\ldots, r_n$ de modo que la distancia entre cualesquiera dos puntos diferentes $P_i$ y $P_j$ sea $r_i + r_j$.
Paisanos en una mesa redonda
Alrededor de una mesa redonda están sentados representantes de $n$ países ($n\geq 2$), de tal manera que si dos representantes son del mismo país, entonces sus vecinos de la derecha no son del mismo país. Determinar, para cada $n$, el número máximo de personas que pueden sentarse alrededor de la mesa.
98 puntos en una circunferencia
En una circunferencia hay dados 98 puntos. María y José juegan alternadamente de la siguiente manera: cada uno traza un segmento que une dos puntos que no han sido unidos antes. El juego finaliza cuando los 98 puntos han sido usados como extremos de al menos un segmento. El ganador es quien traza el último segmento. Si José inicia el juego ¿quién puede asegurarse la victoria?