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}\]
lunes, 27 de mayo de 2013
Suscribirse a:
Comentarios de la entrada (Atom)
14 comentarios:
Contraejemplo: a=b=2. El juez 1 reprueba al estudiante 1 y aprueba al estudiante 2, el juez 2 hace lo contrario. K=0.
Ok, ya vi que lo corregiste. Bueno ya me salió con $b$ impar, ¿posteo la solución?
A... perdón, también debo corregir eso, efectivamente $b$ debe ser impar. Ya habías visto el problema?
APMO, me parece. ya habia visto yo el problema
Nopi (No lo habia visto. ¿por?). OK ya estaba preocupado porque no me salía con b par.
Bueno, no es APMO pero ya lo habia visto
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$
Bueno, hay algunos errores pero me rindo. LaTeX ganó.
IMO 1998, Problema 2
Publicar un comentario