viernes, 11 de marzo de 2016

Maratón Combinatoria 1

Problema 0. Un subconjunto $S$ de $1,2,\ldots,n$ se llama balanceado si para cada $a$ en $S$ hay un $b$ en $S$ distinto de $a$ tal que $\frac{a+b}{2}$ también está en $S$.

a) Sea $k>1$ un entero y $n=2k$. Muestra que cada subconjunto $S$ de $1,2,\ldots,n$ con más de $\frac{3n}{4}$ elementos es balanceado.

b) ¿Existe un $n=2k$ con $k>1$ un entero para el cual cada subconjunto $S$ de $1,2,\ldots,n$ con más de $\frac{2n}{3}$ elementos es balanceado?

21 comentarios:

Unknown dijo...

Solucion:
Incso a) https://www.dropbox.com/s/su2ugx4v8o07spo/Photo%2022-03-16%2012%2018%2040.jpg?dl=0
No se si el b lo entendi bien, pero con n=6, veo que 2(6)/3=4, y por el inciso a cualquier subconjunto de 5 o 6 si es balanceado, entonces si existe esa n.

Problema 1:Se tienen N monedas, de las cuales N − 1 son auténticas de igual peso y una es falsa, de peso diferente de las demás. El objetivo es, utilizando exclusivamente una balanza de dos platos, hallar la moneda falsa y determinar si es más pesada o más liviana que las auténticas. Cada vez que se pueda deducir que una o varias monedas son auténticas, entonces todas estas monedas se separan inmediatamente y no se pueden usar en las siguientes pesadas. Determine todos los N para los que se puede lograr con certeza el objetivo. (Se pueden hacer tantas pesadas como se desee.)

Unknown dijo...

Solución: https://www.dropbox.com/s/6dxtoryewuq3b2i/Sol%20C1.png?dl=0

Problema 2: Sea $A=(a_{1},a_{2},...,a_{2001})$ una secuencia de enteros positivos. Sea $M$ el número de ternas $(a_{i}, a_{j}, a_{k})$ con $1\leq i < j <k \leq 2001$ tal que $a_{j}=a_{i}+1$ y $a_{k}=a_{j}+1$. Considerando todas las posibles secuencias $A$, encuentra el mayor valor posible de $M$.

Ariel dijo...

Solución 2:
https://www.dropbox.com/s/lwxykluhdz2r47c/SolC2.pdf?dl=0

Problema 3:
Sea $a_1, a_2, \dots, a_n$ una secuencia de números reales y $m$ un entero positivo fijo menor que $n$. Decimos que un índice $k$ con $1 \leq k \leq n$ es bueno si existe un $\ell$ con $1 \leq \ell \leq m$ tal que $a_k + a_{k + 1} + \dots + a_{k + \ell - 1} \geq 0$, donde los índices se toman módulo $n$.

Sea $T$ el conjunto de todos los índices buenos. Muestra que $\sum_{k \in T} a_k \geq 0$.

Unknown dijo...

Solución 3: https://www.dropbox.com/s/vs6rdld0w2hsjgr/image.jpeg?dl=0

Problema 4:
Un conjunto de tres enteros no negativos $\{x,y,z\}$ con $x<y<z$ es elegante si $\{z-y,y-x\}$=$\{1776,2001\}$. Muestra que el conjunto de todos los enteros no negativos puede ser escrito como la unión de conjuntos elegantes disjuntos.

Alef dijo...

Solución 4: https://www.dropbox.com/s/db1hb4yh228tqw3/SolC4.pdf?dl=0

Problema 4: Dado un $n \ge 2$ entero positivo sea $S = \{1,2,3, \dots, 6n \}$ un conjunto. Encuentra el mayor $k$ tal que cada subconjunto $A$ de $S$ con $4n$ elementos tiene al menos $k$ parejas $(a,b)$ con $a<b$ tal que $a$ divide a $b$.

Unknown dijo...

Solución 5: https://www.dropbox.com/s/n7e8q80rwpc7vx3/Sol-C5.pdf?dl=0

