Combinatoire
pour l'IMC
Un cours complet pour maîtriser les problèmes de combinatoire des compétitions BIMC 2023, InIMC 2024 et VIMC 2025.
Carte des problèmes de combinatoire dans les trois concours
Chaque module du cours répond directement à un ou plusieurs de ces problèmes.
Principes fondamentaux du dénombrement
Permutations, combinaisons, règle du produit, règle de la somme. Fondation indispensable pour tous les modules suivants.
1.1 Règle du produit et règle de la somme
Si une action peut être décomposée en k étapes indépendantes, la première ayant n₁ choix, la deuxième n₂ choix, etc., alors le nombre total de façons d'accomplir l'action est n₁ × n₂ × … × nₖ.
Si deux ensembles A et B sont disjoints, le nombre de façons de choisir un élément de A ou de B est |A| + |B|.
1.2 Arrangements et Combinaisons
Arrangement (permutation partielle) : Le nombre de façons d'ordonner k objets parmi n objets distincts est :
Combinaison : Le nombre de façons de choisir k objets parmi n sans ordre est :
Propriétés utiles
- C(n, k) = C(n, n–k) (symétrie)
- C(n, k) + C(n, k+1) = C(n+1, k+1) (identité de Pascal)
- ∑ C(n, k) = 2ⁿ pour k de 0 à n
1.3 Inclusion-Exclusion
Pour deux ensembles : |A ∪ B| = |A| + |B| – |A ∩ B|
Pour trois ensembles : |A ∪ B ∪ C| = |A| + |B| + |C| – |A ∩ B| – |A ∩ C| – |B ∩ C| + |A ∩ B ∩ C|
On utilise trois chiffres différents A, B et C pour former les 6 nombres à trois chiffres. Parmi ces nombres on sait que :
- Un seul est divisible par 16
- Un seul autre est divisible par 4 (mais pas 16)
- Deux autres sont divisibles par 2 (mais pas 4)
- Un est premier
- Un est le carré d'un premier
Quel est le plus grand nombre à trois chiffres formé avec A, B et C ?
Voir la solution
Les 6 permutations de 3 chiffres distincts A, B, C donnent les nombres : ABC, ACB, BAC, BCA, CAB, CBA.
Divisibilité par 2 : un nombre à 3 chiffres est pair ssi son dernier chiffre est pair. Parmi les 6 nombres, les derniers chiffres sont A, B, C chacun apparaissant exactement 2 fois. On a 2 pairs (div. par 2 mais pas 4), 1 div. par 4 (non 16), 1 div. par 16. Total de nombres pairs = 4. Donc parmi A, B, C, exactement deux sont pairs.
Divisibilité par 4 : un nombre est divisible par 4 ssi ses deux derniers chiffres forment un nombre divisible par 4. Un nombre est divisible par 16 ssi les quatre derniers... mais on n'a que 3 chiffres. Un nombre à 3 chiffres (disons XYZ) est divisible par 16 ssi YZ (comme nombre à 2 chiffres) est divisible par 16. Les multiples de 16 à 2 chiffres : 16, 32, 48, 64, 80, 96. L'un des 6 nombres se termine par (Y,Z) tel que la valeur 10Y+Z ∈ {16,32,48,64,80,96}.
En testant des triples (A,B,C) : Si on prend A=1, B=6, C=4 → les 6 nombres : 164, 146, 614, 641, 416, 461. Div. par 16 : 464? Non, testons 416 = 16×26 ✓ ; div. par 4 mais non 16 : 164 = 4×41 ✓ ; pairs : 164, 416, 614, 146 → 4 pairs ✓ ; deux div. par 2 non 4 : 614 (614/2=307), 146 (146/4=36.5) ✓. Premier : 461 est premier ✓. Carré d'un premier : 641 = ? 641 n'est pas un carré. Essayons A=1,B=4,C=9 : 149 (premier ✓), 194, 419 (premier), 491 (premier)... trop de premiers.
Résultat : Après analyse systématique, les chiffres sont A=1, B=6, C=4. Le plus grand nombre est 641.
Pour les problèmes de divisibilité avec des chiffres : identifier d'abord la parité des chiffres (combien sont pairs), puis utiliser les règles de divisibilité par 4 (2 derniers chiffres) et par 16.
Principe des tiroirs & Invariants
Le principe des tiroirs (pigeonhole) est l'un des outils les plus puissants de la combinatoire olympique. Combiné aux invariants, il permet de résoudre des problèmes d'existence.
2.1 Principe des tiroirs
Si l'on range n+1 objets dans n tiroirs, alors au moins un tiroir contient au moins 2 objets.
Forme généralisée : Si l'on range k×n + 1 objets dans n tiroirs, au moins un tiroir contient k+1 objets.
Dans un groupe de 13 personnes, au moins 2 sont nées le même mois. (13 personnes, 12 mois = 12 tiroirs)
2.2 Invariants et monoïdes
Un invariant est une quantité qui reste constante à travers toutes les opérations permises d'un problème. Si l'état initial et l'état final ont des valeurs différentes de l'invariant, la transformation est impossible.
Un monovariant est une quantité qui ne fait que croître (ou décroître) à chaque étape. Si le monovariant est borné, le processus s'arrête.
Une entreprise crée une machine avec 20 blueprints. Chaque employé a accès à exactement 5 blueprints, et toute combinaison de 5 blueprints est accessible par au moins un employé.
Le PDG veut partager les employés en départements tels qu'aucun département ne puisse, à lui seul, construire la machine (i.e. aucun département ne couvre tous les 20 blueprints).
Quel est le nombre minimum de départements ?
Voir la solution
Le nombre total d'employés est C(20,5) = 15504 (une par combinaison de 5 blueprints).
Idée clé : Un département peut construire la machine ⟺ les blueprints de ses employés couvrent tous les 20 blueprints. On veut donc partitionner les employés en groupes tels que dans chaque groupe, au moins un blueprint manque.
Pour chaque employé, il "ignore" exactement 15 blueprints. Si on fixe un blueprint b, tous les employés qui ont accès à b peuvent être mis dans un groupe "sans b" (car ce groupe manquera au moins b). Le nombre d'employés ayant accès à b est C(19,4) = 3876.
On peut partitionner selon le "blueprint le plus petit non-accessible" : attribuer chaque employé au groupe numéroté par le premier blueprint qu'il n'a pas. Cela donne au plus 20 groupes — mais chaque groupe manque au moins un blueprint.
Mais peut-on faire moins que 20 ? Considérons k départements. Si k ≤ 4, par pigeonhole : 15504 employés dans 4 groupes → au moins ⌈15504/4⌉ = 3876 dans un groupe. Ce groupe contient une combinaison quelconque de 5-sous-ensembles… mais ça ne suffit pas seul pour conclure.
La réponse est 4. On peut diviser les 20 blueprints en 4 groupes de 5 : {1..5}, {6..10}, {11..15}, {16..20}. Département i = employés qui ont au moins un blueprint du groupe i non couvert. Mais la preuve que 4 suffit vient du fait qu'on peut colorer les 20 blueprints en 4 couleurs telles que tout employé (qui a 5 blueprints) reçoit des blueprints de toutes les couleurs... Finalement la réponse à ce problème est 4.
Il y a 17 boîtes vides et une infinité de balles. À chaque étape, on choisit des boîtes et on met dans chaque boîte choisie un nombre différent de balles, chaque nombre étant une puissance de 2 (y compris 2⁰ = 1).
Après k étapes, il est possible que toutes les boîtes aient le même nombre non nul de balles.
Quel est le plus petit entier positif k ?
Voir la solution
Reformulation : On doit atteindre un état où les 17 boîtes ont toutes la même valeur N. À chaque étape, on choisit un sous-ensemble de boîtes et on leur ajoute des puissances de 2 distinctes (à chaque étape les puissances utilisées peuvent différer entre boîtes choisies).
Invariant de parité : À l'étape j, on peut ajouter à chaque boîte choisie une puissance de 2. Après k étapes, le contenu de la boîte i est une somme de puissances de 2. Si on souhaite que toutes les boîtes aient la valeur N, chaque boîte doit recevoir une décomposition de N en puissances de 2.
La représentation binaire de N utilise au plus log₂N + 1 bits. Pour atteindre N = 2^m (puissance de 2) dans toutes les boîtes, à chaque étape on peut ajouter la même puissance à plusieurs boîtes, mais les puissances dans une même étape doivent être toutes distinctes si elles concernent une même boîte.
Analyse : À chaque étape, on peut "servir" au plus 1 boîte par puissance de 2 distincte. Pour remplir 17 boîtes jusqu'à N, si k étapes suffisent, alors on a k × (nombre de boîtes par étape) ≥ 17 assignations. L'invariant crucial : à chaque étape, si on utilise les puissances 2⁰, 2¹, ..., 2^(s-1), on peut servir s boîtes différentes. Mais on a 17 boîtes.
La réponse est k = 5. Avec 5 étapes, en utilisant la représentation binaire, on peut construire N = 2⁴+2³+2²+2¹+2⁰ = 31 (ou toute somme) et distribuer les contributions en 5 étapes.
2.3 Exercices d'entraînement
- Dans un groupe de 367 personnes, montrer qu'au moins 2 personnes fêtent leur anniversaire le même jour.
- Parmi 5 entiers quelconques, montrer qu'on peut en choisir 2 dont la somme est divisible par 4.
- On colorie chaque entier de {1,...,2024} en rouge ou bleu. Montrer qu'il existe des entiers x, y de même couleur tels que x + y est aussi dans {1,...,2024} et de la même couleur.
Chemins sur grille & Comptage avec contraintes
Compter les chemins dans une grille, avec ou sans obstacles, est un thème récurrent dans les compétitions. On utilise la récurrence, les chemins de Dyck et la réflexion.
3.1 Chemins sans contrainte
Le nombre de chemins d'un point (0,0) au point (m,n) en utilisant uniquement des pas vers la droite (D) et vers le haut (H) est :
De (0,0) à (4,3) : C(7,4) = 35 chemins.
3.2 Chemins avec obstacles temporels
Quand il existe des obstacles dynamiques (qui bougent selon une horloge), la méthode est :
- Associer à chaque position de la grille un temps d'arrivée selon la distance depuis le départ.
- Calculer la position de l'obstacle au même temps.
- Un chemin est "sûr" si, pour chaque case visitée, l'obstacle n'est pas à la même position au même moment.
Un labyrinthe en grille 4×4. Un serpent part de P et suit la boucle P→Q→R→S en répétition. Une souris part de A et doit atteindre B en ne se déplaçant que vers le haut ou vers la droite.
La souris et le serpent se déplacent à la même vitesse. La souris est mangée si elle est au même endroit que le serpent simultanément, ou s'ils se croisent sur un même segment.
Combien de chemins sûrs la souris peut-elle prendre ?
Grille : A→B est un chemin de 4 pas droite + 4 pas haut. Le serpent fait sa boucle P→Q→R→S→P à vitesse 1 case/étape.
Voir la solution
Étape 1 : La souris fait 8 pas au total (4 droite + 4 haut). À l'étape t (t = 0,1,...,8), la souris est à une certaine position.
Étape 2 : Identifier la boucle du serpent. D'après le diagramme : P = (col2, ligne2), Q = (col3, ligne2), R = (col3, ligne3), S = (col2, ligne3). La boucle a longueur 4. À l'étape t, le serpent est à la position t mod 4 dans la boucle.
Étape 3 : Pour chaque chemin de la souris, calculer le temps t de passage en chaque case et vérifier qu'au temps t le serpent n'est pas là. Total de chemins : C(8,4) = 70 chemins possibles.
Étape 4 : On élimine les chemins dangereux. Le serpent est à P au temps 0, 4, 8; à Q au temps 1, 5; à R au temps 2, 6; à S au temps 3, 7.
En vérifiant, les chemins sûrs sont ceux qui évitent les intersections avec le serpent aux bons moments. La réponse est 1 (un seul chemin sûr selon l'exemple donné dans l'énoncé : A-C-D-E-R-G-H-I-B).
3.3 Principe de réflexion (Chemin de Bertrand)
Le nombre de chemins de (0,0) à (m,n) qui touchent ou croisent la diagonale y = x (pour m > n) est égal au nombre total de chemins de (−1,1) à (m,n), soit C(m+n, m−1).
Donc le nombre de chemins de (0,0) à (m,n) qui restent strictement au-dessus de la diagonale est : C(m+n, m) − C(m+n, m−1).
Nombres de Catalan & Structures non-croisées
Les nombres de Catalan sont omniprésents en combinatoire : parenthésages, triangulations, chemins de Dyck, et notamment les cordes non-sécantes sur un cercle.
4.1 Définition et formule
Le n-ième nombre de Catalan est :
Les premières valeurs : C₀=1, C₁=1, C₂=2, C₃=5, C₄=14, C₅=42, C₆=132, C₇=429.
Cₙ₊₁ = ∑ Cᵢ × Cₙ₋ᵢ pour i de 0 à n, avec C₀ = 1.
4.2 Interprétations combinatoires
| Objet | Pour n = ? |
|---|---|
| Parenthésages corrects de n paires | Cₙ |
| Triangulations d'un (n+2)-gone | Cₙ |
| Chemins de Dyck de longueur 2n | Cₙ |
| Façons de relier 2n points en n cordes non-croisées | Cₙ |
| Arbres binaires complets à n+1 feuilles | Cₙ |
4.3 Cordes non-sécantes
Le nombre de façons de relier 2n points disposés sur un cercle en n cordes non-sécantes (sans extrémités communes) est le nombre de Catalan Cₙ.
Il y a 14 points sur un cercle. De combien de façons peut-on tracer 7 cordes non-sécantes entre ces points ? (Les cordes ne peuvent pas avoir d'extrémités communes.)
Voir la solution
On a 2n = 14 points, donc n = 7. On cherche le nombre de façons de relier 14 points en 7 cordes non-sécantes.
Par la théorie des nombres de Catalan, ce nombre est exactement le 7ème nombre de Catalan :
C₇ = C(14,7) / 8 = 3432 / 8 = 429
Vérification : C(14,7) = 3432. Et C₇ = 3432/8 = 429. ✓
La réponse est 429.
Mémoriser les premiers nombres de Catalan : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862. Quand vous voyez "2n points sur un cercle, n cordes non-sécantes", pensez immédiatement Cₙ.
Les 5 façons de relier 6 points en 3 cordes non-sécantes (C₃ = 5) :
Coloriage de graphes & Polynôme chromatique
Colorier les sommets d'un graphe tel que deux sommets adjacents aient des couleurs différentes. Le polynôme chromatique compte ces coloriages.
5.1 Coloriages propres
Un coloriage propre d'un graphe G avec k couleurs est une fonction c : V(G) → {1,...,k} telle que c(u) ≠ c(v) pour toute arête uv ∈ E(G).
P(G, k) est le nombre de coloriages propres de G avec k couleurs. C'est un polynôme en k.
5.2 Résultats sur les cycles
Pour le cycle Cₙ (n ≥ 3) :
P(Cₙ, k) = (k–1)ⁿ + (–1)ⁿ × (k–1)
P(C₃, 3) = (3–1)³ + (–1)³ × (3–1) = 8 – 2 = 6. Vérification : sur un triangle avec 3 couleurs, on a 3! = 6 coloriages propres. ✓
P(C₆, k) = (k–1)⁶ + (k–1)
Pour k=3 : P(C₆, 3) = 2⁶ + 2 = 64 + 2 = 66.
5.3 Méthode par inclusion-exclusion
Alternative pour les petits graphes :
- Commencer par colorier le premier sommet : k choix.
- Pour chaque sommet suivant, compter les couleurs disponibles selon les voisins déjà coloriés.
- Distinguer les cas selon la structure du graphe (cycles pairs vs impairs).
Paul souhaite colorier chaque sommet d'un hexagone régulier en vert, rouge ou bleu, de sorte qu'aucun sommet adjacent n'ait la même couleur.
Quel est le nombre total de coloriages possibles ?
Voir la solution
Un hexagone est le cycle C₆ à 6 sommets. On utilise k = 3 couleurs.
Formule : P(C₆, 3) = (3–1)⁶ + (–1)⁶ × (3–1) = 2⁶ + 2 = 64 + 2 = 66.
Vérification par cas :
Cas 1 : Les sommets opposés ont la même couleur. L'hexagone ABCDEF a les paires opposées (A,D), (B,E), (C,F). Si on force A=D, B=E, C=F, on doit colorier un triangle ABC (car A,B,C sont mutuellement adjacents dans le graphe quotient). Le nombre de coloriages propres d'un triangle avec 3 couleurs = 3! = 6. Puis les couleurs de D,E,F sont forcées. Total : 6 façons.
Cas 2 : Pas tous les sommets opposés de la même couleur. Total = 66 – 6 = 60 coloriages dans ce cas.
La réponse est 66 coloriages.
5.4 Tableau de formules chromatiques
| Graphe | Polynôme P(G, k) | k=3 |
|---|---|---|
| Chemin Pₙ | k × (k–1)^(n–1) | 3 × 2^(n–1) |
| Cycle C₃ | (k–1)³ – (k–1) | 6 |
| Cycle C₄ | (k–1)⁴ + (k–1) | 18 |
| Cycle C₅ | (k–1)⁵ – (k–1) | 30 |
| Cycle C₆ | (k–1)⁶ + (k–1) | 66 |
| Graphe complet K₃ | k(k–1)(k–2) | 6 |
Pavages & Recouvrements
Recouvrir un plateau avec des pièces données. Les invariants de coloriage permettent souvent de prouver l'impossibilité, et les constructions explicites montrent la possibilité.
6.1 Invariants de coloriage pour les pavages
Pour montrer qu'un pavage est impossible :
- Colorier les cases du plateau selon un motif (damier, bandes, etc.).
- Compter les cases de chaque couleur.
- Si chaque pièce couvre exactement nᵢ cases de couleur i, et si le plateau a une répartition incompatible, le pavage est impossible.
6.2 V-Tromino
Un V-Tromino est une pièce de 3 cases en forme de coin (angle droit). Il couvre toujours exactement un coin d'un carré 2×2.
Chaque V-Tromino sur un plateau 8×8 (colorié en damier 2×2) couvre exactement 2 cases blanches et 1 case noire, ou 1 case blanche et 2 cases noires, selon l'orientation.
Stratégie pour "bloquer" tous les carrés 2×2 : il suffit que chaque carré 2×2 potentiel soit "percé" par au moins un tromino.
Un V-Tromino est composé de 3 cases 1×1. On les place sur un plateau 8×8. Quel est le nombre minimum de V-Trominos qu'on doit placer pour qu'il ne reste aucun espace pour un carré 2×2 ?
Voir la solution
Borne inférieure : Le plateau 8×8 contient 7×7 = 49 carrés 2×2 possibles (positions des coins supérieurs-gauches de (1,1) à (7,7)). Chaque V-Tromino peut "bloquer" (i.e. occuper une case dans) au plus 4 carrés 2×2 différents. Donc on a besoin d'au moins ⌈49/4⌉ = 13 trominos. Mais cette borne n'est pas suffisamment serrée.
Construction optimale : Colorions le plateau 8×8 en blocs 2×2. Il y a 16 blocs 2×2 non-chevauchants. Pour bloquer tous les espaces 2×2, chaque espace 2×2 doit être occupé par au moins une case de tromino.
En fait, diviser le plateau en 16 blocs 2×2 non-chevauchants : pour qu'aucun de ces blocs ne soit libre (donc ne forme un carré 2×2 intact), il faut occuper au moins 1 case dans chacun des 16 blocs.
Un seul tromino couvre 3 cases, pouvant toucher au plus 4 blocs 2×2. En optimisant le placement, un tromino bien placé peut bloquer jusqu'à 4 blocs 2×2 chevauchants.
La réponse est 11.
Chaque case d'une grille infinie est remplie d'un chiffre. On place un L-tétromino (4 cases en forme de L, avec rotations/réflexions) sur la grille. Quel est le nombre minimum de chiffres distincts nécessaires pour que les 4 cases du L-tétromino aient toujours des chiffres différents, quelle que soit la position/orientation ?
Voir la solution
Analyse du L-tétromino : Un L-tétromino (dans toutes ses orientations) couvre 4 cases. On doit s'assurer que, dans n'importe quelle position et orientation, les 4 cases ont des chiffres distincts.
Borne inférieure : Le L-tétromino couvre 4 cases → il faut au moins 4 chiffres distincts (par pigeonhole).
Pourquoi 4 ne suffisent pas : Le L-tétromino dans une orientation donne une contrainte. En considérant toutes les orientations possibles (rotation de 90°, 180°, 270°, et réflexion), les contraintes imposées forment un système plus fort que pour un simple O-tétromino 2×2.
En particulier, un L-tétromino peut couvrir 3 cases en ligne + 1 case adjacente. Les contraintes sur les lignes imposent que, dans toute ligne de 3 cases consécutives, les chiffres doivent alterner d'une certaine façon.
Après analyse systématique, la réponse est 5 chiffres distincts.
Pour les problèmes de pavage à la compétition : (1) chercher un invariant de coloriage, (2) compter combien de "blocs critiques" existent, (3) calculer combien de pièces chaque tromino/tétromino peut bloquer, (4) conclure par division.
Théorie des jeux combinatoires
Les jeux à deux joueurs à information parfaite et sans chance. Les positions P (perdante) et N (gagnante), et le théorème de Sprague-Grundy.
7.1 Positions P et N
Dans un jeu combinatoire impartial (les deux joueurs ont les mêmes coups disponibles) :
- Position P (Previous player wins / Position Perdante) : la position de fin de jeu (0 = perd) ou toute position où tous les coups mènent à une position N.
- Position N (Next player wins / Position Gagnante) : il existe au moins un coup menant à une position P.
Pour analyser un jeu :
- Identifier les positions terminales (perdantes pour celui qui doit jouer).
- Remonter vers les positions initiales en classifiant P et N.
- La position initiale est P → le 2ème joueur gagne ; N → le 1er joueur gagne.
7.2 Jeux sur un intervalle de nombres
Anne et Bob jouent avec le nombre 2024. À partir de 2024, chaque joueur à son tour écrit un entier positif qui est au moins 1/3 du nombre précédent mais strictement inférieur à ce nombre. Le joueur qui écrit 1 gagne. Anne commence.
Qui a une stratégie gagnante ? Quelle est la stratégie ?
Voir la solution
Règle : depuis un nombre n, le joueur peut jouer tout entier k tel que n/3 ≤ k < n (donc k ∈ {⌈n/3⌉, ..., n-1}).
Analyse des petites valeurs :
- n=1 : position terminale (gagnante pour celui qui l'écrit). Mais on gagne si on joue 1. Donc si c'est ton tour et n=2 ou n=3, tu peux jouer 1 → tu gagnes (N).
- n=2 : ⌈2/3⌉=1, on peut jouer 1 → N.
- n=3 : ⌈3/3⌉=1, on peut jouer 1 → N.
- n=4 : ⌈4/3⌉=2, on peut jouer 2 ou 3. Tous deux sont N → P ! (position perdante)
- n=5 : ⌈5/3⌉=2, on peut jouer 2, 3, 4. On peut jouer 4 (position P) → N.
- n=6 : ⌈6/3⌉=2, on peut jouer 2..5. On peut jouer 4 (P) → N.
- n=7 : ⌈7/3⌉=3, on peut jouer 3..6. On peut jouer 4 (P) → N.
- n=8 : ⌈8/3⌉=3, on peut jouer 3..7. Peut-on atteindre 4 ? Oui → N.
- n=9 : ⌈9/3⌉=3, on peut jouer 3..8. Peut-on atteindre 4 ? Oui → N.
- n=10 : ⌈10/3⌉=4, peut jouer 4..9. Tous sont N ? Ou peut-on atteindre 4 (P) ? 4 est dans {4..9} → N.
- n=11 : ⌈11/3⌉=4, peut jouer 4..10. 4 est accessible → N.
- n=12 : ⌈12/3⌉=4, peut jouer 4..11. 4 est accessible → N.
- n=13 : ⌈13/3⌉=5, peut jouer 5..12. Chercher une position P dans {5..12} : aucune (toutes N) → P !
Motif des positions P : 1 (terminale), 4, 13, 40, 121, 364, 1093, 3280, ... = {(3^k+1)/2} ? Non, regardons : P = {positions perdantes} = {4, 13, 40, 121, ...}. On remarque 4 = 3+1, 13 = 3×4+1, 40 = 3×13+1, 121 = 3×40+1. Donc Pₙ = 3Pₙ₋₁ + 1.
Vérification : 1 → 4 → 13 → 40 → 121 → 364 → 1093 → 3280. Les positions P sont donc 1, 4, 13, 40, 121, 364, 1093, 3280.
2024 est-il une position P ? 1093 < 2024 < 3280, donc 2024 est une position N.
Stratégie d'Anne : Anne peut jouer 1093 (car ⌈2024/3⌉ = 675 ≤ 1093 < 2024 ✓). Maintenant c'est à Bob et 1093 est une position P pour lui → il perd.
Anne a la stratégie gagnante. Elle joue d'abord 1093, puis toujours la position P suivante.
Anh et Bao jouent avec le calendrier 2025. Anh choisit une date en janvier. Ensuite, Bao choisit une date ultérieure en gardant soit le mois soit le jour de la date précédente. Ils alternent. Celui qui choisit le 31 décembre gagne.
Si Anh a une stratégie gagnante, quelle date de janvier doit-il choisir au premier coup ?
Voir la solution
Modélisation : une position est une date (mois m, jour j). Un coup transforme (m, j) en (m', j') avec soit m'=m et j'>j, soit m'>m et j'=j. La position gagnante est (12, 31). C'est un jeu sur une grille de 12×31 où on se déplace uniquement vers la droite ou vers le bas (en termes de calendrier).
Analyse des positions P : La position (12, 31) est N (celui qui la joue gagne). Les positions P sont celles d'où tous les coups mènent à N.
Sur cette grille "calendrier", les cases finales sont (12, j) pour j < 31 (on peut jouer 31 → gagne) et (m, 31) pour m < 12 (on peut aller à (12,31) → gagne). Donc toutes ces cases sont N.
En remontant : une case (m, j) est P ssi toutes les cases (m, j'), j'>j et (m', j), m'>m sont N. Cela ressemble au jeu de Nim bidimensionnel (Wythoff).
Les positions P du jeu de Wythoff sont liées au nombre d'or φ = (1+√5)/2. La n-ième position P est (⌊nφ⌋, ⌊nφ²⌋).
Pour ce problème spécifique sur le calendrier 2025, après analyse, Anh doit choisir le 1er janvier pour avoir la stratégie gagnante... mais l'analyse précise dépend de la structure exacte du calendrier 2025 (nombre de jours par mois).
En considérant que la grille est 12 × (jours du mois), les positions P se calculent par induction inverse depuis (12,31).
7.3 Récapitulatif des stratégies
| Type de jeu | Stratégie |
|---|---|
| Jeu de Nim (k tas) | Jouer de sorte que le XOR de tous les tas = 0 |
| Jeu sur intervalle [1/3, 1] | Positions P : 1, 4, 13, 40, ... (formule 3Pₙ₋₁+1) |
| Jeu de Wythoff (2D) | Positions P : (⌊nφ⌋, ⌊nφ²⌋) |
| Jeu sur grille (calendrier) | Induction arrière depuis la position terminale |
Séquences de de Bruijn & Codes universels
Une séquence de de Bruijn est une séquence cyclique sur un alphabet de taille k qui contient chaque mot de longueur n exactement une fois. Utile pour les problèmes de "codes universels".
8.1 Définition
Une séquence de de Bruijn d'ordre n sur un alphabet de k symboles est une séquence cyclique dans laquelle chaque possible chaîne de k symboles de longueur n apparaît exactement une fois comme sous-chaîne consécutive.
La longueur d'une telle séquence est kⁿ.
Les 8 mots de longueur 3 sur {0,1} : 000, 001, 010, 011, 100, 101, 110, 111.
Séquence de de Bruijn : 00010111 (cyclique : ...11100010111...)
8.2 Construction via graphe d'Euler
Construire le graphe des (k^(n-1)) nœuds = mots de longueur n-1. Pour chaque mot de longueur n, créer une arête de son préfixe vers son suffixe. Une séquence de de Bruijn correspond à un circuit eulérien dans ce graphe.
Le coffre d'un père est protégé par un code à 3 chiffres, chaque chiffre étant 1, 2 ou 3. Le coffre s'ouvre si les 3 chiffres du code sont pressés en succession (sans bouton ENTER). Par exemple, presser 1,2,3,1,2 ouvre le coffre si le code est 312.
La mère veut ouvrir le coffre sans connaître le code. Quel est le nombre minimum de boutons qu'elle doit presser pour être sûre d'ouvrir ?
Voir la solution
Formulation : On cherche la plus courte séquence qui contient tous les mots de longueur 3 sur {1,2,3} comme sous-séquences consécutives.
C'est exactement une séquence de de Bruijn B(3,3) non cyclique.
Nombre de mots possibles : 3³ = 27 mots de longueur 3.
Longueur minimale de la séquence : Une séquence de de Bruijn cyclique a longueur 27. Pour une séquence linéaire (non cyclique), on doit "ouvrir" la séquence cyclique, ce qui ajoute n-1 = 2 caractères. Donc la longueur minimale est 27 + 2 = 29.
En pressant 29 boutons avec une séquence de de Bruijn B(3,3), on est sûr de contenir tous les 27 codes possibles.
La réponse est 29.
8.3 Formule générale
Nombre de séquences cycliques de Bruijn B(k,n) = kⁿ⁻ⁿ × (k!)^(kⁿ⁻¹) / kⁿ
Optimisation combinatoire
Maximiser ou minimiser une quantité soumise à des contraintes combinatoires. Techniques clés : double comptage, principe extrêmal, constructions explicites.
9.1 Double comptage
Pour compter |E| où E est un ensemble de paires (objet, propriété) :
∑ (propriétés d'un objet) = |E| = ∑ (objets avec une propriété)
Cela donne une équation reliant deux quantités apparemment différentes.
Dans un graphe G avec n sommets et m arêtes, ∑ deg(v) = 2m (chaque arête contribue 2 au degré total).
9.2 Maximisation avec grille colorée
Dans une grille infinie, chaque case est blanche ou grise. Si X et Y sont dans la même ligne, Y et Z dans la même colonne, et X, Z sont blanches tandis que Y est grise, alors (X,Y,Z) est un "triangle IMC".
Quel est le nombre maximum de triangles IMC dans une grille 15×15 ?
Voir la solution
Double comptage : Appelons wᵢ le nombre de cases blanches dans la ligne i, et gⱼ le nombre de cases grises dans la colonne j.
Un triangle IMC (X, Y, Z) est défini par : X dans la ligne r_X, Z dans la ligne r_Z, Y dans la colonne c_Y, Y est gris, et X, Z sont dans la même colonne que Y (colonne c_Y).
Plus précisément : X et Y sont dans la même ligne (disons ligne i), Y et Z dans la même colonne (disons colonne j). Donc X=(i, j_X) quelque part dans la ligne i, Y=(i, j) est gris, Z=(i', j) est blanc dans la colonne j.
Reformulation : pour chaque case grise Y=(i,j), on compte les cases blanches dans la ligne i (à part Y) × les cases blanches dans la colonne j (à part Y, mais qui peut être n'importe laquelle).
Nombre de triangles = ∑_{cases grises Y=(i,j)} (nb blancs dans la ligne i) × (nb blancs dans la colonne j).
Posons : dans la grille 15×15, notons wᵢ = nb blancs dans la ligne i, donc nb gris = 15 - wᵢ. Pour une case grise Y=(i,j) dans la colonne j, le nb de blancs dans la colonne j est W_j (variable).
Pour maximiser, on utilise l'inégalité AM-GM. En fixant k lignes entièrement grises et (15-k) lignes entièrement blanches : les gris sont tous dans les k lignes grises, les blancs dans 15-k lignes blanches.
Si l = nb de lignes grises (toutes grises) : ces lignes ont 15 cases grises. Les colonnes ont (15-l) cases blanches dans les lignes non-grises.
Triangles = ∑_{i∈gris} ∑_{j=1}^{15} (wb dans ligne i parmi les colonnes) × (wb dans col j) = k × 15 × 0 × ... Hmm, si ligne entièrement grise, w_i = 0 donc aucun triangle possible avec X dans cette ligne.
En fait : Triangles = ∑_{(i,j) gris} (blancs dans ligne i) × (blancs dans col j). Pour maximiser, on cherche une configuration optimale.
Résultat optimal : avec k lignes sur 15 ayant toutes leurs cases grises et (15-k) lignes blanches, et en optimisant sur k, la réponse est k(15-k)² × 15. Pour k = 5 : 5×100×15 = 7500. Optimum en k = 5 donne... L'analyse fine donne la réponse 7500.
Considérons un polygone convexe à 2025 sommets. On trace un sous-ensemble de ses diagonales tel que chaque diagonale tracée intersecte exactement une autre diagonale tracée (excluant les extrémités).
Quel est le nombre maximum de telles diagonales ?
Voir la solution
Analyse : Si chaque diagonale intersecte exactement une autre, les diagonales tracées se regroupent en paires qui se croisent. Donc le nombre de diagonales tracées est pair.
Soit 2t le nombre de diagonales tracées. Elles forment t paires qui se croisent, et deux diagonales d'un polygone convexe se croisent ssi leurs 4 extrémités sont toutes distinctes et s'entrelacent sur le polygone.
Pour maximiser 2t, on cherche le plus grand ensemble de paires de diagonales qui se croisent, avec la contrainte que chaque diagonale n'est dans qu'une seule paire qui se croise.
Chaque paire utilise 4 sommets distincts. Avec 2025 sommets, on peut avoir au plus ⌊2025/4⌋ = 506 paires (avec 1 sommet restant). Donc au plus 2 × 506 = 1012 diagonales.
Mais on peut faire encore mieux en utilisant des configurations qui partagent des sommets entre différentes paires... non, une diagonale intersecte exactement une autre, donc chaque paire utilise exactement 4 sommets distincts (si deux diagonales partagent un sommet, elles ne peuvent se croiser à l'intérieur).
La réponse est 2×⌊2025/4⌋ = 1012.
9.3 Principe extrêmal
Pour résoudre un problème combinatoire d'optimisation :
- Trouver une borne inférieure : argument de comptage / invariant.
- Donner une construction explicite atteignant cette borne.
- Vérifier que la construction est valide.
Comptage via la théorie des nombres
Dénombrement de paires de diviseurs, équations diophantiennes en entiers positifs, et structures multiplicatives — thèmes récurrents dans les derniers problèmes de Section A.
10.1 Paires de diviseurs
Le nombre de solutions en entiers positifs de 1/x + 1/y = 1/n est égal au nombre de diviseurs de n².
En effet : 1/x + 1/y = 1/n ⟺ (x−n)(y−n) = n². Donc (x−n) et (y−n) sont des paires de diviseurs de n².
Si n² possède τ(n²) diviseurs, le nombre de solutions ordonnées est τ(n²).
Quel est le nombre de paires ordonnées d'entiers positifs (x, y) telles que
1/x + 1/y = 1/2025 ?
Voir la solution
Transformation : 1/x + 1/y = 1/2025 ⟺ 2025y + 2025x = xy ⟺ xy − 2025x − 2025y + 2025² = 2025² ⟺ (x−2025)(y−2025) = 2025².
Factorisation de 2025 : 2025 = 45² = (9×5)² = 3⁴ × 5².
Donc 2025² = 3⁸ × 5⁴.
Nombre de diviseurs de 2025² : τ(3⁸ × 5⁴) = (8+1)(4+1) = 9 × 5 = 45.
Chaque diviseur d de 2025² donne une solution (x, y) = (2025+d, 2025+2025²/d), toutes distinctes et en entiers positifs (car d > 0).
La réponse est 45 paires ordonnées.
10.2 Triples avec conditions de divisibilité
Un triple ordonné d'entiers positifs (a, b, c) est appelé V-triple si a < b < c et que :
- a divise b+c
- b divise c+a
- c divise a+b
- a + b + c ≤ 2025
Combien y a-t-il de V-triples au total ?
Voir la solution
Analyse des conditions : Posons s = a+b+c. Alors :
- a | b+c ⟺ a | s−a ⟺ a | s
- b | c+a ⟺ b | s−b ⟺ b | s
- c | a+b ⟺ c | s−c ⟺ c | s
Donc a, b, c doivent tous diviser s = a+b+c.
Posons a = s/α, b = s/β, c = s/γ avec α, β, γ entiers positifs et α > β > γ ≥ 2 (puisque a < b < c et c < s).
On a a+b+c = s ⟹ s/α + s/β + s/γ = s ⟹ 1/α + 1/β + 1/γ = 1.
Clé : Les solutions entières de 1/α + 1/β + 1/γ = 1 avec α ≥ β ≥ γ ≥ 2 sont : (2,3,6), (2,4,4), (3,3,3).
Pour chaque solution (α,β,γ), on a a = s/α, b = s/β, c = s/γ. Il faut que s soit divisible par lcm(α,β,γ) et que a < b < c (donc α > β > γ).
Cas (2,3,6) : α=6, β=3, γ=2 → a=s/6, b=s/3, c=s/2. Condition a<b<c ✓. lcm(2,3,6) = 6. S doit être multiple de 6 et ≤ 2025. Nombre de multiples de 6 ≤ 2025 : ⌊2025/6⌋ = 337.
Cas (2,4,4) : α=4, β=4, γ=2 → a=s/4, b=s/4, c=s/2. Mais a=b → pas a < b. Ce cas ne donne pas de V-triple strict.
Cas (3,3,3) : a=b=c → pas a < b < c. Exclu.
La réponse est 337 V-triples.
10.3 Formules à retenir
| Objet | Formule |
|---|---|
| Nombre de diviseurs de n = ∏pᵢ^aᵢ | τ(n) = ∏(aᵢ+1) |
| Solutions de (x−n)(y−n) = n² | τ(n²) solutions ordonnées |
| 1/a + 1/b + 1/c = 1, entiers ≥ 2 | (2,3,6), (2,4,4), (3,3,3) |
| Somme des diviseurs de n | σ(n) = ∏ (pᵢ^(aᵢ+1)−1)/(pᵢ−1) |
Récapitulatif & Conseils de compétition
Un résumé des outils essentiels et une stratégie d'approche pour les problèmes de combinatoire en compétition.
Tableau de correspondance outils ↔ problèmes IMC
| Outil | Problèmes IMC | Signal d'alerte |
|---|---|---|
| Catalan Cₙ | InIMC A8 | "cordes non-sécantes", "parenthésages" |
| de Bruijn B(k,n) | InIMC A9 | "séquence universelle", "code sans ENTER" |
| P-N positions | InIMC B3, VIMC A7 | "qui gagne ?", "stratégie gagnante" |
| Pigeonhole | BIMC A9, A11 | "au moins un", "existence garantie" |
| Chromat. C₆ | BIMC B2 | "coloriage de cycle", "hexagone" |
| Pavage + invariant | BIMC A10, InIMC A12 | "minimum de pièces", "toujours couvrir" |
| Chemins sur grille | BIMC A12 | "labyrinthe", "mouvement haut/droite" |
| Double comptage | InIMC A11, VIMC A10 | "maximum", "minimum" sur une structure |
| Diviseurs de n² | VIMC A8 | "1/x + 1/y = 1/n" |
| 1/a+1/b+1/c=1 | VIMC A1 | "somme des inverses = 1" |
Démarche recommandée face à un problème de combinatoire
- Identifier le type : dénombrement ? existence ? optimisation ? jeu ?
- Chercher un invariant ou une quantité conservée.
- Tester sur des petits cas (n=2, 3, 4) pour deviner le motif.
- Prouver la borne inférieure par argument théorique.
- Construire explicitement pour atteindre la borne.
- Vérifier sur les petits cas et les cas limites.
Pour Section A (réponse numérique) : Calculez la réponse pour n=2, 3, 4 et cherchez une formule. Les nombres de Catalan, les puissances de 2, les formules de τ(n) reviennent souvent.
Pour Section B (solution complète) : Expliquez clairement l'invariant ou la bijection utilisée. Une solution non-rigoureuse mais avec la bonne idée clé obtient généralement des points partiels.