Aller au contenu

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 :

  1. Prouver une identité : deux expressions comptent le même ensemble.
  2. Prouver une inégalité : une façon de compter donne un majorant, l'autre un minorant.
  3. 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 :

\[N \leq k \binom{b}{2} = \frac{k\,b(b-1)}{2}.\]

É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

\[N \geq a\,m^2 = \frac{a(b-1)^2}{4}.\]

É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

  1. Existe-t-il un groupe de \(7\) personnes dans lequel chacun connaît exactement \(3\) autres personnes ?
  2. Montrer que \(k\binom{n}{k} = n\binom{n-1}{k-1}\) en comptant des comités avec un président.
  3. 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\).
  4. 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\).
  5. 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.

Parcours suggéré

Un choix de problèmes de la shortlist, du plus accessible au plus difficile, où ce concept joue le premier rôle. La liste complète est plus bas.

Étape 1 — Premiers pas (1 ★)

  • 2012 C2 ★☆☆☆☆ : Combien de paires disjointes de \(\{1, \ldots, n\}\), de sommes distinctes au plus \(n\), peut-on choisir ?
  • 2014 C1 ★☆☆☆☆ : Découper un rectangle en évitant \(n\) points intérieurs demande au moins \(n + 1\) petits rectangles.
  • 2024 C1 ★☆☆☆☆ : \(n\) élèves, \(n\) courses, et un score qui récompense les bons classements : quelle somme des scores au maximum ?

Étape 2 — Consolidation (2 ★)

  • 2016 C4 ★★☆☆☆ · OIM P2 : Pour quels \(n\) peut-on remplir un tableau \(n \times n\) de \(I\), \(M\), \(O\) équilibrés sur les lignes, colonnes et certaines diagonales ?
  • 2016 C3 ★★☆☆☆ : Les sommets d'un \(n\)-gone régulier sont coloriés en trois couleurs, chacune en nombre impair : un triangle isocèle est tricolore.
  • 2018 C3 ★★☆☆☆ : Sisyphe déplace des pierres d'autant de cases au plus que la pile en compte : il lui faut au moins \(\sum \lceil n/k \rceil\) tours.

Étape 3 — Approfondissement (3 ★)

  • 2018 C5 ★★★☆☆ : Un tournoi de tennis où chaque joueur paie l'hôtel de son premier à son dernier match : quel coût total minimal ?
  • 2023 A5 ★★★☆☆ : Une permutation de \(1, \ldots, 2023\) dont les écarts successifs sont tous distincts commence ou finit par au moins \(507\).

Étape 4 — Défi (4 ★ – 5 ★)

  • 2022 C8 ★★★★☆ · OIM P6 : Remplir un tableau \(n \times n\) de \(1\) à \(n^2\) avec le moins possible de chemins croissants partant d'un minimum local.
  • 2012 N8 ★★★★★ : Pour \(p > 100\) premier, tout résidu s'écrit \(a^2 + b^5\) modulo \(p\).

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

46 problèmes · difficulté moyenne : ★★★★★ (3,1) · dont 6 choisis pour l'OIM
Répartition par difficulté : 1 ★ : 5 · 2 ★ : 8 · 3 ★ : 16 · 4 ★ : 11 · 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
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 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 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
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