Problema 6: Cada una de nueve líneas rectas divide a un cuadrado en dos cuadriláteros con razón entre sus áreas igual a $r$ con $r>0$ (La razón es igual para cada recta que lo divide). Prueba que al menos tres de esas rectas concurren.

Ariel dijo...

Solución 6: https://drive.google.com/file/d/0B-Pv6Th_qH4nYmhjOEpuZmVFWWc/view?usp=sharing

Problema 7: En cierto planeta, hay $2^N$ países ($N \geq 4$). Cada país tiene una bandera de ancho $N$ y altura 1 compuesta por $N$ campos de tamaño $1 \times 1$, cada campo de color amarillo o azul. No hay dos países con la misma bandera.

Decimos que un conjunto de $N$ banderas es diverso si dichas banderas se pueden acomodar en un cuadrado de $N \times N$ de tal manera que los $N$ campos de alguna de sus diagonales principales tienen el mismo color. Determina el mínimo entero positivo $M$ tal que entre cualesquiera $M$ banderas distintas, existen $N$ que forman un conjunto diverso.

Unknown dijo...

Solución 7: https://www.dropbox.com/s/a997y02ux7dte7r/image.jpeg?dl=0

Problema 8: Encuentra todos los posibles valores de $n$ tales que existe un conjunto $S$ de $n$ puntos en el plano, no hay tres colineales, y se cumple que uno puede colorear los puntos de manera que si tres puntos son del mismo color o si tienen tres colores diferentes, entonces no forman un ángulo obtuso. El número de colores que se pueden utilizar es ilimitado.

Ariel dijo...

Solución 8:
https://drive.google.com/file/d/0B-Pv6Th_qH4nME1feWhtdjBlcFk/view?usp=sharing

Problema 9:
Para un polígono convexo $P$ un recorte de $P$ consiste en elegir tres vértices consecutivos $A, B, C$ y cambiar los segmentos $AB$ y $BC$ por los segmentos $AM$, $MN$ y $NC$, donde $M$ y $N$ son los puntos medios de $AB$ y $BC$ respectivamente.

Sea $\mathcal{P}_6$ un hexágono regular de área 1. Para cada $n \geq 6$ se obtiene el polígono $\mathcal{P}_{n + 1}$ aplicandole un recorte al polígono $\mathcal{P}_n$.

Muestra que sin importar los recortes que se hagan, el área de $\mathcal{P}_n$ es mayor que $\frac{1}{3}$ para todo $n \geq 6$.

Unknown dijo...

Solución 9: https://www.dropbox.com/s/a997y02ux7dte7r/image.jpeg?dl=0

Problema 10: En la secuencia $1,0,1,0,1,0,3,5, \cdots$ cada término a partir del séptimo es igual al último dígito de la suma de los seis anteriores. Prueba que no hay seis términos consecutivos que sean $0,1,0,1,0,1$.

Ariel dijo...

Solución 10:
https://drive.google.com/file/d/0B-Pv6Th_qH4nOWlnSXdXbG42RmM/view?usp=sharing

Problema 11:
Sea $n \geq 4$ un entero positivo. Dado un conjunto $S = \{P_1, P_2, \dots, P_n\}$ de puntos en el plano tales que no hay tres colineales y no hay cuatro concíclicos, sea $a_t$, $1 \leq t \leq n$, el número de circunferencias $(P_iP_jP_k)$ que contienen a $P_t$ en su interior, y sea
$$m(S) = \sum_{i = 1}^n a_i$$
Muestra que existe un entero positivo $f(n)$, que depende únicamente de $n$, tal que los puntos de $S$ son los vértices de un polígono convexo si y solo si $m(S) = f(n)$.

Unknown dijo...

Solución 11: https://www.dropbox.com/s/a997y02ux7dte7r/image.jpeg?dl=0

Problema 12: Se tienen $n$ puntos en el plano tales que no hay tres colineales. Prueba que el número de triángulos, cuyos vértices son tomados de los $n$ dados, y que tienen área $1$, es menor o igual a $\frac{2}{3}(n^{2}-n)$

Ariel dijo...

Solución 12:
https://drive.google.com/file/d/0B-Pv6Th_qH4neG1lM3BKNkxDUkU/view?usp=sharing

