Problemas - Combinatoria

Problema

Problema 5, IMO 2010

Enviado por jesus el 18 de Julio de 2010 - 20:58.

En cada una de las seis cajas $B_1,B_2,B_3,B_4,B_5,B_6$ hay inicialmente sólo una moneda. Se permiten dos tipos de operaciones:

  • Tipo 1: Elegir una caja no vacía $B_j$ , con $1 \leq j \leq 5$. Retirar una moneda de $B_j$ y añadir dos monedas a $B_{j+1}$.
  • Tipo 2: Elegir una caja no vacía $B_k$, con $1 \leq k \leq 4$. Retirar una moneda de $B_k$ e intercambiar los contenidos de las cajas (posiblemente vacías) $B_{k+1}$ y $B_{k+2}$.

Determine si existe una sucesión finita de estas operaciones que deja a las cajas $B_1,B_2,B_3,B_4,B_5$ vacías y a la caja $B_6$ con exactamente $2010^{2010^{2010}}$ monedas. (Observe que $a^{b^c} = a^{(b^c)}$.)

Problema

P2 OMM 2001. Un problema pelotudo

Enviado por jmd el 13 de Julio de 2010 - 21:53.

Se tienen algunas pelotas de colores (son por lo menos tres colores), y por lo menos tres cajas. Las pelotas se ponen en las cajas de manera que no quede vacía ninguna caja y que no haya tres pelotas de colores distintos que estén en tres cajas distintas. Prueba que hay una caja con todas las pelotas que están fuera de ella son del mismo color.

Problema

P5 OMM 2000. Operación sobre rectángulos --en tablero nxn

Enviado por jmd el 13 de Julio de 2010 - 20:24.

Se tiene un tablero de $n\times n$, pintado como tablero de ajedrez. Está permitido efectuar la siguiente operación en el tablero:

  • Escoger un rectángulo en la cuadrícula de tal manera que las longitudes de sus lados sean ambas pares o ambas impares, pero que no sean las dos iguales a 1 al mismo tiempo, e
  • invertir los colores de los cuadritos de ese rectángulo.

Encuentra para qué valores de $ n $ es posible lograr que todos los cuadritos queden de un mismo color después de haber efectuado la operación el número de veces que sea necesario. (Nota: Las dimensiones de los rectángulos que se escogen pueden ir cambiando).

Problema

P6 OMM 1999. Cubrimiento con fichas de dominó

Enviado por jmd el 13 de Julio de 2010 - 19:23.

Se dice que un polígono es ortogonal si todos sus lados tienen longitudes enteras y cada dos lados consecutivos son perpendiculares. Demuestre que si un polígono ortogonal puede cubrirse con rectángulos de $2 \times1$ (sin que éstos se traslapen) entonces al menos uno de sus lados tiene longitud par.

Problema

P4 OMM 1999. Diez cuadros marcados en tablero de ajedrez

Enviado por jmd el 13 de Julio de 2010 - 19:17.

En una cuadrícula de $8\times8$ se han escogido arbitrariamente 10 cuadritos y se han marcado sus centros. El lado de cada cuadrito mide 1. Demuestre que existen al menos dos puntos marcados que están separados una distancia menor o igual que $\sqrt{2}$, o que existe al menos un punto marcado que se encuentra a una distancia $1/2$ de una orilla de la cuadrícula.
 

Problema

P1 OMM 1999. Estrategia ganadora con fichas rojinegras

Enviado por jmd el 13 de Julio de 2010 - 19:02.

Sobre una mesa se tienen 1999 fichas que son rojas de un lado y negras del otro (no se especifica cuántas con el lado rojo hacia arriba ni cuántas con el lado negro hacia arriba). Dos personas juegan alternadamente. Cada persona, en su turno, hace una de las siguientes cosas:

  • Retirar cualquier número de fichas, con la condición de que todas las fichas retiradas tengan el mismo color hacia arriba.
  • Voltear cualquier número de fichas, con la condición de que todas las
    fichas tengan el mismo color hacia arriba.

Gana el que toma la última ficha. ¿Cuál jugador puede asegurar que ganará, el primero en jugar o el segundo?

Problema

P3 OMM 1998. Octágono rojinegro

Enviado por jmd el 11 de Julio de 2010 - 11:20.

Cada uno de los lados y las diagonales de un octágono regular se pintan de rojo o de negro. Demuestre que hay al menos siete triángulos cuyos vértices son vértices del octágono y sus tres lados son del mismo color.

Problema

P4 OMM 1997. Planos determinados por seis puntos

Enviado por jmd el 11 de Julio de 2010 - 10:31.

Dados 3 puntos no alineados en el espacio, al único plano que los contiene le llamamos plano determinado por los puntos. ¿Cuál es el mínimo número de planos determinados por 6 puntos en el espacio si no hay 3 alineados y no están los 6 en un mismo plano?

Problema

P3 OMM 1997. Dieciseis vecinos en una cuadrícula

Enviado por jmd el 11 de Julio de 2010 - 10:29.

En una cuadrícula de 4 × 4 se van a colocar los números enteros del 1 al
16 (uno en cada casilla).

  • (a) Pruebe que es posible colocarlos de manera que los números que aparecen en cuadros que comparten un lado tengan una diferencia menor o igual a 4.
  • (b) Pruebe que no es posible colocarlos de tal manera que los números que aparecen en cuadros que comparten un lado tengan diferencia menor o igual a 3.
Problema

P5 OMM 1996. Recorre los cuadros y suma sus números

Enviado por jmd el 11 de Julio de 2010 - 09:36.

En una cuadrícula de $n \times n$ se escriben los números del 1 al $n^2$ en el orden habitual (de izquierda a derecha y de arriba a abajo). Como ejemplo se ilustra el caso $n = 3$: $$1 ~2 ~3$$ $$4 ~5 ~6$$ $$7 ~8 ~9$$

Llamemos camino en la cuadrícula a una sucesión de pasos de un cuadro a otro desde el cuadro 1 hasta el $n^2$, de tal manera que en cada paso el movimiento sea hacia la derecha o hacia abajo. Si $C$ es un camino, denotamos por $L(C)$ a la suma de los números por los que pasa el camino $C$.