Mathématiques discrètes, algorithmique

On attribue au physicien Ernest Rutherford (1871-1937) la citation « All science is either physics or stamp collecting ». Malgré son caractère provocateur et caricatural, cette citation résume assez bien l’architectonique des sciences jusqu’à la fin du XXe siècle : la physique règne, une grande partie des mathématiques est motivée par ses applications à la physique, la biologie décrit et classe les espèces, les humanités ne sont pas encore les sciences humaines et la technique n’est qu’une application de la science.

Voici un texte qui nous a été envoyé par un de nos jeunes lecteurs, Thibault Bourgeron, actuellement en classe de terminale S au lycée Sainte-Marie d'Antony ! Ce travail traite de deux problèmes à résoudre par récurrence.

Les suites de Fibonacci, le nombre de parenthésages “légaux” possibles avec 2n parenthèses, le profil des montagnes... Ces sujets on un rapport, dans le monde des mathématiques ! Il existe en effet une manière assez générale d'étudier des suites dont la définition fait apparaître (clairement ou après analyse), des phénomènes de récurrence. Il s'agit d'introduire une série formelle associée à cette suite. Le but de ce texte est d'introduire cette notion qui généralise celle de polynôme en autorisant les degrés infinis.

Il est ici question d'un théorème peu connu de G. Polyà, résultat qui fournit une méthode systématique pour dénombrer les coloriages possibles d'un ensemble sous l'action d'un groupe. De tels problèmes peuvent être posés de façon extrêmement simple : par exemple, combien peut-on faire de colliers différents si l'on dispose de 10 perles noires et de 3 perles rouges ?

Comment gagner à coup sûr au jeu de Nim ? Peut-on gagner à coup sûr aux échecs ? Ou bien est-ce qu'au contraire deux ordinateurs infiniment puissants jouant l'un contre l'autre aboutiraient nécessairement à une partie nulle ? Toutes ces questions tournent autour de la notion de stratégie, le jeu de Nim comme le jeu d'échecs étant des jeux à deux joueurs, finis.

Si l'on prends six personnes au hasard, alors trois d'entre elles se connaissent, ou alors on peut en trouver trois dont aucune ne se connaissent. Cette remarque, en apparence anodine, permet de déboucher sur toute une théorie combinatoire. En effet, reformulée en termes de graphe, cela signifie que, si l'on colorie les arêtes du graphe complet à six sommet en deux couleurs, alors on peut trouver un triangle dont les trois arêtes sont de la même couleur. La question se pose alors pour d'autres type de configurations, et l'on verra que le résultat reste valable à condition de colorier les arêtes d'un graphe suffisamment gros.

Le "Berlekamp's switching game'' est un jeu inventé par Elwin R. Berlekamp et David Gale. Son support est un tableau carré de m*m ampoules, contrôlées par 2m interrupteurs frontaux, un pour chaque ligne ou colonne. Quand un interrupteur est basculé, les ampoules qui étaient allumées dans la ligne ou la colonne correspondante sont éteintes, et celles qui étaient éteintes sont allumées. Le jeu consiste à trouver, pour un état initial donné, le nombre minimal d'ampoules allumées après manipulation à volonté des interrupteurs commandant les lignes et les colonnes, puis à maximiser ce nombre par un choix judicieux de l'état initial.

Un peu de théorie des graphes, où comment venir à bout d'un digicode plus vite que n'importe qui. Nous nous intéressons ici à la question de savoir combien de chiffres il faut taper successivement sur un digicode pour être sûr d'avoir tapé toutes les combinaisons possibles.

À quelle condition peut-on dessiner un graphe dans le plan, sans que ne se croisent des arêtes dudit graphe ? Le problème est assez classique : on connaît des condition nécessaires, qui dérivent de la formule d'Euler. Nous introduisons ici ces résultats, en montrant quelques applications sur des graphes particuliers.