lunes, 27 de mayo de 2013

Problema del Día (Adán)

En un concurso hay $a$ concursantes y $b$ jueces, con $b\geq 3$ impar. Cada juez califica a cada concursante como aprobado o reprobado. Se sabe que cada par de jueces coinciden en sus calificaciones en a lo más $k$ concursantes. Muestra que

\[\frac{k}{a}\geq \frac{b-1}{2b}\]

14 comentarios:

Juan dijo...

Contraejemplo: a=b=2. El juez 1 reprueba al estudiante 1 y aprueba al estudiante 2, el juez 2 hace lo contrario. K=0.

Juan dijo...

Ok, ya vi que lo corregiste. Bueno ya me salió con $b$ impar, ¿posteo la solución?

Adán Medrano Martín del Campo dijo...

A... perdón, también debo corregir eso, efectivamente $b$ debe ser impar. Ya habías visto el problema?

Diego Alonso Roque Montoya dijo...

APMO, me parece. ya habia visto yo el problema

Juan dijo...
Este comentario ha sido eliminado por el autor.
Juan dijo...

Nopi (No lo habia visto. ¿por?). OK ya estaba preocupado porque no me salía con b par.

Diego Alonso Roque Montoya dijo...

Bueno, no es APMO pero ya lo habia visto

Juan dijo...
Este comentario ha sido eliminado por el autor.
Juan dijo...
Este comentario ha sido eliminado por el autor.
Juan dijo...
Este comentario ha sido eliminado por el autor.
Juan dijo...
Este comentario ha sido eliminado por el autor.
Juan dijo...

SOLUCIÓN: Primeramente, demuestro un lema.

LEMA: Si $ 0 \le x \le b$ es entero, $b=2c+1$, con $c$ natural, entonces
${{x}\choose{2}} + {{{b-x}}\choose{2}} $$\ge {{{c+1}}\choose{2}} +{{c}\choose{2}}$

DEMOSTRACIÓN: Sabemos que, si $f(y)= {{y}\choose{2}}$, $f$ es convexa. También, sin pérdida de generalida $x \le c$. Entonces ($x$, $b-x$) es mayorizada por ($c$, $c+1$). Entonces $f(x)+f(b-x)\le f(c)+f(c+1)$ por Karamata y acabamos.

Ahora, Llamemos $b=2c+1$, con $c \in \mathbb{N}$, ¿no? Entonces ordeno a los concursantes $E_1$, ..., $E_a$, ¿no? Llamemos $x_i$ al número de jueces que aprobaron a $E_i$, ¿no? Ahora ordenamos a los jueces, $J_1$, ..., $J_b$, ¿no?

Contaré el número de tercias de la forma ($J_i$, $J_j$, $E_m$) con $1\le i,j \le b$, $1 \le m \le a$, tal que $J_i$ y $J_j$ coinciden en su calificación de $E_m$, ¿no? (NOTA: No importa el orden de los jueces.)

Por una parte, cada pareja de jueces pueden estar juntos en a lo más $k$ tercias, ¿no? Entonces hay a lo más $k{{b}\choose{2}}$ tercias. Por otra parte, el alumno $E_i$ está en ${{{x_i}}\choose{2}}+{{{b-x_i}}\choose{2}}$ parejas exactamente, ¿no? Por tanto, sabemos que, por el lema, como $x_i+(b-x_i)=b$,

$k{{b}\choose{2}} \ge \sum_{m=1}^a {{x_i}\choose{2}}+{{b-x_i}\choose{2}} \ge $$\sum_{m=1}^a {{c+1}\choose{2}}+{{c}\choose{2}} = a{{c+1}\choose{2}}+a{{c}\choose{2}}=$$ac(\frac{c+1}{2}+\frac{c-1}{2})=ac^2 \Rightarrow $$\frac{k}{a} \ge \frac{c^2}{{{b}\choose{2}}} = \frac{c^2}{c(2c-1)} = \frac{c}{2c-1} = $$\frac{b-1}{2b}$.

Por tanto, acabamos. $\clubsuit$

Juan dijo...

Bueno, hay algunos errores pero me rindo. LaTeX ganó.

Pablo Soberón Bravo dijo...

IMO 1998, Problema 2

Publicar un comentario