Nacional 2009 N2 P3

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
amcandio

Colaborador
Mensajes: 311
Registrado: Sab 16 Oct, 2010 12:50 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Posadas, Misiones
Contactar:

Nacional 2009 N2 P3

Mensaje sin leer por amcandio » Mié 02 Feb, 2011 7:41 pm

Sobre una mesa hay [math] cajas; Fredy distribuye en las cajas, a su elección, bolitas blancas y bolitas negras, tantas como quiera de cada color. A continuación, Miguel, que ve cuantas bolitas de cada clase hay en cada caja, elige [math] de las cajas. Si las cajas que eligió Miguel contienen por lo menos [math] del total de bolitas blancas y por lo menos [math] del total de bolitas negras, gana Miguel. En caso contrario, gana Fredy. Determinar si Fredy puede elegir las bolitas y distribuirlas para impedir que gane Miguel.
"Prillo es el Lanata de la trigonometria"

Avatar de Usuario
Ivan

Colaborador
Mensajes: 980
Registrado: Vie 15 Oct, 2010 7:18 pm
Medallas: 1
Nivel: Exolímpico

Re: Nacional 2009 N2 P3

Mensaje sin leer por Ivan » Mar 05 Feb, 2013 8:06 pm

Este es un problema muy difícil, aunque las ideas de la solución son totalmente elementales. La solución que escribo a continuación me la contaron hace mucho.
Spoiler: mostrar
Primero explico la idea intuitiva de la solución. Se puede ver que Miguel gana siempre. La idea es elegir las [math] cajas que tienen más bolitas blancas y separar las [math] las cajas restantes en [math] grupos de [math] cajas cada uno, de modo que la cantidad de bolitas blancas en cada grupo sea aproximadamente la misma. Ahora elegimos los dos grupos que más bolitas negras tienen. Es inmediato que las [math] cajas que elegimos tienen al menos [math] del total de bolitas negras. Además como cada grupo tenía aproximadamente la misma cantidad de bolitas blancas, tenemos aproximadamente [math] del total de bolitas blancas. Las [math] cajas que elegimos al principio dan un margen que permite que ese "aproximadamente" se convierta en un "al menos".
Lo que hago a continuación es formalizar estas ideas.



Veamos que Miguel puede ganar siempre.

Primero numeramos las cajas, de [math] a [math], de modo que si [math], la caja [math] contenga a lo sumo tantas bolitas blancas como la caja [math].
Llamemos [math] y [math] a la cantidad de bolitas de la caja [math], blancas y negras respectivamente.

Entonces tenemos
[math]


Separemos las cajas numeradas del [math] al [math] en [math] grupos según el resto del número de la caja en la división por [math]. Cada grupo tiene [math] cajas.

Llamemos [math] a la cantidad de bolitas blancas en el grupo [math]. Tenemos
[math]
Llamemos [math] a la cantidad de bolitas negras en el grupo [math].

Queremos probar que al elegir las cajas de los dos grupos que más bolitas negras tengan y las [math] cajas que no están en ningún grupo (o sea las cajas [math] ) Miguel gana siempre. Es fácil ver que esas [math] cajas tienen por lo menos [math] de las bolitas negras.
Vamos a ver que también tienen [math] de las bolitas blancas.


Lo interesante de la división que hicimos es que [math].

Notemos que si [math] son dos grupos cualesquiera, tenemos [math].

Ahora sumando con [math] entre [math] y [math] tenemos [math] y entonces
[math]
Ahora supongamos que los dos grupos que más bolitas negras tienen son los grupos [math] y [math]. Ahora
[math]
La última desigualdad es cierta porque [math]. Con esto estamos.
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)

Avatar de Usuario
Johanna

OFO - Medalla de Plata
Mensajes: 57
Registrado: Lun 22 Oct, 2012 9:38 pm
Medallas: 2
Nivel: Exolímpico

Re: Nacional 2009 N2 P3

Mensaje sin leer por Johanna » Sab 21 Sep, 2013 11:59 pm

