Problemas - Combinatoria

Problema

Coloreo roji-azul de 2n puntos alineados

Enviado por jmd el 9 de Enero de 2012 - 21:41.

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.

Problema

Pulga saltona --en la recta numérica

Enviado por jmd el 9 de Enero de 2012 - 21:32.

 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}$.

Problema

Condiciones de coloreo de un tablero

Enviado por jmd el 6 de Enero de 2012 - 20:12.

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.

Problema

k-Subconjunto sin seis consecutivos

Enviado por jmd el 6 de Enero de 2012 - 19:55.

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.

 

Problema

Sucesiones de 2003 consecutivos

Enviado por jmd el 6 de Enero de 2012 - 19:44.
  • (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é.

Problema

Policías y ladrones --en un tablero

Enviado por jmd el 6 de Enero de 2012 - 18:39.

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:

Problema

Nueve puntos en el plano

Enviado por jmd el 6 de Enero de 2012 - 18:24.

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.

Problema

Cobertura imposible

Enviado por jmd el 5 de Enero de 2012 - 16:43.

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

 

Problema

Naves marcianas en una cuadrícula

Enviado por jmd el 5 de Enero de 2012 - 16:40.

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:

Problema

Juego con un montón de piedras

Enviado por jmd el 5 de Enero de 2012 - 15:32.

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.