Si un ordinateur vérifie une propriété pour des milliards de nombres, est-elle pour autant démontrée ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

En NSI, j'ai programmé une vérification de la conjecture de Syracuse jusqu'à un million, et tout fonctionnait. J'ai été tenté de conclure qu'elle était vraie. Mon professeur de mathématiques m'a alors montré des propriétés vraies pour des millions de nombres, puis fausses. J'ai voulu comprendre la différence entre vérifier et démontrer, et ce que l'ordinateur peut vraiment apporter.

L'enjeu et les notions du programme

Distinguer exemple, contre-exemple et démonstration, et mesurer ce qu'un calcul sur ordinateur prouve ou ne prouve pas.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   Un ordinateur peut tester une propriété sur des milliards de cas en quelques minutes. Problématique : un grand nombre de vérifications suffit-il à affirmer qu'une propriété est vraie pour tous les entiers ?

2. 2. Mathématiques : des contre-exemples tardifs

   4 min

   Euler a remarqué que $n^2+n+41$n²+n+41 est premier pour $n=0,1,\dots ,39$n=0,1,…,39 : 41, 43, 47, 53… Mais pour $n=40$n=40 : $40^2+40+41=40\times 41+41=41\times 41=1681$40²+40+41=40×41+41=41×41=1 681. La factorisation se voit directement : le contre-exemple n'est pas un hasard.

   Conjecture de Pólya (1919) : parmi les entiers de 2 à $N$N, au moins la moitié ont un nombre impair de facteurs premiers. Vraie pour tous les $N$N testés pendant des décennies, elle est fausse pour $N=906150257$N=906 150 257, trouvé par ordinateur en 1980.

   Conjecture d'Euler : il faudrait au moins $k$k puissances $k$k-ièmes pour obtenir une puissance $k$k-ième. En 1966, un ordinateur trouve $27^5+84^5+110^5+133^5=144^5$27⁵+84⁵+110⁵+133⁵=144⁵ : quatre puissances cinquièmes suffisent.

   Logique : « pour tout $n$n, $P(n)$P(n) » ne se démontre jamais par des exemples, si nombreux soient-ils ; un seul contre-exemple suffit à le réfuter.

3. 3. NSI : le rôle réel de l'ordinateur

   3 min

   L'ordinateur est très efficace pour trouver des contre-exemples et pour suggérer des conjectures. La conjecture de Syracuse a été vérifiée jusqu'à plus de $2^{68}$2⁶⁸, ce qui rend un contre-exemple improbable mais ne prouve rien.

   Il peut aussi participer à une démonstration quand le problème se ramène à un nombre fini de cas : le théorème des quatre couleurs (1976) ou la valeur de $BB(5)$BB(5) (2024). On fait alors vérifier le programme lui-même par des assistants de preuve, pour s'assurer qu'il ne contient pas d'erreur.

4. 4. Conclusion

   1,5 min

   Des milliards de vérifications ne démontrent pas une propriété sur une infinité d'entiers : $n^2+n+41$n²+n+41, Pólya et Euler en sont la preuve. L'ordinateur trouve des contre-exemples et vérifie des cas finis ; la démonstration reste nécessaire pour l'infini. J'ouvre sur la conjecture de Goldbach, vérifiée jusqu'à $4\times 10^{18}$4×10¹⁸ et toujours non démontrée.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Confondre un grand nombre d'exemples avec une démonstration.
• Croire qu'un contre-exemple très grand est sans importance.
• Oublier qu'un programme de vérification peut lui-même être faux.

Revoir les notions

• Nombres et calculs (Seconde) →
• Suites : récurrence et limites (Terminale spé maths) →

Autres questions : logique et calculabilité

• Peut-on écrire un programme qui détecte tous les programmes qui tournent en boucle infinie ?
• Existe-t-il des nombres qu'aucun programme ne pourra jamais calculer ?
• Combien de fonctions logiques différentes peut-on construire avec n entrées, et peut-on toutes les réaliser avec ET, OU, NON ?
• Pourquoi « non (a et b) » ne veut-il pas dire « non a et non b », et pourquoi cette erreur cause-t-elle tant de bugs ?

Toutes les questions maths-nsi →