Théorie > Combinatoire > Double comptage


Général

Introduction Chapitre entier

Points théoriques

Principe Formule de Cayley Premier exemple Deuxième exemple

Exercices

Exercice 1 Exercice 2 Exercice 3 Exercice 4

Deuxième exemple

Voici un autre problème, d'un genre fort différent, qui peut également être résolu de cette manière. Il s'agit du problème 3 de l'IMO 1989.

Problème : Soient $n$ et $k$ des entiers strictement positifs et $S$ un ensemble de $n$ points dans le plan tels que :
  1. Trois points distincts ne sont jamais alignés.
  2. Pour tout point $P$ de $S$, il y a au moins $k$ points de $S$ à égale distance de $P$.
Prouver que $$k < \frac{1}{2} + \sqrt{2n}.$$

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_1$ et $P_2$, 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$.