Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

La mathématique ouvre plus d’une fenêtre sur plus d’un monde Textes en question

La mathématique ouvre plus d’une fenêtre sur plus d’un monde Textes en questionsNouveau Le triangle le plus quelconque Autour de l’hypothèse du continu L’intégrale de Lebesgue en L1 Retournement du cuboctaèdre Mathématiques et grilles de sudoku Quadrature e a Qu d r a t Magazine de mathématiques pures et épicées La mathématique ouvre plus d’une fenêtre sur plus d’un monde n°73 Magazine trimestriel Juillet-Septembre 2009 8,50 euros ISSN 1142-2785 Quadrature n◦73 (2009) 43–48 c ⃝EDP Sciences, 2009 DOI: 10.1051/quadrature/2009014 [Jeux] Y a-t-il des mathématiques derrière les grilles de sudoku ?∗ par Jean-Baptiste Hiriart-Urruty∗∗ Résumé. Un sudoku, qu’es aquò ? Les élèves le savent bien, eux qui essaient, avant d’entrer en cours... ou pendant, de compléter ces grilles fournies par leurs journaux favoris... Mais, quels types de ma- thématiques ou d’informatique se cachent derrière ces grilles ? Les questions suivantes viennent naturellement à l’esprit du lycéen curieux : Combien y a-t-il de sudokus possibles ? Est-on sûr de pouvoir compléter une grille partiellement remplie d’une et d’une seule façon ? Un programme d’ordinateur pourrait-il résoudre à coup sûr tous les sudokus ? Comment font les journaux et ma- gazines pour se procurer ces jeux de sudoku ? Nous commentons ces questions et y apportons des réponses lorsque celles-ci sont connues. Notre texte comporte aussi une connotation historique car un des « ancêtres français » des jeux comme le sudoku fut Gaston Tarry. G. Tarry (1843–1913) fut un « amateur éclairé » des mathématiques, originaire de Villefranche- de-Rouergue en Aveyron. Il a contribué en Arithmétique, Combinatoire et Géométrie, répondant entre autres à une question mathématique laissée sans solution par L. Euler. Peu connu dans la communauté mathématique, quasiment inconnu dans la région Midi-Pyrénées, il se trouve que ses travaux ont une résonance très actuelle avec des jeux de grille populaires comme le sudoku. Nous évoquerons donc brièvement sa carrière et ses contributions scientiﬁques. Introduction Quand on interroge Internet pour avoir des in- formations sur des biographies de mathématiciens, comme cela nous arrive parfois, on tombe rapi- dement et systématiquement sur le site de l’uni- versité de St Andrews en Écosse. C’est un site complet, fort bien fait, qui oﬀre la possibilité de choi- sir des regroupements de biographies, par exemple par thèmes, par périodes, et aussi par régions du monde. Ainsi, en cliquant sur l’onglet « mathémati- ciens nés dans le grand Sud-Ouest de la France», voilà que nous sommes dirigés à Toulouse (avec Fermat), Saint-Aﬀrique (avec Borel), Dax (avec Borda)... et puis, surprise, à Villefranche-de-Panat en Aveyron avec le nom de Gaston Tarry. J’ai voulu en savoir plus sur ce personnage, et c’est ainsi que j’ai fait plus * Adapté d’un exposé à l’Académie des sciences, inscriptions et belles-lettres de Toulouse en octobre 2008. ** Institut de mathématiques, université Paul Sabatier de Toulouse. e-mail : jbhu@cict.fr ample connaissance avec ce « mathématicien éclairé » des mathématiques, dont le parcours et la manière de travailler m’ont fait penser à P. Fermat, avec un dé- calage de 250 ans. Certes, G. Tarry ne fait pas partie de ces mathématiciens qui ont laissé leur nom à d’im- portants résultats ou méthodes, mais, tout de même, il fait partie des contributeurs à ces « ancêtres de jeux de grilles » dont les échos actuels, et ô combien popu- laires, se manifestent quotidiennement, le sudoku par exemple. C’est à cette visite guidée dans un peu d’his- toire (régionale), un peu d’histoire des mathématiques (celle des jeux), que je vous convie ici. Première constatation : Gaston Tarry n’est pas né à Villefranche-de-Panat mais à Villefranche-de- Rouergue en 1843 ; nous l’avons vériﬁé auprès du service des archives de Villefranche-de-Rouergue (cf. Annexes). À la lecture de son acte de naissance, on apprend également que son père est secrétaire « d’une des mairies de Paris ». Cette erreur, ainsi que d’autres concernant des scientiﬁques de la région, a été signalée aux responsables du site de biographies Article published by EDP Sciences de l’université de St Andrews. Ensuite, quand on pose la question « qui était Tarry ? » à la com- munauté des mathématiciens professionnels (comme je l’ai fait à plusieurs reprises), peu connaissent son nom, à part quelques spécialistes de théorie des nombres (cf. [10]) ; et personne ne m’a signalé son origine aveyronnaise. Pourtant, en ouvrant des livres contemporains consacrés à la Combinatoire (par exemple [5]), le nom de Tarry apparaît dans des do- maines diﬀérents, parfois associé à des co-auteurs (cf. infra). Enﬁn, en écho aux préoccupations mathématiques de Tarry, nous parlerons de ce jeu de grilles qui fait fureur dans nos journaux depuis 2005, j’ai nommé le sudoku, jeu récent dans sa diﬀusion mais dont les ra- cines profondes remontent à il y a un siècle, en France précisément. Et on peut dire que Tarry contribua au soubassement mathématique de ces jeux que des au- teurs appellent « les ancêtres français du sudoku ». I Gaston Tarry Gaston Tarry est né à Villefranche-de-Rouergue le 27 septembre 1843, et mort au Havre le 21 juin 1913. C’est à l’occasion de ses études au lycée St Louis à Paris que Gaston Tarry devint intéressé par les mathématiques. Toutefois il n’envisagea jamais une carrière académique comme mathématicien, il joi- gnit plutôt les Contributions Diverses de l’Adminis- tration des Finances ; il ﬁt toute sa carrière en Algérie (l’Algérie était sous administration française depuis 1847) jusqu’à l’heure de sa retraite en 1902. Bien que mathématicien amateur, Tarry avait une étonnante capacité à analyser les problèmes combi- natoires ; notons que ses contributions mathématiques furent tardives, après qu’il eut franchi la cinquan- taine (comme quoi, tous les espoirs nous sont per- mis...). Nous commençons par l’un de ses plus cé- lèbres résultats, une réponse négative au dit problème des 36 oﬃciers de Euler. « Euler, le grand Euler... » disait déjà mon professeur de philosophie en classe de Math-Élém, cet immense scientiﬁque dont nous avons fêté en 2007 le 300e anniversaire de la nais- sance à Bâle. Quel était ce problème (posé par Euler en 1782) ? Imaginons des délégations de six régiments, cha- cune comprenant un colonel, un lieutenant-colonel, un major, un capitaine, un lieutenant et un sous- lieutenant ; il s’agit de disposer les 36 oﬃciers sui- vant six colonnes de six lignes, de manière que chaque colonne ou ligne comporte les six grades, mais provenant tous de régiments diﬀérents. Si, à la place des oﬃciers avec leur grade, vous mettez des nombres de 1 à 6 (mettons 1 pour colonel, 2 pour lieutenant-colonel, etc.), le problème posé est une sorte de sudoku à six éléments (cf. infra), mais plus contraint puisque des oﬃciers de même grade dans deux régiments diﬀérents ne sont pas interchan- geables (il est en eﬀet demandé que les six grades re- présentés dans chaque ligne ou colonne proviennent de régiments diﬀérents, un grade portant donc la cou- leur d’un régiment). Le problème fut posé par Euler en 1782 sous une forme générale, la réponse appor- tée ou conjecturée par lui (oui c’est possible, non ce n’est pas possible) dans beaucoup de conﬁgurations de n2 oﬃciers (n oﬃciers de grades diﬀérents pro- venant de n régiments diﬀérents), mais la question restait ouverte pour n = 6 (cf. Annexe). Dans deux travaux [17,18], Tarry résolut le problème en démon- trant l’impossibilité de l’arrangement demandé des 36 oﬃciers, par une recherche exhaustive des cas pos- sibles et par croisement des résultats. A. Sainte-Laguë ([12], pp. 211–225) replace le problème dans un cer- tain contexte historique, et rappelle la démonstration de Tarry. En fait, le problème est résolu complètement depuis 1960 (par Bose, Shrikhande et Parker) : il y a une solution audit problème des oﬃciers pour n’im- porte quel entier n, sauf pour n = 2 (ce qui était fa- cile à voir) et pour n = 6 (c’est le résultat de Tarry). À titre d’illustration, considérons la situation suivante, après tout nous exerçons à Toulouse au pays de Fermat mais aussi dans la capitale du rugby. On demande à 15 clubs de rugby (les 14 du championnat Top 14, plus le meilleur du championnat de Pro D2) de fournir cha- cun une équipe complète de 15 joueurs (un pour cha- cun des 15 postes de jeu), les joueurs étant habillés aux couleurs du club. Il s’agit à présent de disposer ces 225 joueurs sur une grille carrée de 15 × 15 cases de sorte que chaque ligne et chaque colonne (15 lignes et 15 colonnes) comporte une équipe complète de rugby dans laquelle les 15 clubs sont représentés. Ainsi, chaque joueur se retrouve dans deux équipes consti- tuées, l’équipe-colonne et l’équipe-ligne correspon- dant à sa position sur la grille ; il est le seul de son club dans chacune de ces deux équipes. D’après le ré- sultat général énoncé plus haut, il est tout à fait pos- sible de répartir les 225 joueurs sur la grille 15 × 15 de manière à respecter les contraintes imposées. Cher lecteur, sauriez-vous établir un tel dispositif ? De ma- nière assez étonnante, si on avait posé le même uploads/Geographie/ sudoku.pdf