Jeux finis et infinis Du même auteur Le Fascinant Nombre pi Pour la science, 1997 Jeux mathématiques et mathématiques des jeux Pour la science, 1998 Information, complexité et hasard Hermès science publications, 1999 Merveilleux nombres premiers : voyage au cœur de l'arithmétique Pour la science, 2000 L'Intelligence et le Calcul : de Godel aux ordinateurs quantiques Pour la science, 2002 L'Infini dans les sciences, l'art et la philosophie L'Harmattan, 2003 Les Inattendus mathématiques : art, casse-tête, paradoxes, superstitions Belin,2004 Le Hasard : une idée, un concept, un outil L'Harmattan, 2005 Complexités: aux limites des mathématiques et de l'informatique Pour la science, 2006 Au pays des paradoxes Pour la science, 2008 Complexité aléatoire et complexité organisée Quae, 2009 JEAN-PAUL DELAHAYE Jeux finis et infinis OUVRAGE PUBLIÉ AVEC LE CONCOURS DU CENTRE NATIONAL DU LIVRE ÉDITIONS DU SEUIL 2 7 rue Jacob, Paris VIe ISBN 978-2-02-096483-8 © Éditions du Seuil, janvier 2010 Le Code de la propriété intellectuelle interdit les copies ou reproductions destinées à une utilisation collective. Toute représentation ou reproduction intégrale ou partielle faite par quelque procédé que ce soit, sans le consentement de l'auteur ou de ses ayants cause, est illicite et constitue une contrefaçon sanctionnée par les articles L. 335-2 et suivants du Code de la propriété intellectuelle. www.editionsduseuil.fr Introduction Deux préjugés s'opposent et se contredisent. Celui du mathé maticien, qui aime dire que les mathématiques commencent avec l'infini et qui sous-entend plus ou moins que ce qui est fini est toujours un peu trop facile. Celui du sens commun, qui considère en revanche que l'infini est impossible à maîtriser et que nous, pauvres humains, nous ne pouvons donc pas nous amuser à des jeux infinis. Les deux sont dans l'erreur. Les mathématiques du fini sont aussi difficiles et profondes que celles de l'infini, bien qu'elles aient l'avantage quand on les pratique de fournir la certitude qu'on n'est pas en train de rêver et de se raconter des histoires ... Quant au préjugé du sens commun, il se trompe aussi, car les jeux avec l'infini sont possibles et nombreux; tout le monde peut les comprendre et s'en amuser. L'infini pour celui qui aime jouer n'est pas une abstraction à fuir; d'ailleurs, les jeux finis s'appuient eux-mêmes souvent sur un infini caché (par exemple, celui de l'ensemble de leurs configurations) et finalement jouer, c'est toujours apprivoiser de l'infini. Le but de ce livre composé autour des thèmes mathéma tiques variés se trouve justement là : vous persuader que le fini est aussi inépuisable et subtil que l'infini dont la compréhension n'est pas réservée aux puissances divines. L'un comme l'autre se retrouvent dans toutes sortes de divertissements combina toires et graphiques. Le fini et l'infini s'associent délicatement et s'entremêlent miraculeusement, leur dialogue ininterrompu 5 INTRODUCTION affine notre perception et rend le monde plus clair dans nos esprits qui cherchent à en découvrir les clefs. Le chapitre 1 traite d'un jeu localement fini qui se joue sur un damier infini que des passionnés depuis quarante ans étudient avec ferveur: le Jeu de la vie de John Conway. On y présente quelques-unes des constructions inouïes mises au point par les amateurs à coups de milliers d'heures de calculs d'ordinateurs et d'explorations patientes, minutieuses et parfois géniales. La phy sique abstraite et combinatoire qui se déploie dans cet univers planaire semble totalement invraisemblable. Elle nous apprend que la complexité est susceptible de naître de presque rien. Le chapitre 2 aborde les jeux finis et infinis que des méthodes d'analyse résolvent totalement en formulant des stratégies gagnantes pour l'un des joueurs. L'infini des ordinaux de Georg Cantor dans le cas des jeux infinis est crucial mais, loin d'être une abstraction inaccessible, il se montre ici concret et utile. Le chapitre 3 aborde un type de jeux que nous pratiquons tous chaque jour, entre nous, dans le monde social et écono mique. La question posée est celle de la rationalité de nos com portements. Cette rationalité supposée par les économistes et la théorie des jeux est finalement bien incertaine. C'est ce qu'éta blissent les expériences menées en laboratoire avec des sujets humains à qui on demande de participer à des jeux finis ... impliquant parfois un raisonnement infini. Le chapitre 4 montre qu'on peut jouer à des jeux d'une durée infinie et même y découvrir des méthodes assurant de gagner formulables ... en termes finis. Ces jeux à l'apparence anodine sont au cœur des réflexions sur l'infini des grands ensembles où ils sont les premiers pas de la résolution d'un problème posé il y a plus de cent ans par Cantor: l'hypothèse du continu. Le chapitre 5 est essentiellement ludique et, par le biais d'un jeu fini de transformations d'images, il tente de rendre visibles et évidentes quelques notions liées à la théorie des groupes et aux courbes de longueur. .. infinie. 6 JEUX FINIS ET INFINIS Le chapitre 6 s'intéresse aux pavages fins de la droite, du plan et de l'espace. Ce jeu-infini au possible-consiste à rem plir sans chevauchement ces ensembles géométriques continus à l'aide de morceaux identiques sans épaisseur. L'existence d'un pavage de l'espace par des cercles (de rayon non nul) est éton nante d'autant qu'on prouve aussi que le plan ne peut pas, lui, être pavé par des cercles. Le chapitre 7, finalement, propose un jeu d'imagination à propos de l'infini. Qu'est-ce que pourrait être un livre infini? Y en a-t-il de plusieurs types? Comment, avec nos moyens finis, les manipuler, les classer et les identifier? Là encore, le continu et le discret se mêlent et nous réservent de belles surprises. Les chapitres peuvent être lus indépendamment les uns des autres; souvent même, les encadrés ne demandent pas de s'être plongé dans le texte principal : piochez-en un au hasard et, s'il accroche votre curiosité, cherchez la première page du chapitre et. .. jouez*. * En notant par A les chapitres les plus faciles et parC ceux qui demandent le plus de concentration, les chapitres se classent de la manière suivante : chapitre lA; chapitre 2B ; chapitre 3A; chapitre 4C; chapitre SA; cha pitre 6B; chapitre 7A. j j j j j j j j j j j j j j j j j j j j j j j j j j j j j j j j j j j j j j j Chapitre 1 Quarante ans de Jeu de la vie Survivre, se déplacer et calculer RÉSUMÉ. Les automates cellulaires, dont le jeu de la vie est le plus remarquable exemple, poursuivent leur propre évolution sur un damier à cases carrées. La mécanique élémentaire qui détermine leurs mouvements est d'une grande simplicité, et pourtant, comprendre ce qu'ils font et les «programmer» est un art subtil. Depuis bientôt quarante ans, les passionnés de ce jeu localement fini qui se déroule sur un terrain infini y construisent des confi gurations aux propriétés fantastiques. Les drôles de machines des ingénieurs du Jeu de la vie Calculer, c'est observer, se souvenir et agir. Celui qui effectue une multiplication avec un papier et un crayon regarde les nombres qu'il doit multiplier, s'en souvient (au moins par tiellement à chaque étape du calcul), se remémore les tables de multiplication, et cela détermine le résultat qu'il pose sur le papier. Dans le cours de la multiplication, il doit aussi se souvenir de l'endroit précis où le calcul en est arrivé et s'il y a des retenues. Le mécanisme le plus élémentaire de calcul conçu par les mathématiciens est l'automate fini. L'automate fini procède lui aussi selon le principe : observer, se souvenir et agir. L'automate observe les autres automates autour de lui - on suppose que des automates identiques sont placés sur toutes les cases d'un damier infini -, se souvient de l'état dans lequel il se trouve 9