Certains problèmes de combinatoire, qui paraissent parfois très difficiles aux premiers abords, peuvent être résolus de manière très directe en utilisant le double comptage. Voici par exemple comment résoudre le problème suivant, qui n'est autre que le problème 2 de l'IMO 1998.
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 :
- 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.$$
- 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}.$$