Problema 13:
Sea $n \geq 1$ un entero. Determina el máximo número de parejas disjuntas de elementos del conjunto $\{1, 2, \dots, n\}$ tales que las sumas de las parejas distintas son enteros distintos menores o iguales que $n$.

Unknown dijo...

Solución 13: https://www.dropbox.com/s/1jjjvbafv8hlqj9/Sol%20C13.pdf?dl=0

Algunas de mis soluciones pasadas ya no están en el mismo link, ahora están en este: https://www.dropbox.com/sh/0db5mi64q247e09/AABiK3_4A_sN65plxgEliOBka?dl=0

Problema 14: En una escuela hay $2007$ niñas y $2007$ niños. Cada estudiante pertenece a no más de $100$ talleres en la escuela. Se sabe que cualesquiera dos estudiantes de género opuesto tienen al menos un taller en común. Prueba que existe un taller con al menos $11$ niñas y $11$ niños.

Ariel dijo...

Solución 14:
https://drive.google.com/file/d/0B-Pv6Th_qH4nNXp5MXluZm9OajQ/view?usp=sharing

Problema 15:
Para un polígono convexo $\mathcal{P}$ un recorte de $P$ consiste en elegir tres vértices consecutivos $A, B, C$ y dos puntos $M, N$ en el interior de los segmentos $AB$ y $AC$ respectivamente, y reemplazar los segmentos $AB$ y $AC$ por los segmentos $AM, MN$ y $NC$.

Sea $\mathcal{P}_6$ un hexágono regular de área 1. Para cada $n \geq 6$ se obtiene el polígono $\mathcal{P}_{n + 1}$ aplicandole alguno de los posibles recortes al polígono $\mathcal{P}_n$.

Determina la máxima constante real $c$ tal que para todo entero positivo $n \geq 6$ se cumple que el área de $\mathcal{P}_n$ es mayor o igual que $c$, independientemente de los recortes que se hagan.

Ariel dijo...

Correción:
"...interior de los segmentos $AB$ y $BC$..."
"...reemplazar los segmentos $AB$ y $BC$..."

Unknown dijo...

Solución 15: https://www.dropbox.com/s/k7iszus6udeci47/Sol%20C15.pdf?dl=0

Problema 16: Una o más potencias de $2$ (pueden repetirse) se escriben en cada una de $n$ hojas de papel. La suma de los números de cada hoja es la misma. Cada número aparece a lo más $5$ veces entre todas las $n$ hojas. Encuentra el mayor valor posible de $n$.

Unknown dijo...

Hints para el problema 16: https://www.dropbox.com/s/tvtyiu8yehxd8sb/Hint%20C16.pdf?dl=0

Unknown dijo...

Solución 16: https://www.dropbox.com/s/cpaslfe81mcvd9o/Sol%20C16.png?dl=0

Problema 17: Los números $1$ y $-1$ se escriben en las casillas de un tablero de $2000\times 2000$. Si la suma de todos los números escritos en las casillas del tablero es positiva, prueba que se pueden elegir $1000$ filas y $1000$ columnas de manera que la suma de los números en las casillas en las que se intersectan estas filas y columnas es al menos $1000$.

José Ramón Tuirán dijo...

Solución 17: https://drive.google.com/open?id=0BzJCrR_cmk8KOU5pSGtROThTbnc

Problema 18: Un librero tiene $n$ volúmenes numerados del $1$ al $n$, en algún orden. Una persona selecciona un volúmen que está muy a la derecha, digamos el volumen $k$, y lo coloca en la posición $k$. Por ejemplo si están los libros en el orden $1, 3, 2, 4$, puede agarrar al $2$ y colocar entre el $1$ y el $3$. Llegando al orden correcto $1, 2, 3, 4$. Pruebe que:
a) Si este proceso es repetido, sin importar como haga los movimientos la persona siempre se llega al orden correcto.
b) ¿Cuántos pasos a lo más debe realizar la persona para llegar al orden correcto?

José Ramón Tuirán dijo...

El inciso b) puede que este algo mal formulado, para evitar confusiones puede ser equivalente al siguiente enunciado: ¿Cuál es el mayor número de movimientos que el proceso puede tomar?

Publicar un comentario