IMO 1998 - Combinatória

Question

Estou tentando este problema IMO Combinatorics$1998$P2 que fica assim:

Em uma competição, existem$m$competidores e$n$juízes, onde$n \geq 3$é um inteiro ímpar. Cada juiz classifica cada competidor como "aprovado" ou "reprovado". Suponha$k$é um número tal que, para quaisquer dois juízes, suas avaliações coincidem por no máximo$k$competidores. Prove que$$\frac{k}{m}\geq \frac{n-1}{2n}$$

Estou completamente confuso sobre como começar, você poderia me dar alguma dica?

Answer 1

Considere o número de combinações$(\{j_1, j_2\},c)$, Onde$\{j_1, j_2\}$é um par de juízes distintos, e$c$é um concorrente com o qual eles concordam. Você pode chegar a essa quantidade de duas maneiras:

1. Soma sobre os competidores, o número de pares de juízes que concordam com eles.

2. Some os pares de juízes, o número de competidores que eles concordam.

Então a quantidade sendo somada em 1 pode ser limitada abaixo por uma expressão envolvendo$n$(lembrar$n$é ímpar), enquanto a quantidade sendo somada em 2. pode ser limitada acima por$k$. A combinação produz a desigualdade desejada.