Tout ce que vous avez toujours voulu savoir sur le théorème de Brouwer (sans jamais oser le demander)
11 septembre 2011 : la moitié de la Terre rend hommage aux attentats du 11 septembre 2001, pendant que l'autre moitié se passionne pour la coupe du monde de Rugby. Pour un blog bimensuel d'actu' comme le mien, c'est le moment où jamais de ne pas se planter dans le choix du sujet. Vais-je parler de la théorie du complot dans les mathématiques, ou profiter de l'homéomorphie entre les ballons de rugby et de football pour écrire un nouvel article de topologie...
Non. Aujourd'hui, je vais jouer la contre-programmation, en proposant un article consacré à la démonstration du théorème de Brouwer par le jeu de Hex ! Ha !
Le jeu de Hex
Le jeu de Hex, c'est un jeu de société qui se joue sur un plateau losange à cases hexagonales qui ressemble à ça :
Un plateau 11×11, mais on peut jouer au jeu de Hex sur un plateau plus grand ou plus petit
Chaque joueur pose à son tour un jeton de sa couleur (rouge ou bleu) sur l'une des cases ; l'objectif est de relier les côtés opposés du losange, ceux de sa couleur.
Vous voulez jouer ? Vous pouvez tester ici. Je vous préviens : même en commençant, le jeu n'est pas aisé...
Fait tout à fait intéressant : une partie de Hex ne se termine jamais par un match nul. Si le plateau est complètement rempli, il y a forcément un chemin connectant rouge ou un chemin connectant bleu (mais jamais les deux en même temps). C'est ce que l'on appelle le théorème de Hex.
Le théorème du jeu de Hex : sur un plateau plein, il existe au moins un chemin gagnant. (Ici, c'est le joueur rouge qui gagne).
Intuitivement, ce fait est évident : on peut imaginer qu'une case rouge est un hexagone de terre, et une case bleue est un hexagone d'eau. Dans ce cas là, soit les cases bleues forment une rivière et il est impossible de passer (le chemin connectant est le bleu), soit pas (le chemin connectant est rouge).
Comme souvent en topologie, ce qui est évident ne l'est plus à la démonstration (on peut penser au théorème de Jordan). Le théorème de Hex ne déroge pas à la règle, et ce n'est pas pour rien si le théorème de Jordan intervient dans certaines des preuves.
Le jeu de Hex à l'instar du jeu de go, du jeu de Nim ou du jeu des bâtonnets de Fort Boyard, est un jeu sans hasard à informations complètes. Le corollaire de ce fait : il existe forcément une stratégie gagnante pour l'un des joueurs. Pour être plus précis, c'est le premier joueur qui pose son pion qui dispose d'une stratégie qui est gagnant dans 100 % des cas (théorème de Nash). Le seul souci, c'est que le théorème ne dit pas quelle est la stratégie, si bien que la stratégie gagnante en question n'est pas connue, sauf pour les plus petits plateaux (pas plus de 9×9 cases).
Et je peux même le prouver : supposons que le joueur 2 dispose d'une stratégie gagnante. Alors, le joueur 1 passe son tour en jouant n'importe où, et peut maintenant prétendre être le joueur 2, et donc, disposer de la stratégie gagnante. Contradiction ! C'est l'argument du vol de stratégie, qui marche pour de nombreux autres jeux combinatoires (notamment, le jeu de Chomp).
Historiquement, le jeu de Hex est créé en 1942 par Piet Hein sous le nom Polygon en 1942. L'idée du jeu lui est venu alors qu'il tentait désespérément de démontrer le théorème des 4 couleurs. Il l'a montré au public lors d'une conférence à Copenhague sur les mathématiques des jeux, comme exemple de ce qu'est un bon jeu. Indépendamment de tout ça, John Nash (le prix Nobel d'économie, le taré que l'on voit dans le film Un homme d'exception de Ron Howard) réinvente Hex, pour montrer qu'il existe des jeux dans lequel le joueur 1 a une stratégie gagnante, mais que personne ne peut connaître. Le jeu prendra le nom Hex (comme hexagone) lorsque l'éditeur de jeu Parker (vous savez, le Monopoly...) rachète le tout.
Le théorème de Brouwer
Le théorème de Brouwer, lui, n'a rien à voir avec le jeu de Hex. C'est simplement un théorème de topologie qui énonce que toute application continue d'une boule fermée d'un espace euclidien dans elle-même admet un point fixe. Autrement dit, si on a une fonction f qui va d'une boule dans une boule (par exemple, la fonction qui à chaque goutte de café dans une tasse associe sa place après le touillage), il existe un point x0 tel que f(x0)=x0 (après le touillage, il y aura au moins une goutte de café qui n'aura pas bougé). Ce n'est pas le plus sexy des théorèmes de topologie, mais c'est grâce à lui qu'est née toute la théorie des théorèmes de points fixes.
Le hollandais Luitzen Egbertus Jan Brouwer à qui l'on doit se théorème était un fervent défenseur de l'intuitionnisme, doctrine mathématique qui (pour simplifier) déteste toutes les démonstrations non constructives (quand on dit "il existe", on le fabrique, au lieu d'utiliser des arguments par l'absurde ; par exemple, le théorème de Nash n'est pas du tout constructif). Ironie de l'histoire : s'il y a un théorème qui n'est pas constructif, c'est bien celui de Brouwer...
Ce théorème aura connu de nombreuses démontrations (topologique, en utilisant des propriétés du groupe fondamental ; combinatoire, par le lemme de Sperner...), mais il en existe une bien plus classe que les autres : celle qui utilise le théorème de Hex ! C'est la démonstration de David Gale (1979), et je vais vous la présenter pas plus tard que tout de suite :
[Attention : la démonstration qui suit est technique !...]
Plutôt que de travailler sur un plateau à cases hexagonales, on va jouer sur un carré. On note donc Bk le plateau de jeu carré (k+1)×(k+1) suivant. Les côtés opposés seront notés N,S,E et O.
Voici Bk , la version carrée du plateau de hex 6×6
Le théorème de Hex énonce donc :
Soient H et V deux ensembles recouvrant B_k. Alors,
- soit H contient un chemin reliant E à O
- soit V contient un chemin reliant N à S
Le théorème de Brouwer, dans le cas plan, et en changeant disque par carré, dit :
Soit I=[0,1]2 et f:I→I une fonction continue. Alors, il existe x0 ∈I tel que f(x0)=x0 .
Bref. Plutôt que de montrer qu'il existe un point fixe, on va montrer qu'il existe un point qui bouge pas trop : qu'il existe x tel que |f(x)-x|≤ε, pour ε arbitrairement petit (I est compact, donc ça suffit). La continuité de f étant uniforme, il existe δ≤ε tel que |x-x'|≤δ implique |f(x)-f(x')|≤ε. On prend la norme |x|=max(|x1|,|x2|).
Du coup, on considère le plateau Bk avec k plutôt grand (vérifiant 1/k≤δ). On considère alors les 4 sous-ensembles de Bk qui voici :
H+ = {z∈Bk | f1(z/k) - z1/k > ε}
H- = {z∈Bk | z1/k - f1(z/k) > ε}
V+ = {z∈Bk | f2(z/k) - z2/k > ε}
V- = {z∈Bk | z2/k - f2(z/k) > ε}
Où f=(f1,f2) et z=(z1,z2). En gros, un sommet z de Bk appartient à H+ (resp. H-, V+, V-) si z/k est déplacé par f de ε unités vers la droite (resp. vers la gauche, le haut, le bas). Si point fixe il y a, il existera un sommet de Bk qui sera dans aucun de ces sous-ensembles.
Fait supplémentaire : les sous-ensembles H+ et H- (resp. V+ et V- ) ne sont pas connectés. Pour voir ça, prenons z∈H+ et z'∈H- adjacents. Par définition de H+ et H- , on a :
f1(z/k) - f1(z'/k) + z1'/k - z1/k > 2ε
Mais, puisque z∈H+ et z'∈H- sont adjacents, on a |z'/k - z/k|≤δ≤ε, ce qui donne
f1(z/k) - f1(z'/k) > ε
Ce qui contredit le choix initial de δ (on a |f(z/k)-f(z'/k)|>ε).
Bref : H+ et H- (resp. V+ et V- ) ne sont pas connectés. Notons H=H+∪H- et V=V+∪V-. Si il existe un chemin connectant E à O dans H, il appartient soit à H+ , soit à H-. Mais H+ correspond aux points de I déplacés vers la droite : il n'y en a pas dans le bord droit de I. Autrement dit, H+ n'est pas connecté à E. De la même façon, H- (resp. V+, V- ) n'est pas connecté à O (resp N, S). Il n'y a donc pas de chemin connectant : H et V ne recouvrent pas Bk (pour ne pas contredire le théorème de Hex). Du coup, il existe un point qui ne bouge pas : c'est le point x0 recherché !
[Fin de la démonstration pénible]
Évidemment, le théorème de Hex se généralise aux dimensions supérieures, généralisant par là même la démonstration qui précède. Plus fort encore : il montre que le théorème de Brouwer permet de démontrer le théorème de Hex !
Je crois que c'est à peu près ce que je voulais dire, en ce dimanche 11 septembre...
Sources :
Hex : Everything You Always Wanted to Know About Hex But Were Afraid to Ask, par Thomas Maarup (tout sur le jeu de Hex : son histoire, ses stratégies)
The Game of Hex and the Brouwer Fixed-Point Theorem, par David Gale (tout sur l'équivalence entre le théorème de Hex et le théorème de Brouwer)