Un graphe c'est simplement un ensemble de points, reliés entre eux. C'est une structure fondamentale des mathématiques et de l'informatique.

Voici quelques problèmes célèbres reliés aux graphes.

Question 1. Sujet n°1. Coloriage de cartes. [atelier]

Combien de couleurs faut-il (au minimum) pour colorier une carte sans que deux pays voisins n'aient la même couleur ?

• Faites divers exemples pour avoir une idée du nombre minimum de couleurs.
  Remarque: La réponse dans le cas général a été conjecturée en 1870 et prouvée en 1976 avec l'aide de l'ordinateur.

Question 2. Sujet n° 2. La promenade des amoureux (les 7 ponts de Königsberg). [atelier]

La ville russe de Königsberg (maintenant Kaliningrad) est traversée par la rivière Pregel. Il y a deux îles, qui sont reliés par 7 ponts. Les amoureux aimaient à se promener sur ses ponts. Un jour, on se posa la question suivante : peut-on faire une promenade qui passerait par tous les ponts, une fois et seule fois ?
On fit appel au plus grand mathématicien de l'époque, Euler, qui trouva la réponse (pour n'importe quel graphe!).

• A vous d'en faire de même !

Question 3. Des traits qui ne se coupent pas (les graphes planaires).

Des ingénieurs veulent relier les trois maisons suivantes à l'eau, au gaz et l'électricité sans que les canalisations ne se croisent.

• Pouvez-vous les aider ?

  MAISON 1 COMPTEUR EAU

   

  MAISON 2 COMPTEUR GAZ

   

  MAISON 3 COMPTEUR ELECTRICITE

Si c'est possible de le faire, alors les mathématiciens disent qu'un tel graphe est "planaire", c'est-à-dire : on peut le dessiner tous les liens dans le "plan" sans qu'ils ne se croisent.

• Essayez de trouver des exemples de graphes planaires et de graphes non planaires. Par exemple: ecrivez le nom des personnes de la classe et faites un lien entre deux personnes si elles habitent un village voisin.
  Arrivez-vous à mettre tous les liens sans les croiser ?
• Remarque : Le mathématicien polonais Kuratowski (1896-1980) a prouvé en 1930 que l'on pouvait caractériser les graphes planaires simplement en vérifiant un "petit détail". http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Kuratowski.htm
  Arriverez-vous à deviner son critère ?

Des articles plus récents (1974, 1980 et 2001) permettent de nos jours à l'ordinateur de montrer rapidement à l'humain si un graphe est planaire ou non.

• Voici pour finir un petit problème relié à la question des graphes planaires:
  Trois oies sont placées sur les cases 1, 2 et 3. Trois renards sont sur les cases 10, 11, 12.
  Échangez les oies contre les renards en suivant les lignes qui relient les cases.

  extrait de http://www.recreomath.qc.ca/dict_planaire_graphe.htm

Question 4: Le voyageur de commerce

Un représentant commercial a un certain nombre de villes à visiter, dans l'ordre qu'il veut, mais il veut minimiser ses frais d'essence et veut trouver le trajet le moins cher.

Comment doit-il faire ?

On dit parfois d'un problème que c'est la "quadrature du cercle", ce qui veut dire que le problème n'a pas de solution. Des gens plus savants (pédants!) parleraient de problème "déliaque", ici encore pour dire qu'il s'agit d'un problème impossible à résoudre.

Mais d'où viennent ces expressions ?

Des mathématiques bien sûr, et plus précisément, des questions de géométrie que se posaient les Grecs, il y a 2000 ans de cela !

Alors voici la question 1 : peut-on construire (à la règle et au compas) un carré qui a la même aire qu'un cercle ?

