Problemas - Combinatoria

Problema

Coloración en números del 1 al 4027

Enviado por vmp el 10 de Noviembre de 2014 - 17:58.

Cada uno de los números del 1 al 4027 se ha coloreado de verde o de rojo. Cambiar el color de un número es pasarlo a verde si era rojo, y pasarlo a rojo si era verde.
Diremos que dos enteros positivos $m$ y $n$ son cuates si alguno de los números $\frac{m}{n}$ o $\frac{n}{m}$ es un número primo. Un paso consiste en elegir dos números que sean cuates y cambiar el color de cada uno de los números.
Muestra que después de realizar algunos pasos es posible hacer que todos los números del 1 al 2014 sean verdes.

Problema

Focos distribuidos en una circunferencia (P1)

Enviado por jesus el 26 de Septiembre de 2014 - 11:20.

Se tienen 25 focos distribuidos de la siguiente manera: los primeros 24 se disponen en una circunferencia colocando un foco en cada uno de los vértices de un 24-ágono regular, y el foco restante se coloca en el centro de dicha circunferencia. Se permite aplicar cualquiera de las siguientes dos operaciones:

Problema

Relaciones combinatorias

Enviado por jmd el 3 de Septiembre de 2014 - 19:53.

Sean $r,n$ enteros no negativos tales que $r\leq{n}$.

a) Demostrar que $$\frac{n+1-2r}{n+1-r}C(n,r)$$ es un entero.

b) Demostrar que

$$ \sum_{r=0}^{\lfloor n/2\rfloor}\frac{n+1-2r}{n+1-r}C(n.r)<2^{n-2}$$ para todo $n\geq 9$.
(Nota: $\lfloor x\rfloor$ es el mayor entero menor o igual que x, y $C(n,r)$ es el número de subconjuntos de tamaño r tomados de un conjunto de tamaño n.) 

Problema

Viaje redondo

Enviado por jmd el 3 de Septiembre de 2014 - 15:20.

Air Michael y Air Patrick operan vuelos directos que conectan Belfast, Cork, Dublin, Galway, Limerick y Waterford. Para cada par de ciudades exactamente una de las aerolíneas opera la ruta (en ambos sentidos) conectando las ciudades.Demostrar que hay cuatro ciudades para las cuales una de las aerolíneas opera un viaje redondo. (Un viaje redondo para las ciudades P,Q,R,S es un viaje que va de P a Q, de Q a R, de R a S y de S a P.)

Problema

P6. IMO 2014 - Coloreado de rectas en posición general

Enviado por jesus el 9 de Julio de 2014 - 11:30.

Un conjunto de rectas en el plano está en posición general si no hay dos que sean paralelas ni tres que pasen por el mismo punto. Un conjunto de rectas en posición general separa el plano en regiones, algunas de las cuales tienen área finita; a estas las llamamos sus regiones finitas.

Demostrar que para cada $n$ suficientemente grande, en cualquier conjunto de $n$ rectas en posición general es posible colorear de azul al menos $\sqrt{n}$ de ellas de tal manera que ninguna de sus regiones finitas tenga todos los lados de su frontera azules.

Problema

P5. IMO 2014 - Monedas fraccionarias

Enviado por jesus el 9 de Julio de 2014 - 11:28.

Para cada entero positivo $n$, el Banco de Ciudad del Cabo produce monedas de valor $\frac{1}{n}$. Dada una colección finita de tales monedas (no necesariamente de distintos valores) cuyo valor total no supera $99 + \frac{1}{2}$, demostrar que es posible separar esta colección en 100 o menos montones, de modo que el valor total de cada montón sea como máximo 1.

Problema

P2. IMO 2014 - Configuraciones pacíficas en un tablero

Enviado por jesus el 9 de Julio de 2014 - 11:13.

Sea $n \geq 2$ un entero. Consideremos un tablero de tamaño $n \times n$ formado por $n^2$ cuadrados unitarios. Una configuración de $n$ fichas en este tablero se dice que es pacífica si en cada fila y en cada columna hay exactamente una ficha. Halle el mayor entero positivo $k$ tal que, para cada configuración pacífica de $n$ fichas, existe un cuadrado de tamaño $k \times k$ sin fichas en sus $k^2$ cuadrados unitarios.

Problema

¿Cuál fórmula? ¡Genera la lista!

Enviado por jmd el 1 de Junio de 2014 - 07:55.

1.C. ¿Cuántos números del 10 al 99 son tales que sus dígitos están en orden decreciente? Nota: 31 cumple pero no el 44 ni el 56.

Problema

Huevos y chilaquiles en buffet

Enviado por jmd el 25 de Mayo de 2014 - 11:09.

2.1. Cierto día en el restaurante La Cascada prepararon para el buffet de desayuno una charola de cada uno de los siguientes siete platillos: huevos con tocino, frijoles con queso, huevos con jamón, huevos a la mexicana, chilaquiles rojos, chilaquiles con huevo y chilaquiles verdes. Se le ordena al mesero acomodar las charolas de los platillos, alineadas en la barra, de forma tal que las que contengan huevo queden juntas y que las que contengan chilaquiles queden juntas.

Problema

Ordenar los superhéroes

Enviado por jmd el 24 de Mayo de 2014 - 21:38.

1.5.  Heberto tiene en su colección de figuras de acción de superhéroes dos Hulk, dos Superman,dos Ironman, dos Batman que quiere acomodar en línea sobre una repisa. Quiere que entre cada dos superhéroes iguales haya una cantidad diferente de figuras. Por ejemplo, si hay tres figuras entre los dos Hulk, no podría haber tres figuras entre los dos Batman. De cuántas maneras diferentes puede hacer esto?