Théorie > Combinatoire > Double comptage

Nous allons cette fois compter le nombre $N$ de couples $(P_1, \{P_2, P_3\})$ telles que $|P_1P_2| = |P_1P_3|$.

1. Si on se fixe d'abord un point $P_1$, alors par hypothèse il y a au moins $k$ points à égale distance de $P_1$. On en déduit qu'il y a au moins $C^2_k$ paires de points $\{P_2, P_3\}$ telles que $|P_1P_2| = |P_1P_3|$. Puisqu'il y a $n$ choix pour $P_1$, on a
   $$N \geq n \cdot \frac{k(k-1)}{2}.$$
2. Si maintenant, on se fixe d'abord deux points $P_2$ et $P_3$ distincts, alors un point $P_1$ se situe à égale distance de ces deux points si et seulement si $P_1$ est sur la médiatrice de $[P_2P_3]$. Comme il n'y a pas trois points alignés dans $S$, il y a au maximum $2$ points sur cette médiatrice, ce qui signifie qu'il y a au plus deux points $P_1$ tels que $|P_1P_2| = |P_1P_3|$. Puisqu'il y a $C^2_n$ façons de choisir $P_2$ et $P_3$, on a
   $$N \leq \frac{n(n-1)}{2} \cdot 2.$$

On a donc prouvé que
$$n \cdot \frac{k(k-1)}{2} \leq N \leq \frac{n(n-1)}{2} \cdot 2,$$ ce qui après simplification devient
$$k^2-k-2(n-1) \leq 0.$$ Le membre de gauche est un polynôme du second degré en $k$, et $k$ doit donc se situer entre les deux racines du polynôme pour que cette expression soit négative. Or, les deux racines sont données par
$$\frac{1 \pm \sqrt{1 + 8(n-1)}}{2},$$ donc on doit avoir
$$k \leq \frac{1 + \sqrt{8n-7}}{2} < \frac{1}{2} + \frac{\sqrt{8n}}{2} = \frac{1}{2} + \sqrt{2n},$$ ce qui est exactement la borne désirée pour $k$.