Théorie > Combinatoire > Double comptage

Nous allons pour résoudre ce problème évaluer une quantité de deux manières différentes. Au vu des hypothèses, il n'est pas insensé de penser à dénombrer les couples $(\{J_1, J_2\}, P)$ où $J_1$ et $J_2$ sont des juges, $P$ est un participant et $J_1$ et $J_2$ sont d'accord sur $P$. Évaluons ce nombre $N$ de deux manières :

1. Premièrement, regardons les paires de juges une par une. Il y a $C^2_n$ paires de juges $\{J_1,J_2\}$, et pour chacune de ces paires on sait par hypothèse qu'il existe au maximum $k$ participants $P$ tels que $J_1$ et $J_2$ sont d'accord sur $P$. Cela signifie que
   $$N \leq \frac{n(n-1)}{2} \cdot k.$$
2. Considérons maintenant les participants un par un. Pour chaque participant $P$, notons $x$ le nombre de juges ayant noté $P$ comme "réussi". Il y a alors $n-x$ juges ayant noté $P$ comme "raté". Dans ce cas, le nombre de paires de juges étant d'accord sur $P$ est égal à
   $$C^2_x + C^2_{n-x} = \frac{x(x-1)}{2} + \frac{(n-x)\cdot(n-x-1)}{2} = \frac{2x^2-2nx+n^2-n}{2}.$$

Le minimum de cette fonction en $x$ est atteint en $x = \frac{n}{2}$, mais comme $n$ est impair le minimum possible dans notre contexte est atteint en $x =\frac{n-1}{2}$ et $x = \frac{n+1}{2}$ ce qui donne
$$\left(\frac{n-1}{2}\right)^2-n\left(\frac{n-1}{2}\right) + \frac{n^2-n}{2} = \left(\frac{n-1}{2}\right)^2.$$ On a donc au moins $\left(\frac{n-1}{2}\right)^2$ paires de juges pour chaque participant, ce qui donne finalement
$$N \geq m \cdot \left(\frac{n-1}{2}\right)^2.$$

On a donc prouvé que
$$k \cdot \frac{n(n-1)}{2} \geq N \geq m \cdot \left(\frac{n-1}{2}\right)^2,$$ ce qui se révèle être équivalent à
$$\frac{k}{m} \geq \frac{n-1}{2n}.$$