Double comptage¶
Domaine : Combinatoire · Niveau : débutant · Prérequis : aucun
L'idée¶
On compte le même ensemble de deux façons différentes, et l'on égale (ou l'on compare) les deux résultats.
L'image à garder est un tableau : la somme de toutes les cases se calcule ligne par ligne ou colonne par colonne, et les deux totaux sont égaux. En combinatoire, les lignes et les colonnes sont deux familles d'objets (des personnes et des clubs, des points et des droites, des sommets et des arêtes), et l'on compte les couples formés d'un objet de chaque famille qui sont « en relation ».
Le premier exemple est le lemme des poignées de main : dans un graphe, la somme des degrés vaut le double du nombre d'arêtes, car chaque arête est comptée une fois par chacune de ses deux extrémités.
Le double comptage sert de trois façons :
- Prouver une identité : deux expressions comptent le même ensemble.
- Prouver une inégalité : une façon de compter donne un majorant, l'autre un minorant.
- Prouver une existence par la moyenne : si une somme de \(N\) termes vaut \(S\), l'un des termes vaut au moins \(\frac{S}{N}\).
Toute la difficulté est de choisir ce que l'on compte : souvent des couples ou des triplets mélangeant les objets de l'énoncé.
Exemple résolu¶
Problème (OIM 1998)
Dans un concours, \(a\) candidats sont notés par \(b\) juges, où \(b \geq 3\) est impair. Chaque juge déclare chaque candidat « reçu » ou « recalé ». Deux juges quelconques donnent le même avis sur au plus \(k\) candidats. Montrer que \(\dfrac{k}{a} \geq \dfrac{b - 1}{2b}\).
Étape 1 : choisir ce que l'on compte. L'hypothèse porte sur des paires de juges d'accord. On compte donc les triplets \((C, \{J, J'\})\) où \(C\) est un candidat et \(J, J'\) deux juges qui donnent le même avis sur \(C\). Notons \(N\) leur nombre.
Étape 2 : compter par paires de juges. Il y a \(\binom{b}{2}\) paires de juges, et chacune est d'accord sur au plus \(k\) candidats :
Étape 3 : compter par candidats. Écrivons \(b = 2m + 1\). Si \(x\) juges déclarent un candidat reçu et \(b - x\) le déclarent recalé, le nombre de paires d'accord sur lui est \(\binom{x}{2} + \binom{b - x}{2}\). Cette quantité est minimale quand les deux groupes sont les plus équilibrés possible, c'est-à-dire pour \(x = m\) ou \(x = m + 1\), où elle vaut \(\binom{m}{2} + \binom{m+1}{2} = m^2\). Donc
Étape 4 : comparer. On obtient \(\frac{a(b-1)^2}{4} \leq \frac{k\,b(b-1)}{2}\), soit \(\frac{k}{a} \geq \frac{b - 1}{2b}\).
Le bon objet à compter mélange les deux familles de l'énoncé (candidats et juges) de sorte que l'hypothèse borne un des deux comptes.
Comment le reconnaître¶
- L'énoncé dit « chaque … a exactement (ou au plus) … » pour deux familles d'objets liées entre elles.
- On demande une borne sur le nombre d'objets d'une configuration.
- Il y a des incidences : des points sur des droites, des éléments dans des ensembles, des personnes dans des clubs, des sommets sur des arêtes.
- On veut une identité entre sommes, ou entre coefficients binomiaux.
- On doit montrer qu'un objet est « beaucoup » utilisé : penser à la moyenne.
Doubles comptages classiques¶
| Situation | Ce que l'on compte |
|---|---|
| Graphe | Les couples (sommet, arête qui le contient) : \(\sum \deg = 2 \times\) nombre d'arêtes |
| Éléments et ensembles | Les couples (élément, ensemble qui le contient) : \(\sum_x (\text{nb d'ensembles contenant } x) = \sum_E \lvert E \rvert\) |
| Paires d'éléments dans un même ensemble | Les triplets \((x, y, E)\) avec \(x, y \in E\) |
| Diviseurs | Les couples \((d, k)\) avec \(d \mid k \leq n\) : \(\sum_{k=1}^n \tau(k) = \sum_{d=1}^n \left\lfloor \frac{n}{d} \right\rfloor\) |
| Identités binomiales | Les comités avec un président : \(k\binom{n}{k} = n\binom{n-1}{k-1}\) |
| Figures découpées en morceaux | Les angles, les côtés ou les sommets, comptés par morceau puis globalement |
Exercices d'échauffement¶
- Existe-t-il un groupe de \(7\) personnes dans lequel chacun connaît exactement \(3\) autres personnes ?
- Montrer que \(k\binom{n}{k} = n\binom{n-1}{k-1}\) en comptant des comités avec un président.
- Montrer que \(\tau(1) + \tau(2) + \cdots + \tau(n) = \left\lfloor \frac{n}{1} \right\rfloor + \left\lfloor \frac{n}{2} \right\rfloor + \cdots + \left\lfloor \frac{n}{n} \right\rfloor\), où \(\tau(k)\) est le nombre de diviseurs de \(k\).
- Dans un tournoi à \(n\) joueurs où chacun rencontre chacun une fois, sans match nul, le joueur \(i\) a \(w_i\) victoires et \(l_i\) défaites. Montrer que \(\sum w_i^2 = \sum l_i^2\).
- Montrer l'identité de Vandermonde \(\sum_{k} \binom{m}{k}\binom{n}{r - k} = \binom{m + n}{r}\) en choisissant \(r\) personnes dans un groupe de \(m\) filles et \(n\) garçons.
Double comptage dans la shortlist¶
- 2016 C3 : on compte de deux façons les couples (triangle isocèle, côté bicolore).
- 2015 C2 : on compte les couples (paire \(\{A, B\}\), point \(C\) équidistant de \(A\) et \(B\)).
- 2016 C4 : on compte les couples (ligne, case) de deux façons, puis on compare modulo \(3\).
- 2017 G8, solution 2 : les « coins pointus », comptés par segment (\(2\) chacun) puis par région (\(3\) chacune), donnent \(2s = 3r\).
- 2025 C7 : la somme des angles des triangles et le décompte des côtés donnent le nombre de triangles et d'arêtes.
Pour approfondir : Objectif Olympiades de Mathématiques, tome 3 (M. Aassila), p. 251 (le principe de Fubini), p. 251 à 260 (exemples, dont la somme des \(\tau(k)\) et le théorème d'Erdős-Ko-Rado p. 258), p. 261 à 272 (couplage et appariement) ; tome 4, p. 26 (le double comptage pour les problèmes de maximum).
Problèmes de la shortlist¶
49 problèmes · difficulté moyenne : ★★★★★ (3,1) · dont 7 choisis pour l'OIM
Répartition par difficulté : 1 ★ : 5 · 2 ★ : 8 · 3 ★ : 18 · 4 ★ : 12 · 5 ★ : 6
| Problème | Difficulté | Concepts |
|---|---|---|
| 2024 C1 | ★☆☆☆☆ | Invariants et monovariants |
| 2017 C2 | ★☆☆☆☆ | Invariants et monovariants |
| 2015 C2 · OIM P1 | ★☆☆☆☆ | Géométrie combinatoire : enveloppe convexe, points du réseau · Principe des tiroirs · Graphes : degrés, chemins, arbres |
| 2014 C1 | ★☆☆☆☆ | Récurrence et constructions récursives |
| 2012 C2 | ★☆☆☆☆ | Récurrence et constructions récursives |
| 2025 C4 | ★★☆☆☆ | Invariants et monovariants |
| 2024 C3 | ★★☆☆☆ | Invariants et monovariants · Principe extrémal · Récurrence et constructions récursives |
| 2018 C3 | ★★☆☆☆ | - |
| 2016 C3 | ★★☆☆☆ | - |
| 2016 C4 · OIM P2 | ★★☆☆☆ | - |
| 2012 C3 | ★★☆☆☆ | AM-GM et moyennes · Cauchy-Schwarz et lemme de Titu |
| 2011 C4 | ★★☆☆☆ | Principe des tiroirs · Graphes : degrés, chemins, arbres |
| 2009 C2 | ★★☆☆☆ | Récurrence et constructions récursives |
| 2023 A5 | ★★★☆☆ | - |
| 2022 N5 | ★★★☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2021 C5 | ★★★☆☆ | Principe des tiroirs |
| 2019 A4 | ★★★☆☆ | - |
| 2018 C5 | ★★★☆☆ | Invariants et monovariants |
| 2017 A5 | ★★★☆☆ | Graphes : degrés, chemins, arbres |
| 2015 C5 · OIM P6 | ★★★☆☆ | Graphes : degrés, chemins, arbres · Principe des tiroirs · AM-GM et moyennes |
| 2014 C5 · OIM P6 | ★★★☆☆ | Principe extrémal · Géométrie combinatoire : enveloppe convexe, points du réseau |
| 2013 A4 | ★★★☆☆ | Graphes : degrés, chemins, arbres · Récurrence et constructions récursives |
| 2013 C4 | ★★★☆☆ | Principe des tiroirs · Principe extrémal |
| 2013 A5 | ★★★☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Congruences, théorèmes de Fermat et d'Euler |
| 2012 C5 | ★★★☆☆ | Graphes : degrés, chemins, arbres · Coloriages et pavages |
| 2010 C5 | ★★★☆☆ | Graphes : degrés, chemins, arbres |
| 2009 C4 | ★★★☆☆ | Coloriages et pavages · Convexité, inégalité de Jensen, lissage |
| 2008 C4 · OIM P5 | ★★★☆☆ | Bijections et dénombrement |
| 2008 C5 | ★★★☆☆ | Principe extrémal |
| 2007 C3 | ★★★☆☆ | Équations diophantiennes : factorisation et encadrement |
| 2007 N3 | ★★★☆☆ | Congruences, théorèmes de Fermat et d'Euler · Principe des tiroirs |
| 2025 C6 | ★★★★☆ | Graphes : degrés, chemins, arbres · Principe extrémal |
| 2025 C7 | ★★★★☆ | Géométrie combinatoire : enveloppe convexe, points du réseau |
| 2024 N6 | ★★★★☆ | Congruences, théorèmes de Fermat et d'Euler · Résidus quadratiques · Principe des tiroirs |
| 2022 C8 · OIM P6 | ★★★★☆ | Graphes : degrés, chemins, arbres |
| 2021 C7 | ★★★★☆ | Coloriages et pavages |
| 2017 C6 | ★★★★☆ | Récurrence et constructions récursives |
| 2014 N6 | ★★★★☆ | Théorème des restes chinois · Congruences, théorèmes de Fermat et d'Euler · Polynômes à coefficients entiers |
| 2014 C7 | ★★★★☆ | Invariants et monovariants · Géométrie combinatoire : enveloppe convexe, points du réseau |
| 2011 C6 | ★★★★☆ | Principe extrémal |
| 2009 N5 | ★★★★☆ | Polynômes à coefficients entiers · Congruences, théorèmes de Fermat et d'Euler |
| 2008 C6 | ★★★★☆ | Récurrence et constructions récursives |
| 2007 C8 | ★★★★☆ | Géométrie combinatoire : enveloppe convexe, points du réseau |
| 2025 C8 · OIM P6 | ★★★★★ | Coloriages et pavages · Principe extrémal · AM-GM et moyennes · Graphes : degrés, chemins, arbres |
| 2018 C7 | ★★★★★ | Graphes : degrés, chemins, arbres · Coloriages et pavages |
| 2017 G8 | ★★★★★ | Invariants et monovariants · Graphes : degrés, chemins, arbres |
| 2014 C9 | ★★★★★ | Invariants et monovariants · Graphes : degrés, chemins, arbres |
| 2012 N8 | ★★★★★ | Ordre d'un élément et racines primitives · Résidus quadratiques · Cauchy-Schwarz et lemme de Titu |
| 2011 C7 | ★★★★★ | Coloriages et pavages · Récurrence et constructions récursives |