A mi se me ocurrio asi:
Spoiler: mostrar
La idea seria ver que Miguel siempre va a ganar, para que Miguel no pueda ganar se deberia lograr que haya [math] de las blancas en 15 cajas y [math] de las negras en 14 cajas. Tomo como ejemplo que hay 700 bolitas blancas, para que haya 200 en 15 cajas tiene que haber 14 bolitas en 15 cajas y el resto las reparto entre las demas, poniendo en 15 cajas 1 bolita en cada una y las demas las divido en las cajas sobrantes. Ponemos en las 15 cajas con 14 bolitas blancas 1 negra en cada una y en las que tienen 1 bolita blanca se colocan 14 negras en cada una. Ahora cuando Miguel tenga que elegir al elegir las 15 cajas para elegir los [math] blancos ya elige 15 negras, entonces puede elegir 13 cajas con 14 bolitas negras y cumple el cometido.
Lo que no me queda claro del enunciado es si se puede dejar cajas con 0 bolitas de algun color en ese caso creo que se puede hacer dejando 15 cajas sin bolitas blancas y 15 sin bolitas negras asi es necesario que elija 30 cajas.

Avatar de Usuario
Ivan

Colaborador
Mensajes: 980
Registrado: Vie 15 Oct, 2010 7:18 pm
Medallas: 1
Nivel: Exolímpico

Re: Nacional 2009 N2 P3

Mensaje sin leer por Ivan » Dom 22 Sep, 2013 1:09 am

Johanna escribió:A mi se me ocurrio asi:
Spoiler: mostrar
La idea seria ver que Miguel siempre va a ganar, para que Miguel no pueda ganar se deberia lograr que haya [math] de las blancas en 15 cajas y [math] de las negras en 14 cajas. Tomo como ejemplo que hay 700 bolitas blancas, para que haya 200 en 15 cajas tiene que haber 14 bolitas en 15 cajas y el resto las reparto entre las demas, poniendo en 15 cajas 1 bolita en cada una y las demas las divido en las cajas sobrantes. Ponemos en las 15 cajas con 14 bolitas blancas 1 negra en cada una y en las que tienen 1 bolita blanca se colocan 14 negras en cada una. Ahora cuando Miguel tenga que elegir al elegir las 15 cajas para elegir los [math] blancos ya elige 15 negras, entonces puede elegir 13 cajas con 14 bolitas negras y cumple el cometido.
Lo que no me queda claro del enunciado es si se puede dejar cajas con 0 bolitas de algun color en ese caso creo que se puede hacer dejando 15 cajas sin bolitas blancas y 15 sin bolitas negras asi es necesario que elija 30 cajas.
Creo que ahí estás dando un ejemplo de una distribución de las bolitas en las cajas que le permite a Miguel ganar. Para asegurar que Miguel gana siempre hay que hacer un argumento que funcione para cualquier distribución de las bolitas, no alcanza con probarlo para una en particular.
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)

juandodyk
Mensajes: 14
Registrado: Mar 26 Jun, 2018 1:59 am
Nivel: Exolímpico

Re: Nacional 2009 N2 P3

Mensaje sin leer por juandodyk » Lun 06 Ago, 2018 2:47 am

Estoy bastante seguro de que me salió. Mi solución es mucho más chota que la solución oficial (la que cuenta @Ivan), pero intuitivamente creo que es bastante simple. Eso sí, formalizarla fue muy engorroso; agradezco que alguien se anime a leerla y me diga si le parece que está bien. Lo bueno es que con mi método puedo mejorar la cota de $\frac27$ a $\frac{15}{51}$ (de 0,286 a 0,294; mucho más no se puede mejorar porque si los números son todos iguales eso da $\frac{28}{88}\cong 0.318$).
Spoiler: mostrar
La solución es muy pesada, así que la voy comentando. Arranco con notación: sean $(a_1, b_1), \ldots, (a_{88}, b_{88})$ las cajas, donde $a_i$ es la cantidad de bolitas blancas de la caja $i$ y $b_i$ la cantidad de bolitas negras; tenemos $a_i,b_i\geqq0$. Llamo $[n]$ al conjunto $\{1, \ldots, n\}$. Lo que pide el problema es demostrar que existe $I \subset [88]$ tal que $|I|=28$ y tal que $\sum_{i\in I} a_i \geqq \frac27 \sum_{i=1}^{88} a_i$ y $\sum_{i\in I} b_i \geqq \frac27 \sum_{i=1}^{88} b_i$. Notemos que podemos asumir que $a_i$ está ordenada (cambiando las etiquetas si hace falta), así que asumimos que $a_1 \geqq a_2 \geqq \cdots \geqq a_{88}$.

Intuitivamente el peor caso se da cuando $b_i$ está ordenado al revés que $a_i$. En ese caso tiene sentido buscar un $I$ simétrico (en el sentido de que $I=n+1-I$), de manera que funcione tanto para $(a_i)$ como para $(b_i)$. Busco, pues, $I\subset [88]$, $|I|=28$, simétrico, tal que $\sum_{i\in I} a_i \geqq \frac27 \sum_{i=1}^{88}a_i$ para toda secuencia $a_i$ tal que $a_1\geqq\cdots\geqq a_{88}$. En efecto:

