IMO 1998 - Combinatoire

Question

J'essaye ce problème de combinatoire IMO $1998$ P2 qui va comme ceci:

Dans une compétition, il y a $m$ candidats et $n$ juges, où $n \geq 3$est un entier impair. Chaque juge attribue à chaque concurrent la note «réussite» ou «échec». Supposer$k$ est un nombre tel que, pour deux juges quelconques, leurs notes coïncident au plus $k$concurrents. Prouve-le$$\frac{k}{m}\geq \frac{n-1}{2n}$$

Je suis complètement perplexe sur la façon de commencer, pouvez-vous me donner des indices?

Answer 1

Considérez le nombre de combinaisons $(\{j_1, j_2\},c)$, où $\{j_1, j_2\}$ est une paire de juges distincts, et $c$est un concurrent sur lequel ils sont d'accord. Vous pouvez arriver à cette quantité de deux manières:

1. Somme sur les concurrents, le nombre de paires de juges qui sont d'accord sur eux.

2. Somme sur paires de juges, le nombre de concurrents sur lesquels ils sont d'accord.

Alors la quantité additionnée en 1. peut être bornée ci-dessous par une expression impliquant $n$ (rappelles toi $n$ est impair), tandis que la quantité additionnée en 2. peut être bornée ci-dessus par $k$. La combinaison produit l'inégalité souhaitée.