(C'est cela la "quadrature du cercle".)

Question 2. Les habitants de l'île de Délos souffraient de la peste. L'oracle de Delphe leur recommande de calmer la colère des dieux en doublant le volume de leur autel cubique, dédié à Apollon. De nombreuses tentatives furent des échecs et la peste redoublait. Alors, ils allèrent chercher les conseils de Platon. Platon ne trouva pas la solution (bien sûr) : il prétendait qu'Apollon n'avait pas besoin d'un nouvel autel, mais que cette demande signifiait plutôt qu'il fallait s'intéresser à la géométrie ! [Racontée par Philoponus, et rapportée par Ératosthène ou par Plutarque (50 et 125 av. J.-C.)].

• Comment ont-ils fait pour doubler le volume d'un cube ?
  (C'est cela un problème "déliaque").

Question 3. Comment partager un angle en trois ?

Question 4. Peut-on construire (toujours à la règle non graduée et au compas) un pentagone, un hexagone, un heptagone, un octogone, un nonagone, un dodécagone, un endécagone, un dodécagone, un tridecagone...

La réponse à ce problème a été trouvé par le "prince des mathématiciens", le génial Gauss.

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Gauss.html

Question 5. La diagonale du carré (avec des côtés de longueur 1) est a une certaine longueur. Cette longueur est-elle une fraction ?

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Pythagoras.html

Les Pythagoriciens (les disciples de Pythagore [569 av JC- 475 ac JC]) pensaient que tout était harmonie, tout était "rapport", tout était "fraction". On raconte que les Pythogoriciens tuèrent (en le poussant hors d'une barque) un de leur disciple, qui avait trahi un terrible secret. Saurez-vous retrouver ce secret ?

Sujet n°3 Les nombres premiers et les codes secrets.
Nb d'élèves : 1 (Ajayi GLUFOMI)

Les mathématiciens appellent nombre "premier" un nombre entier positif qui n'est divisible que par un et lui-même.

C'est une notion toute simple, mais qui fascine toujours, depuis plus de 2000 ans, les mathématiciens. La "théorie des nombres" a en fait été un moteur pour développer de nombreux autres pans des mathématiques (en algèbre, en analyse...), et a plus récemment elle a trouvé des applications surprenantes en informatique.

Voici le début de la liste des nombres premiers :

2, 3, 5, 7, 11, 13, 17, 19

Question 1. Continuer cette liste jusqu'à dépasser 50.

Question 2. Observez que tout nombre peut s'écrire d'une seule façon comme une multiplication de nombres premiers.

Question 3. Combien y a-t-il de nombres premiers ?
Remarque : C'est Euclide (-325, -265) qui a le premier répondu à cette question.
http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Euclid.html

Question 4. Trouvez une méthode pour lister les nombres premiers entre 1 et 1000.
Améliorez cette idée !
Remarque : c'est Erathostène (-274,-194) qui a le permier répondu à cette question.
[avec le "crible" d'Erathostène http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Eratosthenes.html ]

Question 5. Vous savez faire une multiplication, finalement assez rapidement. Si je vous demande 17 x 23, pas de problème ! Et si je vous demande 1131 x 2231, ca prendra un peu plus de temps, mais vous y arriverez aussi. Avec un ordinateur, on fait immédiatement des multiplications de milliers de chiffres !

En revanche, si je vous demande 35, c'est combien fois combien, vous réfléchissez un peu et vous dîtes 5 x 7. (On appelle cela "factoriser en produit de nombres premiers"). Pour 143, ce sera un plus long. Et pour 14545612171341123123, qui n'a que 20 chiffres, vous risquez d'y passer toute votre vie !

Même les plus puissants ordinateurs de nos jours doivent calculer pendant plusieurs semaines pour factoriser un nombre de 300 chiffres. Et pour mille chiffres, ca prendrait des siecles !

C'est sur ce principe d'opération facile dans un sens (la multiplication) et difficile dans l'autre (la factorisation) que sont basés les codes secrets de nos jours.

Factorisez 9889. réponse

Question 6. La théorie des codes secrets (la "cryptographie" = cachée+ écriture en grec) est un domaine actif, qui a des répercussions sur notre vie de tous les jours.

Trouvez des exemples où l'on utilise la cryptographie.

[Cartes bleues, mot de passe ordinateur, connexion internet pour achat, emails codés, cryptage canal + / satellite, communication portable, etc.]

Question 7. Essayer d'utiliser la factorisation en nombres premiers pour créer un code secret.

Anecdote 8: Trouvez des entiers qui vérifient x^2+y^2=z^2 (i.e. un triangle rectangle à côtés entiers).

C'est une question qui se trouve dans un livre de Diophante. En lisant ce livre, un grand mathématicien français, Fermat, avait écrit

"L'équation xⁿ+yⁿ=zⁿ n'a pas de solution pour n>2, mais la marge de ce livre est trop petite pour que j'écrive ma preuve".

Personne n'a ensuite retrouvé la preuve de Fermat, et on pense qu'il avait fait une erreur.

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Fermat.html

Tous les plus grands mathématiciens ont cherché à résoudre la "conjecture de Fermat" ; et ce n'est qu'en 1993, Andrew Wiles s'est rendu célèbre en annonçant avoir trouver une preuve que cette équation n'avait en effet jamais de solution. Mais... patratras ! Ca preuve était fausse.

Imaginez sa déception ! Il y avait un "trou" dans son raisonnement !

Heureusement, il s'est remis au travail, et a trouvé une preuve complète en1995.

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Wiles.html

Voilà, les mathématiques c'est aussi celà, beaucoup de tentatives, des fausses pistes, qui permettent aussi de mieux comprendre les choses. Et parfois, le succès ! Et alors, quel plaisir !