Problemas - Combinatoria

Problema

El juego de biribol

Enviado por jmd el 10 de Enero de 2012 - 15:11.

En un partido de biribol se enfrentan dos equipos de cuatro jugadores cada uno. Se organiza un torneo de biribol en el que participan $n$ personas, que forman equipos para cada partido (los equipos no son fijos). Al final del torneo se observó que cada dos personas disputaron exactamente un partido en equipos rivales. Determinar para qué valores de $n$ es posible organizar un torneo con tales características.

Problema

Saltos dragón en un tablero

Enviado por jmd el 10 de Enero de 2012 - 08:36.

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.


Problema

Disputa por un territorio circular

Enviado por jmd el 10 de Enero de 2012 - 08:29.

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.

Problema

Paseos de una ficha en un tablero

Enviado por jmd el 9 de Enero de 2012 - 22:04.

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.

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: