Problemas - Combinatoria
Saltos dragón en un tablero
En un tablero cuadriculado de tamaño $19\times 19$, una fiha llamada dragón da saltos de la siguiente manera: se desplaza 4 casillas en una dirección paralela a uno de los lados del tablero y 1 casilla en dirección perpendicular a la anterior.
Disputa por un territorio circular
Dos equipos, $A$ y $B$, disputan el territorio limitado por una circunferencia. $A$ tiene $n$ banderas azules y $B$ tiene $n$ banderas blancas ($n\geq 2$, fijo). Juegan alternadamente y $A$ comienza el juego.
Paseos de una ficha en un tablero
Los números $1,2,3,\ldots,n^2$ se colocan en las casillas de una cuadrícula de $n\times n$, en algún orden, un número por casilla. Una ficha se encuentra inicialmente en la casilla con el número $n^2$. En cada paso, la ficha puede avanzar a cualquiera de las casillas que comparten un lado con la casilla donde se encuentra. Primero, la ficha viaja a la casilla con el número 1, y para ello toma uno de los caminos más cortos (con menos pasos) entre la casilla con el número $n^2$ y la casilla con el número 1.
Coloreo roji-azul de 2n puntos alineados
Dado un entero positivo $n$, en un plano se consideran $2n$ puntos alineados $A_1, A_2,\ldots, A_{2n}$. Cada punto se colorea de azul o rojo mediante el siguiente procedimiento:
- En el plano dado se trazan $n$ circunferencias con diámetros de extremos $A_i$ y $A_j$ , disyuntas dos a dos.
- Cada $A_k, 1\leq k\leq 2n$, pertenece exactamente a una circunferencia.
- Se colorean los puntos de modo que los dos puntos de una misma
circunferencia lleven el mismo color.
Determine cuántas coloraciones distintas de los $2n$ puntos se pueden obtener al variar las $n$ circunferencias y la distribución de los dos colores.
Pulga saltona --en la recta numérica
Una pulga salta sobre puntos enteros de la recta numérica. En su primer movimiento
salta desde el punto 0 y cae en el punto 1. Luego, si en un movimiento la pulga saltó desde el punto $a$ y cayó en el punto $b$, en el siguiente movimiento salta desde el punto $b$ y cae en uno de los puntos $b + (b - a) - 1, b + (b - a), b + (b - a) + 1.$
Demuestre que si la pulga ha caído dos veces sobre el punto $n$, para $n$ entero
positivo, entonces ha debido hacer al menos $t$ movimientos, donde $t$ es el menor
entero mayor o igual que $2\sqrt{n}$.
Condiciones de coloreo de un tablero
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.
k-Subconjunto sin seis consecutivos
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.
Sucesiones de 2003 consecutivos
- (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é.
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.