Lema 1. Sean $a_1 \geqq \cdots \geqq a_{88} \geqq 0$ números y $I = \left\{\underbrace{1,4,7,\ldots,40}_{3k+1\text{ para }0\leqq k\leqq13}, \underbrace{49, 52, 55,\ldots,88}_{88-3k\text{ para }0\leqq k\leqq13}\right\}$. Entonces $\sum_{i\in I} a_i \geqq \frac{7}{24} \sum_{i=1}^{88}a_i$.

Demostración. Si $0\leqq k\leqq13$, $a_{3k+1} \geqq \frac{7}{24}(a_{3k+1}+a_{3k+2}+a_{3k+3}) + \frac{3}{24}a_{3k+1}$. Además $\frac{3}{24}a_{3k+1}\geqq \frac{3}{24}\frac{a_{43}+\cdots+a_{48}}{6}$. Por otro lado si $1\leqq k\leqq 13$, $a_{88-3k} \geqq \frac{7}{24}(a_{88-3k}+a_{88-3k+1}+a_{88-3k+2})$, y $a_{88}\geqq \frac{7}{24} a_{88}$. Sumando todo, obtenemos $\sum_{i\in I} a_i \geqq \frac{7}{24}(a_1+\cdots+a_{42}) + 14 \frac{3}{24}\frac{a_{43}+\cdots+a_{48}}{6} + \frac{7}{24}(a_{49}+\cdots+a_{88}) = \frac{7}{24} \sum_{i=1}^{88}a_i$, como queríamos. $\blacksquare$

Hay que probar que esto funciona para cualquier orden de la secuencia $(b_i)$. La idea es que si tomo números de $I$ y los achico, $\sum_{i\in I} a_i$ aumenta, así que se mantiene por encima de $\frac27\sum a_i$. Entonces puedo buscar $I'$ achicando números de $I$ de manera que los números $\{b_i \mid i \in I'\}$ sean lo más grandes posible. La propuesta es recorrer los números $b_i$ de mayor a menor, tomar, si no lo tomé antes, un $j\in I$ con $i\leqq j$, y cambiarlo por $i$. De esa forma $\sum_{i\in I} a_i$ a lo sumo crece, y $\sum_{i\in I}b_i$ es lo más grande posible. El siguiente lema formaliza esta construcción, aunque en su versión simétrica (para que la notación sea menos engorrosa), y prueba que funciona.

