Chaque chapitre est constitué de points théoriques et d'exercices. Ces derniers ont pour but de vérifier que la théorie a bien été assimilée. Ils rapportent chacun entre 3 et 12 points, selon leur difficulté. Pour compléter un chapitre, il faut résoudre tous ses exercices.
Certains chapitres ont d'autres chapitres pour prérequis. Pour accéder aux exercices d'un tel chapitre, il est nécessaire de d'abord compléter ses chapitres prérequis.
La combinatoire étudie principalement les collections finies d'objets et peut prendre des formes très diverses. Ainsi, les problèmes de dénombrement, de pavages, ou encore de théorie des graphes sont considérés comme des problèmes de combinatoire. Nous donnons ici toute la théorie nécessaire concernant ces différents thèmes ainsi que des exemples illustrant les différentes méthodes de résolution de ces problèmes.
Les chapitres de cette section sont ordonnés selon leur importance (des plus primordiaux aux plus avancés).
Les chapitres suivants reprennent la théorie essentielle relative à cette section.
Principe des tiroirs |
|
Le principe des tiroirs est un principe important qui peut servir dans des contextes variés. Il est également appelé principe de Dirichlet ou pigeonhole principle en anglais. Ce principe, qui peut a priori sembler trivial, permet pourtant dans certains cas de résoudre des situations très complexes.
Statistiquesdepuis le 8 décembre 2014 Taux de réussite : 74% |
Dénombrement |
|
Bon nombre de problèmes de combinatoire consistent à dénombrer les façons d'effectuer une certaine tâche. On pourra ainsi se demander de combien de manières il est possible de placer des convives autour d'une table ou encore combien il existe de tirages différents au Lotto. Il existe pour ce faire plusieurs formules s'appliquant à différents cas. Nous présentons dans ce chapitre toutes les formules de permutations, combinaisons et arrangements, ainsi que des exemples d'utilisation de celles-ci.
Statistiquesdepuis le 8 décembre 2014 Taux de réussite : 37% |
Pavages |
|
Les problèmes de pavages constituent une classe de problèmes assez particulière. Ils consistent à paver une surface donnée à l'aide de certains pavés de forme donnée, et le tout est généralement de montrer qu'un tel pavage est impossible. Nous présentons ici les différentes méthodes permettant de résoudre ce type de problème.
Pour pouvoir accéder aux exercices de ce chapitre, vous devez d'abord compléter : Principe des tiroirs ExercicesStatistiquesdepuis le 8 décembre 2014 Taux de réussite : 69% |
Coefficients binomiaux |
|
Les coefficients binomiaux $C_n^k$ définis précédemment ont en fait de nombreuses propriétés, des plus basiques aux plus surprenantes. Il est important de bien connaître celles-ci puisque, en plus d'être divertissantes, elles permettent de simplifier des formules a priori compliquées obtenues lors d'un dénombrement. Le triangle de Pascal permet de représenter les différents coefficients binomiaux de sorte à mettre en évidence plusieurs de ces propriétés.
Pour pouvoir accéder aux exercices de ce chapitre, vous devez d'abord compléter : Dénombrement ExercicesStatistiquesdepuis le 8 décembre 2014 Taux de réussite : 92% |
Les chapitres suivants, un peu plus avancés, reprennent les résultats classiques de cette section.
Invariants et (mono)variants |
|
Bien que la notion d'invariant soit assez simple à comprendre, elle reste un outil très puissant pour résoudre des problèmes de combinatoire. De manière un peu plus générale, on peut également utiliser des monovariants ou des variants pour mieux comprendre certaines situations non évidentes.
ThéorieStatistiquesdepuis le 8 décembre 2014 Taux de réussite : 34% |
Théorie des graphes |
|
Nous présentons dans ce chapitre la notion de graphe et expliquons comment des graphes peuvent être cachés derrière des problèmes divers et variés. Nous donnons ensuite quelques résultats concernant les graphes eulériens et les graphes planaires. Enfin, nous voyons en quoi le coloriage des graphes peut s'avérer utile et énonçons un résultat fondamental dans ce sujet : le théorème de Ramsey.
Pour pouvoir accéder aux exercices de ce chapitre, vous devez d'abord compléter : Principe des tiroirs ExercicesStatistiquesdepuis le 8 décembre 2014 Taux de réussite : 56% |
Dénombrement (suite) |
|
Nous avons vu précédemment comment dénombrer des possibilités à l'aide des formules de permutations, combinaisons et arrangements. Il n'est pas toujours possible d'appliquer ces formules directement, et l'objectif de ce chapitre est de présenter différentes méthodes permettant de résoudre certaines situations plus complexes.
Pour pouvoir accéder aux exercices de ce chapitre, vous devez d'abord compléter : Coefficients binomiaux ExercicesStatistiquesdepuis le 8 décembre 2014 Taux de réussite : 58% |
Les chapitres suivants reprennent des notions plus rarement utiles en compétition mais qui peuvent devenir assez puissantes si bien maitrisées.
Double comptage |
|
Ce chapitre présente la méthode du double comptage, qui permet de démontrer des résultats théoriques comme la formule de Cayley mais qui se révèle surtout être un outil très puissant pour démontrer des problèmes de combinatoire de haut niveau.
Pour pouvoir accéder aux exercices de ce chapitre, vous devez d'abord compléter : Théorie des graphes - Dénombrement (suite) ExercicesStatistiquesdepuis le 28 février 2015 Taux de réussite : 88% |