Lema 2. Sea $n$ entero positivo, $I=\{j_1<\ldots<j_{m}\}\subset [n]$ y $\sigma$ una permutación de $[n]$. Pongo $I_1=\varnothing$ y $I^{(1)}=I$. Para cada $i=1,\ldots,n$ hago lo siguiente: si $\sigma_i < \min I^{(i)}$, pongo $I^{(i+1)}=I^{(i)}$; si no, tomo el mayor $j\in I^{(i)}$ tal que $j\leqq \sigma_i$, pongo $I^{(i+1)}=I^{(i)}\smallsetminus \{j\}$ y agrego $i$ a $I_1$. Al final tengo $I_1=\{i_1 < \ldots < i_{m'}\}$. Entonces para todo $k=1,\ldots,m'$ tengo $i_k\leqq j_k$, y $m'=m$.

Demostración. Sea $k\in[m']$. Sea $j_t = \min I^{(i_k)}$. Notar que antes de $i_k$ saqué $k-1$ elementos de $I$, luego $t\leqq k$. Como $I^{(1)} \supset I^{(2)} \supset \cdots \supset I^{(i_k)}$, $j_t \in I^{(i)}$ para todo $i\leqq i_k$. Si $i \in [i_k-1]\smallsetminus I_1$, tuvo que pasar $\sigma_i < \min I^{(i)}$ (si no $i\in I_1$), pero $\min I^{(i)} \leqq j_t$ ya que $j_t \in I^{(i)}$, luego $\sigma_i < j_t$. Ahora antes del paso $i_k$ se quitaron $j_1,\ldots,j_{t-1}$ de $I$, es decir, hubo $t-1$ elementos $i$ de $[i_k-1] \cap I_1$ tales que $\sigma_i < j_t$. Entonces $[i_k-1]\smallsetminus I_1 \subset \{i \mid \sigma_i < j_t\}$, luego $[i_k-1]\smallsetminus I_1 \subset \{i \mid \sigma_i < j_t\}\smallsetminus I_1$, pero $|\{i \mid \sigma_i < j_t\}\cap I_1| \geqq t-1$, luego $|\{i \mid \sigma_i < j_t\}\smallsetminus I_1| = |\{i \mid \sigma_i < j_t\}| - |\{i \mid \sigma_i < j_t\}\cap I_1| \leqq j_t-1-(t-1) = j_t-t$. Ahora $|[i_k-1]\smallsetminus I_1| = i_k-1-(k-1)=i_k-k$, luego $i_k -k \leqq j_t-t$. Como $t\leqq k$, tengo $j_t-t \leqq j_{t+1}-(t+1) \leqq \cdots \leqq j_k-k$. Entonces $i_k -k \leqq j_k-k$ y $i_k \leqq j_k$, como queríamos demostrar.
Falta ver que $m'=m$. Claramente $m'\leqq m$, porque cuando se agrega un elemento a $I_1$ se quita uno de $I$. Si $m'<m$, el argumento anterior con $n+1$ en lugar de $i_k$ (jugando el papel de un $i_{m'+1}$ ficticio) prueba que $n+1 \leqq j_{m'+1}$, absurdo. $\blacksquare$

Demostración del teorema. Tenemos $a_1\geqq\cdots\geqq a_{88}$, y existe una permutación $\tau$ de $[88]$ tal que $b_{\tau_1}\geqq\cdots\geqq b_{\tau_{88}}$. Definimos $I = \left\{\underbrace{1,4,7,\ldots,40}_{3k+1\text{ para }0\leqq k\leqq13}, \underbrace{49, 52, 55,\ldots,88}_{88-3k\text{ para }0\leqq k\leqq13}\right\}$, y $\sigma:[88]\to[88]$ dado por $\sigma_i=89-\tau_i$; $\sigma$ es una permutación. Aplicamos el lema anterior a $I$ y $\sigma$. Esto nos da $I_1=\{i_1 < \ldots < i_{28}\}$ tal que $i_k\leqq j_k$ para todo $k\in[28]$, donde $I=\{j_1<\ldots<j_{28}\}$. Además, viendo la definición de $I_1$ en el enunciado del lema, a cada $i\in I_1$ corresponde un $j\in I$ tal que $j\leqq \sigma_i$, y la correspondencia es biunívoca (no le puede tocar el mismo $j$ a dos $i$ distintos). Es decir, hay una biyección $f:I_1\to I$ tal que $f(i) \leqq \sigma_i$ para todo $i\in I_1$. La función $g:I\to I$ dada por $g(i)=89-i$ es una biyección, ya que $I$ es "simétrico". Entonces $h=g\circ f$ es una biyección $I_1\to I$ tal que $h(i)=g(f(i))=89-f(i)\geqq 89-\sigma_i = \tau_i$. Esto implica que $\sum_{i\in I_1} a_{\tau_i} \geqq \sum_{i\in I_1} a_{h(i)} = \sum_{i\in I} a_i$.

Sea $I_2=\{\tau_{i} \mid i \in I_1\}$. Tenemos $$\sum_{i\in I_2}a_i = \sum_{i\in I_1} a_{\tau_i} \geqq \sum_{i\in I} a_i \geqq \frac{7}{24} \sum_{i=1}^{88} a_{i}$$ por el razonamiento anterior y el Lema 1. Por otro lado tenemos que $$\sum_{i\in I_2} b_i = \sum_{i\in I_1} b_{\tau_i} = \sum_{k=1}^m b_{\tau_{i_k}} \geqq \sum_{k=1}^m b_{\tau_{j_k}} = \sum_{i\in I} b_{\tau_i}$$ (porque $i_k\leqq j_k$ y $b_{\tau_{\bullet}}$ es decreciente). Ahora por el Lema 1 aplicado a $b_{\tau_1} \geqq \cdots \geqq b_{\tau_{88}}$ tenemos $$\sum_{i\in I} b_{\tau_i} \geqq \frac{7}{24} \sum_{i=1}^{88} b_{\tau_i} = \frac{7}{24} \sum_{i=1}^{88} b_{i}.$$ Luego $\sum_{i\in I_2} b_i \geqq \frac{7}{24} \sum_{i=1}^{88} b_{i}$. Como $\frac{7}{24}>\frac{2}{7}$, probamos el teorema. $\blacksquare$

Comentario. Con el mismo método, cambiando un poco el conjunto $I$ (acercando un poco 40 y 49) se puede mejorar la cota a $\frac{15}{51}$.

Responder