Choux romanesco, Vache qui rit et intégrales curvilignes

08 février 2015

Deux minutes pour l'hôtel de Hilbert

Vignette

J'en avais déjà parlé sûr ce blog il y a bien longtemps, mais cette histoire d'hôtel possédant une infinité de chambre est vraiment parfaite pour aborder la notion d'infini (et s'il le faut, j'en ferai un nouvel article dans 7 ans...)

Transcription :
En 1891, Georg Cantor défraye la chronique en annonçant au monde entier que tous les infinis ne se valent pas : certains infinis seraient plus grands que d'autres.
Trente ans plus tard, David Hilbert propose lors d'une conférence sa métaphore de l’hôtel, qui permet de comprendre pourquoi l'idée de Cantor, même si elle semble paradoxale, n'a absolument rien de stupide. Ça tombe bien, j'ai environ deux minutes pour en parler.

Sur la merveilleuse planète des mathématiques, il existe quelque part un hôtel très particulier : le grand hôtel de Hilbert. Cet hôtel possède un nombre infini de chambres, numérotées 0, 1, 2, 3, etc.

Ce soir là, il est 19h, et chaque chambre est occupée. malheureusement, un nouveau client se présente à l'accueil, et désire à tout prix une chambre pour la nuit. Puisque l’hôtel est complet, la situation semble impossible, et pourtant...
Après deux minutes de réflexion, le gérant répond « pas de problème », et annonce via les hauts-parleurs de l'hôtel que chacun des clients doit changer de chambre.
Le client de la chambre n°0 doit se déplacer dans la chambre n°1, celui de la chambre n°1 ira dans la chambre n°2, celui de la chambre n°2 ira dans la chambre n°3, et ainsi de suite : le client de la chambre n°n doit se rendre dans la chambre n° n+1.
La chambre n°0 est donc maintenant libre, et le nouveau client pourra donc y loger.
On peut donc finalement dire que ∞ +1 = ∞.

Malheureusement, à 21h, ce n'est pas un nouveau client qui se présente à l'accueil, mais un bus complet qui comporte une infinité de touristes. Dans ce bus, chaque siège est numéroté 0, 1, 2, …, et chacun de ces touristes veut sa chambre. Pour le gérant de l’hôtel, ce n'est encore une fois pas un problème.
Après deux minutes de réflexion, il se saisit de son micro, et annonce aux clients de l’hôtel les nouvelles directives à suivre.
Le client de la chambre n°1 doit se déplacer dans la chambre n°2, celui de la chambre n°2 ira dans la chambre n°4, celui de la chambre n°3 ira dans la chambre n°6, et ainsi de suite : le client de la chambre n°n ira ainsi dans la chambre n°2n.
Suite à ces déplacements, les chambres numérotées par des nombres pairs sont occupées, tandis que les chambres numérotées par des nombres impairs sont maintenant libres. Le touriste de la place 0 pourra donc loger dans la chambre n°1, celui du siège n°1 ira dans la chambre n°3, celui du siège n°2 se rendra dans la chambre n°5, et ainsi de suite : le touriste du siège n°y ira dans la chambre n°2y+1.
Finalement, on vient de démontrer que ∞ + ∞ = ∞.

Le lendemain, alors que l'hôtel s'est vidé, c'est une infinité de bus contenant un nombre infini de clients qui se présentent. Les bus sont numérotés 0, 1, 2, 3, etc, et dans chaque car, les places sont numérotées 0, 1, 2, 3, etc.
Encore une fois, cela ne va poser aucun problème au gérant de l'hotel, mais les clients devront respecter ses consignes.
Dans un premier temps, le 1er client du 1er bus (c'est à dire, le client du bus n°0 et du siège n°0) ira dans la chambre n°0.
Dans un second temps, le 1er client restant dans chacun des deux premiers bus (c'est à dire, le client du bus n°0 siège n°1, et le client du bus n°1 siège n°0) iront dans les deux chambres suivantes (chambre n°1 et n°2).
Dans un troisième temps, on logera dans les trois chambres suivantes le 1er client restant dans chacun des trois premiers bus, et ainsi de suite. En suivant cette procédure, chaque client se verra assigner une chambre pour la nuit. On peut même être plus précis, et prouver que le client du bus x et de la place y sera logé dans la place n° x + ½ [(y+x)²+y+x]. Chaque client a sa chambre, et chaque chambre a son client.
On vient donc de prouver que ∞ × ∞ = ∞.

Le lendemain, l’hôtel s'est une nouvelle fois vidé, mais c'est un bus d'un tout autre type qui se présente à l'accueil : dans ce bus, les clients sont infiniment serrés, puisque les sièges sont numérotés non pas par les nombres entiers, mais par tous les nombres réels de l'intervalle [0,1]. On pourra donc parler de la place 0,5, de la place 1/3, de la place π – 3 ou de la place √2/2.
Cette-fois-ci, il y a vraiment un problème. On pourrait trouver un moyen de loger tous les clients dont le numéro du siège est un nombre décimal. On pourrait même loger ceux dont le siège est une fraction rationnelle. Mais cette foule-ci est trop dense : cet infini des nombres réels est strictement plus grand que celui des nombres entiers, et c'est à Cantor que l'on doit cette découverte.

Essayons quand même de voir ce qu'il se passerait si on trouvait un moyen de loger chacun de ces clients.
Par exemple,

  • la chambre 0 accueillera le client de la place 1/3
  • le chambre 1 accueille celui de la place π – 3
  • la chambre 2 accueille celui de la place √2/2
  • la chambre 3 accueille celui de la place 0,5

et ainsi de suite, où chaque chambre accueillera un client différent de façon à ce que chaque client soit pris en compte.
Et pourtant, même si on voulait loger tout le monde on va se heurter à un impossible : certains clients ne trouveront pas de chambre, quel que soit la façon dont on s'y prendra.
Pour le comprendre, on va fabriquer un exemple de nombre qui ne peut pas se trouver dans la liste.
Prenons la 1ere décimale du premier client, la deuxième décimale du deuxième, la troisième du troisième et ainsi de suite. Dans notre exemple, on obtient le nombre 0,3470...
Maintenant, transformons chaque chiffre du nombre ainsi obtenu : on transforme les 0 en 1, les 1 en 2, les 2 en 3, et ainsi de suite, en transformant les 9 en 0.
Dans l'exemple, on obtient le nombre 0,4581...
On peut alors affirmer que le client dont le siège porte ce numéro ne trouvera pas de place dans l’hôtel, puisque si sa chambre est la chambre n°n, alors la (n+1)-ième décimale posera forcément problème. Et ce client n'est qu'un exemple parmi l'infinité de clients qui ne trouveront pas de chambre.

Bref : l'infini des nombres réels est strictement plus grand que l'infini des nombres entiers

Une question qui a longtemps perturbé les mathématiciens est de savoir si il existe un infini intermédiaire qui serait strictement plus grand que l'infini des nombres entiers (noté ℵ0) et strictement plus petit que celui de l'infini des nombres réels (noté, 2ℵ0).
Cette question, appelée hypothèse du continue, a trouvé sa réponse en 1963, lorsque Paul Cohen annonce qu'en fait, chacun peut choisir si oui ou non, il veut de cet infini intermédiaire, et que ça ne changera de toutes façons rien au reste des mathématiques. Mais ça, c'est une autre histoire...

 

Posté par El Jj à 10:10 - Commentaires [13] - Permalien [#]
Tags : , , ,

25 janvier 2015

Deux minutes pour le théorème de Futurama

Vignette

J'avais déjà parlé des références mathématiques dans la série Futurama (là-bas), mais je n'y avais qu'à peine développé LE théorème de futurama, celui qui parle de permutation. En environ deux minutes, voilà qui est maintenant fait :

 

Transcription :
Le 19 août 2010, la chaîne américaine Comedy Central diffuse "Le prisonnier de Benda", dixième épisode de la sixième saison de Futurama, la deuxième série de Matt Groening après les Simpsons. L'épisode est exceptionnel puisque, pour la première fois à la télévision, une intrigue est résolue à l'aide d'un théorème avancé de la théorie des groupes. Il faut dire que le producteur de la série est David X Cohen, diplomé en informatique théorique à l'Université de Californie, et que l'épisode en question a été écrit par Ken Keeler, diplomé à Harvard en mathématiques appliqué.
Ca tombe bien, j'ai deux minutes pour en parler !
Dans cet épisode, le professeur Farnsworth met au point une machine à échanger les corps qui, comme son nom l'indique, permet d'intervertir le corps et l'esprit entre deux personnes.
Pour le premier essai, le professeur échange son corps avec celui de son étudiante Amy.
Le problème, c'est que à cause des défenses imunitaires du cerveau, l'échange ne fonctionne que dans un seul sens : le professeur et Amy ne peuvent pas faire l'échange contraire.
Pour retrouver leurs corps d'origine, leur seule solution est d'utiliser un corps de transition : ça sera celui du robot Bender !
C'est donc naturellement que'il accepte d'échanger son corps avec celui de Amy. L'esprit du professeur se retrouve alors dans le corps de Bender, l'esprit de Bender est dans le corps de Amy et l'esprit Amy est dans le corps du professeur.
Maintenant, si l'on échange les corps de Bender et du professeur, le corps de Bender possèdera l'esprit de Amy, et le corps du professeur retrouvera son corps original. Oui, mais, les corps de Amy et Bender ont déjà été intervertis, l'échange retour est donc impossible !

Mais les échanges ne s'arrêtront pas là, puisque /

  • Amy, échange son corps de professeur avec celui de Leela
  • Bender échange son corps de Amy avec celui du seau robotique
  • Fry et Zoidberg s'échangent leur corps
  • Bender échange son corps de seau avec celui de l'empereur Nikolaï de l'empire robot-hongrois
  • Et enfin, Amy échange son corps de Leela avec celui de Hermès.

C'est donc une dizaine de corps et d'esprit qui sont mélangés. Comment vont-ils s'en sortir ?

Ce problème s'inscrit dans le domaine de l'algèbre appellé théorie des groupes et, plus particulièrement, dans celui des permutations.

Une permutation, c'est donc l'opération qui consiste à réarranger un certain nombre d'objets. Dans le cas présent : c'est la permutation de ces 9 corps qui nous intéresse.
Une propriété essentielle de cette théorie, c'est que n'importe quelle permutation correspond toujours à la composition de une ou plusieurs permutations circulaires disjointes. Pour le comprendre, il suffit de regarder dans quel corps se trouve chacun des espritS.
L'esprit du professeur se trouve dans le corps de Bender, l'esprit de Bender est dans le corps de Nikolaï, l'esprit de Nikolaï est dans le corps du robot de nettoyage, l'esprit de ce robot est dans le corps de Amy, l'esprit de Amy est dans le corps de Hermès, l'esprit de Hermès est dans le corps de Leela, et enfin, l'esprit de Leela est dans le corps de le corps du professeur. La boucle est bouclée. A côté de cela, il reste Fry et Zoidberg, qui ont échangé leur corps indépendament du reste du groupe.
La permutation de ces 9 personnages est donc composée de deux cycles :  un cycle de 7 personnages, appellé 7-cycle et un cycle de 2 personnages, appellé transposition.
C'est finalement une suite de transposition qui a engendré la permutation finale.
La question est donc de savoir quelle est la suite de transpositions à effectuer pour que tout rentre dans l'ordre, et le nombre minimal de corps de transition à apporter.

La réponse est donnée dans la série par Sweet Clyde et Bubble Gum Tate, deux basketteurs de l'équipe des Harlem Globtrotter. Il se trouve en effet que, dans le futur, cette équipe de basket n'est composéee que de scientifiques.
Ils démontrent donc dans l'épisode que deux corps de substitutions suffisent toujours, quel que soit la façon dont les autres membres auront été mélangés, et qu'il faudra a peu près autant d'échanges que de personnages présents. C'est ce théorème que l'on appelle aujourd'hui "théorème de Futurama", que l'on doit à Ken Keeler, le scénariste de l'épisode.

Démonstration :
Procédons dans le cas où la permutation n'est qu'un simple cycle. Pour simplifier, supposons qu'il contient 5 personnes, où l'esprit de 1 est dans le corps de 2, l'esprit de 2 est dans le corps de 3, etc., et ajoutons deux nouveaux corps X et Y, qui n'ont jamais permuté avec l'une de ces 5 personnes.
Dans un premier temps, on va permuter le corps additionnel Y avec le corps 1 et X avec le corps 2.
Dans un deuxième temps, on va remonter le corps Y jusqu'à l'esprit de X. Pour cela on échange les corps Y et 5, puis Y et 4, puis Y et 3, puis Y et 2.  
Il n'y a plus qu'à échanger les corps de X et de 1 pour que les 5 premiers esprits aient retrouvé leur corps original.
A ce point, les corps de X et Y sont échangés, il suffit d'une dernière transposition pour que tout rentre dans l'ordre.

Dans le cas général, une permutation est composée de plusieurs cycles.il suffit d'appliquer cette suite de transpositions sur chacun des cycles, et le tour est joué. CQFD

On peut maintenant appliquer le théorème à la permutation des personnages de Futurama, en ajoutant les nouveaux corps de Sweet Clyde et Bubblegum Tate.
Cette permutation est composée de deux cycles : le 2-cycle Fry-Zoidberg et le 7-cycle.
Commençons par remettre dans l'ordre Fry et Zoidberg :

  • On échange Tate et Fry
  • puis Clyde et Zoidberg
  • puis Tate  et Zoidberg
  • et enfin Clyde et Fry

Fry et Zoidberg ont retrouvé leur corps, tandis que Clyde et Tate l'ont échangé. Il n'y a plus qu'à s'occuper des 7 autres personnages :

  • On échange Tate et le professeur
  • puis Clyde et Bender
  • puis Tate et Leela
  • puis Tate et Hermès
  • puis Tate et Amy
  • et ainsi de suite jusqu'à l'échange entre Tate et Bender
  • et enfin, on échange Clyde et le professeur

Chacun a retrouvé son corps, en seulement 11 échanges !

Le théorème donne donc la marche à suivre pour que chaque esprit retrouve son corps, bien que la solution ne soit pas forcément optimale, puisque ce problème aurait pu être résolu en seulement 7 opérations. Cependant, le théorème s'adapte à n'importe quel problème similaire, et pourrait un jour vous servir si vous échangez par mégarde votre corps avec celui d'un ami...


Sources :
Futurama, le prisonnier de Benda - saison 5 & 6
Keeler’s Theorem and Products of Distinct Transpositions, Ron Evans, Lihua Huang, Tuan Nguyen

Posté par El Jj à 22:27 - Commentaires [0] - Permalien [#]
Tags : , , ,
04 janvier 2015

2014+1 (Cette nouvelle année est-elle intéressante ? Episode 06)

Une nouvelle année commence, avec son lot de bonnes résolutions qui ne seront pas tenues. Par exemple, j'ai décidé, en cette nouvelle année, d'écrire enfin un article sur Maryam Mirzakhani ! Vais-je tenir cette bonne résolution ?...
En tout cas, il y a une coutume à laquelle je ne résiste pas : éplucher l'OEIS à la recherche des propriétés intéressantes du nombre correspondant à l'année qui débute. Que peut-on dire de 2015 ? Je me tourne une nouvelle fois vers l'arbitre officiel de ce qui est intéressant : l'OEIS.

Rappelons que l'OEIS est l'encyclopédie en ligne des suites entières. Si une suite de nombres (entiers) est intéressante, elle sera présente dans cette encyclopédie. Du coup, si un nombre possède une propriété intéressante, elle sera dans une suite intéressante, et donc, dans l'OEIS. Ainsi, plus un nombre apparaît dans l'OEIS, plus il pourra être considéré comme intéressant.

Les nombres 2012, 2013 et 2014 possèdent donc (au moment où j'écris cet article) respectivement 131, 104 et 88 propriétés intéressantes. Et 2015, dans tout ça ?... Eh bien...

2015 possède 170 propriétés intéressantes !

2015 sera-t-elle enfin l'année où la courbe va s'inverser ? A en croire l'OEIS, oui !..

Inversion de la courbe
Nombre de propriétés pour chaque année, selon l'OEIS

Mais voyons dans le détail ce que l'OEIS nous dit de 2015...

Arbre de diamètre 5 [A189979]
Dans un graphe, le diamètre est la plus longue distance séparant deux sommets. Par exemple, les deux graphes suivants ont pour diamètre 5 :

Graphe_7s_d5
La distance séparant deux sommets dans un de ces graphe est toujours inférieure ou égale à 5.

Ces deux graphes ne sont pas simplement des graphes : ce sont des arbres (ils ne possèdent aucune boucle - ou cycle). Et on peut en fait vérifier que ce sont les deux seuls arbres de diamètre 5 possédant 7 sommets.

On peut aussi vérifier qu'il existe 7 graphes de diamètre 5 possédant 8 sommets :

Graphe_8s_d5

Et pour les graphes de diamètre 5 possédant 18 sommets, il y en a 2015 :

Graphe_18s_d5
Un exemple parmi les 2015 existants...

Sous-réseaux tridimentionnels [A001001]
Les points à coordonnées entières dans le repère d'un plan (infini) forment ce que l'on appelle un réseau carré.
En sélectionnant ces points de façon adéquate (en ne gardant que 1 sur 2, ou que 1 sur 3, toujours de la même façon), on forme un sous-réseau. On dira que le sous-réseau est d'ordre n si on en a gardé que 1 sur n.

Ainsi, on peut fabriquer exactement 7 sous-réseaux carrés d'ordre 4, suivant la façon dont on sélectionne "un point sur 4" :

Sreseau_1004     Sreseau_4001     Sreseau_4011     Sreseau_4031     
Sreseau_2002     Sreseau_2012     Sreseau_2102

On peut en fait démontrer que le nombre de sous-réseaux carrés d'ordre n est égal à σ(n), c'est à dire, la somme des diviseurs de n. Puisque les diviseurs de 4 sont 1, 2 et 4, σ(4) = 1+2+4 = 7, ce qui est bien le nombre de sous-réseaux carrés d'ordre 4. On peut ainsi vérifier qu'il y a 6 sous-réseaux carrés d'ordre 5, et 12 d'ordre 6. Mais tout ceci n'a rien a voir avec 2015.

On peut de la même façon chercher les sous-réseaux d'un réseau cubique, à 3 dimensions (les points à coordonnées entières dans un repère de l'espace). Pour ce qui est des sous-réseaux cubiques d'ordre 2, on en dénombre 7 différents :

Screen Shot 12-28-14 at 06 Screen Shot 12-28-14 at 06 Screen Shot 12-28-14 at 06

Screen Shot 12-28-14 at 06 Screen Shot 12-28-14 at 06 Screen Shot 12-28-14 at 06 Screen Shot 12-28-14 at 06

Le nombre de sous-réseaux cubiques d'ordre n est en fait donné par la formule 

sum_d_sigma_d

On peut ainsi vérifier que le nombre de sous-réseaux cubiques d'ordre 3 est 13, mais surtout, que le nombre de sous-réseaux cubiques d'ordre 24 est... 2015 !

Triangles rectangles distincts [A189979]
Prenons une grille 4x4 : combien peut-on y tracer de triangles rectangles différents, à une isométrie (translation, symétrie, rotation) près ?
La réponse en gif est 9 :

Triangles_Rectangles

Et sur une grille 40x40 ?... 2015, évidemment !

 

Mais 2015 possède d'autres propriétés intéressantes !

  • [A129868] 2015, quand on l'écrit en binaire, devient 11111011111 : c'est un palindrome ! (Voir l'article de Blogdemaths pour une étude détaillée de ces nombres palindromes)
  • [A006972] 2015 est un nombre de Lucas-Carmichael. Ces nombres ont une définition proche de celle des nombres de Carmichael, qui sont les nombres qui ont l'air premier au yeux du test de primalité de Fermat (le plus classique des tests de primalité), mais qui ne le sont en fait pas du tout. Mais comme ils n'ont pas la même définition, les nombres de Lucas-Carmichael n'ont en fait aucun intérêt (sinon celui d'exister, et ça, c'est cool)
    Un nombre n, donc, est appellé nombre de Lucas-Carmichael lorsque : si p est un facteur premier de n, alors p+1 divise n+1 (il faut en plus que n soit sans facteur carré)
    2015 possède 3 facteurs premiers, qui sont 5, 13 et 31. Puisque les nombres 6, 14 et 32 sont des diviseurs de 2016, alors 2015 est un nombre de Lucas-Carmichael.
  • [A001304] Il y a 2015 façons différentes de composer un bouquet fleurs à 45 € chez un fleuriste proposant 4 types de fleurs coûtant respectivement 1, 1, 2 et 5 €.
  • [A164576] 2015 est la moyenne des 77 premiers carrés : 2015 = (1²+2²+3²+...+77²) / 77
  • [A115160] 2015 ne peut pas être écrit comme la somme de deux nombres triangulaires et d'un nombre à la puissance 4.
  • [A124189] Le nombre 1 + 2015 + 2015+ 2015+ 2015+ 2015+ 201511 + ... + 201539 est un nombre premier ! (Un point à celui qui arrive à replacer ça dans une conversation)
  • [A120828] Le nombre 109876543210987...109876543210987 (qui compte 2015 chiffres) est un nombre premier ! (Un point bonus à celui qui arrive à replacer ça en plus dans la même conversation)

Et quelques autres propriétés glanées sur Twitter aux alentours du 1er janvier :

  • 2015 = 48×48-17×17 ! Mais si vous avez trop bu et que vous lisez à l'envers, 84×84-71×71, ça fait toujours 2015. (@MickaelLaunay)
  • 2015 = 13³-13²-13¹ (@brusicor02) [A152015]

Et la santé !

Posté par El Jj à 10:00 - Commentaires [3] - Permalien [#]
Tags : , ,
28 décembre 2014

Deux minutes pour le duc de Densmore

Cette vidéo ne contient aucun 42 et c'est une honte !

Ce sont les fêtes de Noël ! Quoi de mieux qu'une enquête policière sur fond de théorie des graphes ? !


Sources :
Qui a tué le duc de Densmore, Claude Berge, à lire à partir de la page 77

Posté par El Jj à 11:09 - Commentaires [0] - Permalien [#]
Tags : , ,
30 novembre 2014

Deux minutes pour les maisons de Dudeney

Water_gaz_electricity_Dudeney

Nouvel épisode de "deux minutes pour", où il est cette fois-ci question de problèmes de voisinages à SimCity...

 Et bon anniversaire à ce blog qui vient de souffler sa huitième bougie !

Posté par El Jj à 10:00 - Commentaires [3] - Permalien [#]
Tags : , , ,
09 novembre 2014

NP Entertainment System

Super Mario Bros : The Lost Levels est un jeu très difficile, tous les joueurs qui l'ont testé le savent. Mais ce qu'une bande de mathématiciens / informaticiens (G. Aloupis, E. D. Demaine, A. Guo et G. Viglietta) ont démontré en février 2014 dans un article d'une trentaine de pages, c'est que c'est plus qu'un jeu difficile : c'est un jeu... NP-difficile ! Et ce n'est pas le seul : la plupart des jeux de la série des Mario, Zelda, Donkey Kong, Metroid et Pokémon sont eux aussi NP-difficile. Candy Crush aussi, d'ailleurs, mais cela n'a aucun rapport.
Il n'est pas vraiment ici question de la difficulté de ces jeux en elle-même, mais plutôt de la complexité des puzzles qu'il est possible de générer avec le moteur de ces jeux.

En informatique, une question de type Oui/Non peut être plus ou moins complexe : plus un problème est complexe, plus les algorithmes permettant de les résoudre seront long à être exécutés. Il existe tout un bestiaire de classes de complexités, les principales étant les classes P et NP (bien que l'on ne sache pas réellement si ces deux classes sont distinctes ou non, mais c'est un autre problème). 
D'un côté, donc, il y a les problèmes P (polynomiaux), ceux qui sont faciles et rapides à résoudre. Par exemple, savoir si une liste est triée est un problème facile : si il me faut 21 secondes pour vérifier qu'une liste donnée de mots est rangée par ordre alphabétique, il m'en faudra 42 pour vérifier qu'une liste 2 fois plus grande l'est. Le temps de cette vérification est ici proportionnel à la taille des données qui rentrent en jeu, et c'est en cela que l'on peut dire que ce problème est facile. De manière plus globale, un problème est "facile" si le temps nécessaire pour y répondre est une fonction polynomiale de la taille des données.
De l'autre côté, il y a les problèmes NP qui ne sont pas P (Non déterministe en temps polynomial), ceux qui sont dans les grandes lignes difficiles et longs à résoudre. Par exemple, savoir s'il est possible de relier les 6 plus grandes villes de France en moins de 30 heures demandera 20 secondes de calculs, tandis que savoir si on peut relier les 12 plus grandes villes en moins de 60h prendra 5 jours de calculs, et c'est encore pire si le nombre de villes augmente. Le temps n'est pas du tout proportionnel à la taille des données impliquées ! Un problème est donc "difficile" si le temps nécessaire pour répondre "non" n'est pas une fonction polynomiale de la taille des données (mais qu'il peut quand même être résolu de manière polynomiale si l'algorithme utilise un générateur de hasard).

Ce qui est NP-difficile chez les jeux classiques de Nintendo, c'est de savoir si, dans une carte d'un Mario ou d'un Pokémon généralisé, il est toujours possible d'aller d'un point A à un point B en respectant les règles de ce jeu. Et on va le prouver, en montrant que dans tous les jeux Nintendo se cache en fait un problème 3-SAT !

Le problème 3-SAT
Le problème SAT est un problème de classe NP. S'il ne devait en rester qu'un, ça serait celui-là. Pour montrer qu'un problème est NP-difficile, le meilleur moins de procéder est bien souvent de montrer qu'il peut être ramené à ce problème. Le problème SAT est le suivant :

Étant donné une forme normale conjonctive, est-il possible d'assigner des valeurs booléennes à ses variables qui la rende logiquement vraie ?

Détaillons un peu. Si on dispose de plusieurs variables booléennes ("Vrai" ou "Faux") A, B, C et D, une forme normale conjonctive est une expression construite avec ces variables (ou leur négation) composée de parenthèses de "ou" entrecoupées de "et". L'expression suivante

(A ou B ou ¬D) et (¬A ou ¬C ou ¬D) et (A ou C ou D) et (¬A ou B ou ¬C) et (B ou ¬C ou ¬D)

est un exemple de forme normale conjonctive. Celle-ci est constituée 4 variables, de 5 clauses et de 3 variables par clauses. La question qui se pose alors est de savoir si il est possible de déterminer des valeurs logiques pour chacune des 4 variables qui rendent l'expression vraie.
Dans ce cas, c'est effectivement possible, en prenant par exemple les variables A=Vrai, B=Vrai et C=Faux et D=Faux, car chacune des 5 clauses de la FNC sont vérifiées. Mais pour aboutir à cette solution, la façon la plus simple de procéder reste encore d'essayer les 16 combinaisons possibles jusqu'à tomber sur une solution qui fonctionne. Mais lorsque le nombre de variables augmente, le nombre de combinaisons explose, et c'est pour cela que le problème SAT est (NP-)difficile !
Puisqu'il a été démontré que le problème SAT est équivalent au problème 3-SAT (cas où chaque clause ne contient que 3 variables), c'est ce problème particulier qui va nous intéresser.

Pour démontrer que les jeux Nintendo sont NP-difficiles, il faut donc montrer que certains niveaux de Metroid ou de Zelda peut être ramenés à l'assignation de variables d'une forme normale conjonctive. Prenons l'exemple de la forme normale conjonctive suivante

FNC = (A ou ¬B ou C) et (¬A ou B ou C) et (A ou ¬B ou ¬C)

Pour transformer ce problème 3-SAT en niveau de Zelda, il faut que le level design oblige Link à résoudre ce problème de logique. Pour cela, on va simuler au sein du jeu l'assignation des variables, ainsi que la vérification des clauses en fonction des variables rentrées.
Dans un premier temps, notre avatar passera successivement, et sans possibilité de retour en arrière, par trois modules d'assignation de variables (autant que de variables). Chacun de ces modules consiste à choisir un chemin, celui-ci correspond à donner une valeur logique (Vrai/Faux) à chacune des variables A, B et C. Lorsqu'une valeur "Vrai" ou "Faux" est choisie pour une variable, elle donne accès aux modules de clauses correspondant (par exemple, choisir "Vrai" pour la variable A donne un accès aux clauses (A ou ¬B ou C) et (A ou ¬B ou ¬C), car c'est une valeur qui valide ces clauses). Ces modules de clauses, si ils sont tous visités au moins une fois, ouvrent l'accès final à l'arrivée. Résoudre le problème 3-SAT consiste donc à trouver le chemin qui permet d'ouvrir ce chemin final.

Schéma modules

Schéma de la carte qui permettra de résoudre le problème 3-SAT ci-dessus.
En vert les modules de départ/arrivée, en bleu les modules d'assignation des variables et en rouge les modules de vérification des clauses.
Les chemins noirs correspondent à des chemins que l'on peut passer que dans un seul sens, les chemins rouges peuvent être traversés dans les deux sens. Il ne doit être à aucun moment possible de sortir de ces chemins.
La sortie V du module variable A donne seulement accès aux entrées A, lorsqu'elles existent, des modules de clauses, ainsi qu'à une entrée sans retour possible dans le module variable B.

Ainsi, il faudra construire pour chacun des jeux les modules correspondant aux différentes étapes logiques:

  • Module d'assignation des variable
  • Module de clause

Ainsi que des modules qui permettent de mettre en place le schéma au sein du jeu :

  • Module de départ / d'arrivée
  • Module de carrefour, qui empêche de passer d'un chemin à un autre lorsque deux chemins différents se croisent
  • Module de chemin à sens unique

La saga The Legend of Zelda est NP-difficile !
Commençons par la saga The Legend of Zelda ! Dans cette série, on incarne Link, héros vêtu du vert, qui s'attelle épisode après épisode à sauver la princesse Zelda des griffes de génies démoniaques. Pour l'aider dans sa quête, il dispose d'un arsenal d'objets variant en fonction des jeux, comme des bombes, un boomerang, un marteau ou un masque permettant de danser comme Kamaro. L'un des objets emblématique de la série est le grappin qui permet à Link d'atteindre des zones inatteignables, et c'est cet objet qui nous permettra de montrer que le jeu est NP-difficile !

Ce n'est pas vraiment du jeu The Legend of Zelda que parle le théorème de Aloupis, mais de sa version généralisée. Dans cette version, les cartes peuvent être arbitrairement grande, tout comme la mémoire de la SNES qui la ferait tourner. Elle garde cependant les caractéristiques du jeu original : même comportement des ennemis, des décors et des objets, même gameplay, etc. Le théorème de Aloupis énonce donc :

Dans le jeu The Legend of Zelda : A Link to the past généralisé, déterminer si il est possible d'atteindre un point donné depuis un autre point donné est un problème NP-difficile.

On va commencer par le démontrer dans la version généralisé de The Legend of Zelda: A Link to the Past pour une raison assez simple : c'est le meilleur épisode de la série. Seuls deux éléments du gameplay nous seront utile dans la démonstration :

  • Link est capable de pousser certaines pierres (mais ne peut pas les tirer)
  • A l'aide du grappin, Link peut rejoindre une plate-forme contenant un coffre, dans le cas où aucun obstacle se trouve dans sa trajectoire. Il peut aussi s'agriper aux pierres.

On supposera alors que Link ne dispose d'aucun autre objet que le grappin (en particulier, qu'il ne possède aucun objet lui permettant de sauter).

Module de départ / d'arrivée :
Pas de problème pour cela : on supposera que Link entre dans la salle depuis une porte, et cherche à atteindre l'autre porte. On veillera cependant à placer un sol destructible au début de la pièce, puisque si Link tombe dans un précipice, il serait téléporté en début de salle.

Module d'assignation des variables :
Pour chacune des variables du problème SAT correspondant, Link doit choisir une valeur logique Vrai ou Faux. Pour modéliser cela, on oblige Link a devoir choisir entre deux chemins qui s'offre à lui, sans possibilité de retour en arrière, et c'est le grappin qui permet cela :

Zelda_assignation_variable
Module d'assignation de variable :
Link arrive en haut, et doit choisir, grâce au grappin, l'un des deux chemins proposés
Le chemin de gauche correspondra à l'assignation Vrai, le chemin de droite à l'assignation Faux.

Ce module donne également une façon de construire le module de passage à sens unique, en plaçant un coffre de l'autre côté d'un précipice.

Module de clauses :
Avant de pouvoir accéder à la porte finale, Link doit avoir ouvert le passage pour chacun des modules de clauses. Chacun de ces modules doit avoir été visité au moins une fois par Link pendant la phase d'assignation des variables, avant de procéder à la vérification finale.

Zelda_clause
Module de clause :
Link entre dans ce module par la droite, et doit atteindre la sortie à gauche.
Pour passer, il faut que (au moins) l'une des pierres ait été poussée, afin qu'elle puisse être atteinte à l'aide du grappin.
Chaque pierre correspond à l'une des trois variables de la clause concernée, les chemins y menant étant reliés à leur variable correspondante.

Module de carrefour :
Les chemins se croisent souvent, et il ne faut pas que Link puisse passer d'un chemin à un autre. Encore une fois, le grappin permet de construire de tels croisements :

Zelda_carrefour
Module de carrefour :
Si Link entre à l'ouest, il ne peut que ressortir à l'est, grâce au grappin. Et inversement.

Maintenant que l'on dispose de tous ces modules, on peut fabriquer un donjon pour The Legend of Zelda: A Link to the Past arbitrairement difficile, au sens de la complexité. CQFD !

Un petit exemple pour montrer à quel point cette construction est horrible, avec la FNC donnée plus haut en exemple :  (A ou ¬B ou C) et (¬A ou B ou C) et (A ou ¬B ou ¬C) :

Zeldaaaaaaah
Le plan du donjon correspondant à la FNC : (A ou ¬B ou C) et (¬A ou B ou C) et (A ou ¬B ou ¬C)
Terminer cette salle est équivalent à résoudre le problème NP-difficile 3-SAT correspondant !
Ce qui prend en fait le plus de place dans est le nombre énorme de modules de carrefour...

Les épisodes RPG de la série qui suivent A Link to the Past gardent les mêmes mécaniques de jeu, en particulier le grappin et la possibilité de pousser des pierres. La démonstration est donc exactement la même, et on peut conclure que tous les épisodes de la série, dans leur version généralisée, sont NP-difficile.
Cependant, le grappin ne peut pas être trouvé dans le premier épisode de la série, The Legend of Zelda. Des mécanismes de poussage de blocs sont cependant présent, ce qui permet tout de même de prouver que lui aussi est NP-difficile, puisqu'il est équivalent au jeu Sokoban (un jeu où l'on incarne un garde d'entrepot chargé de ranger des caisses, démontré comme étant NP-difficile).
Seul The Adventure of Link ne peut pas être prouvé de cette façon comme NP-difficile, son gameplay étant radicalement différent des autres épisodes de la série. La complexité de ce jeu est donc toujours ouverte !

La saga Super Mario Bros. est NP-difficile !
Autre saga phare de Nintendo : les jeux de plate-forme de la série des Super Mario Bros., qui contient quand même une vingtaine d'épisodes. On y incarne Mario, un plombier moustachu vouant sa vie à arpenter le monde pour venir en aide à divers avatars féminins. Et sa tâche n'est pas aisée : pour ce qui est des épisodes 2D de la série, on peut montrer qu'ils sont tous NP-difficiles. Le schéma de la preuve est le même : il faut construire les modules de variables, de clause et de croisement !

Chaque épisode de la série présente ses spécificités, mais on peut commencer par les deux premiers épisodes : Super Mario Bros. et Super Mario Bros. : The Lost Levels. Ces deux épisodes sont techniquement similaires, puisqu'ils sont basés sur le même moteur de jeu. En particulier, tous les éléments du premier épisode de retrouvent à l'identique dans le suivant.

Encore une fois, on parlera de maps généralisées pour Super Mario Bros. On supposera que la carte peut être arbitrairement grande, et qu'elle n'est soumise à aucune contrainte technique. En particulier, on va admettre que l'écran du jeu peut être arbitrairement grand, puisque, dans le jeu original, le scrolling empêche Mario de sortir de l'écran par la gauche. On supprimera aussi la contrainte du temps. Le théorème de Aloupis énonce donc :

Dans le jeu Super Mario Bros. généralisé, déterminer si il est possible d'atteindre le drapeau de fin d'un niveau depuis son départ est un problème NP-difficile.

Pour démontrer cela, on s'appuiera sur les propriétés suivantes :

  • Mario est capable de marcher, courir et sauter (jusqu'à une hauteur fixée). Il peut mourir instantanément si il tombe dans un trou sans fond, mais ne subit aucun dommage lors de chutes.
  • Initialement, Mario est petit. Lorsqu'il ramasse un champignon, il devient super Mario, plus grand, et acquière le pouvoir de casser certaines briques en sautant par en-dessous. Lorsqu'il est touché par un ennemi, il redevient Mario, petit.
  • Mario peut également ramasser des étoiles dans des blocs "?", qui le rendent temporairement invulnérable.

Ces quelques éléments du gameplay vont nous permettre de construire les modules nécessaires à la preuve

Module de départ / d'arrivée :
On supposera que Mario doit ramasser en début de niveau un super champignon, et qu'il doit rester Super Mario jusqu'à la fin du niveau. Pour obliger cela, on utilisera les modules de départ et d'arrivée suivants :

Mario_debut
Module de départ :
Le bloc contient un super champignon

Mario_fin
Module d'arrivée :
Pour atteindre le drapeau d'arrivée, il est nécessaire d'avoir pris le champignon du départ

Module d'assignation de variable :
Pour affecter une valeur booléenne à une variable, on utilisera le fait que lorsque Mario tombe, il ne pourra plus remonter :

Mario_variables
Module d'assignation de variable :
Mario doit faire un choix entre le chemin de gauche et de droite. Une fois le choix fait, on ne pourra plus revenir en arrière.

Module de clause :
Pour pouvoir passer ce module de clause, Mario doit faire apparaître une étoile d'invincibilité contenue dans les blocs "?", seule celle-ci permettra de passer les tourniquets enflammés sans être blessé. Ce sont ces blocs "?" qui sont accessibles depuis les chemins d'assignation de variables.

Mario_clause
Module de clause :
Pour franchir ce module, il est nécessaire d'avoir activé l'un des blocs "?"

Module de carrefour :
Le plus difficile à construire, c'est en fait ce module de carrefour :

Mario_carrefour
Module de carrefour :
Si Mario arrive du côté gauche, il ne pourra que sortir du côté droit. Pour cela, il devra retrouver sa taille initiale grâce au Goomba, ce qui lui donne accès au petit passage. Sa petite taille l'empêche de casser les briques, et l'oblige à ressortir du côté droit, après avoir repris un champignon dans le bloc "?".
Si Mario arrive en bas, sa grande taille lui permettra de prendre le chemin du haut en cassant les briques, mais lui interdit le passage réservé au petit Mario.
Ce carrefour ne peut cependant être traversé que dans le sens gauche-droite ou bas-haut.

Puisque ces modules peuvent être réalisés, Super Mario Bros. et Super Mario Bros. : The Lost Levels sont NP-difficile ! CQFD.

Je ne me vais pas me risquer à construire un exemple de monde simulant un problème SAT, la taille du module de carrefour rendront la carte démesurée...
Et les autres jeux de la saga dans tout ça ? Eh bien, il va falloir regarder au cas par cas...

Super Mario Bros 3
Dans ce jeu, les flammes n'existent pas ! Il va falloir du coup modifier le module de clause.

SMB3_clause
Module de clause de SMB3 :
Pour franchir le mur de brique du chemin du bas, il est nécessaire d'avoir éliminé l'un des trois Koopa du dessus (chaque tortue correspond à une variable de la clause). 

Super Mario World
Les flammes n'existent pas non plus dans cette opus de la série. Mais les grands absents de cet épisode, ce sont les briques, qui sont remplacées par des blocs jaunes. Ces blocs ne peuvent pas être détruit, mais il est possible de les franchir par en-dessous quel que soit la taille de Mario, et par au-dessus lorsque Mario est grand. Il faut donc modifier les modules d'arrivée, de clause et de carrefour:

SMW_Arrivee
Module d'arrivée :
Un champignon est nécessaire pour franchir le bloc jaune.

SMW_Clause
Module de clause :
Mario doit franchir ce module depuis le côté droit jusqu'au côté gauche. Pour ce faire, il doit appuyer sur le bouton P contenu dans le bloc "?", celui-ci transformant les pièces en blocs franchissables. Pour que ce bouton apparaisse, il faut que l'une des carapaces de Koopas atteigne le bloc "?", les chemins amenant à ces Koopas n'étant accessibles que lors de la phase d'assignation des variables.
A noter tout de même qu'il faut placer un dispositif (des vignes servant d'échelle, par exemple) empêchant Mario d'emporter l'une des carapaces.

SMW_Carrefour
Module de carrefour :
Le principe reste le même. Ce carrefour est traversable de gauche à droite et de haut en bas.

Les autres épisodes
Pour les épisodes suivants, le principe reste le même. Il faut simplement se méfier des wall jump qui apparaissent à partir de Super Mario 64, qui obligent à repenser les modules d'assignation de variable...

La saga Pokémon est NP-difficile !
Une fois n'est pas coutume, je vais devoir à nouveau parler de Pokémon sur ce blog ! Ce n'est quand même pas ma faute si on peut y trouver autant de problématiques mathématiques... Les jeux de cette saga mettent en scène un jeune à casquette qui cherche à réaliser son rêve : capturer un maximum de Pokémon et les entraîner à combattre afin de devenir maître Pokémon ! Une vingtaine d'épisodes sont sortis, et le constat est sans appel : ils sont tous NP-difficiles !

Tous les jeux de la série mettent en scène des problèmes de type Sokoban, et la simple existence de ce mécanisme entraîne sa NP-complexité. Mais on va plutôt le démontrer en s'appuyant sur le cœur des jeux Pokémon : les combats contre les dresseurs !

Encore une fois, il nous faut une version idéalisée du jeu (carte et mémoire en machine arbitrairement grande), et le théorème de Aloupis devient :

Dans la série RPG des jeux Pokémon (généralisés), déterminer si il est possible d'atteindre un point donné depuis un autre point donné est un problème NP-difficile.

Pour construire des cartes construisant des problèmes SAT, on va s'appuyer sur un principe de base des jeux : quand on passe dans le champs visuel d'un dresseur Pokémon adverse, il s'avance vers nous pour nous combattre. Si le dresseur est battu, il restera à sa place, ne pourra plus bouger et ne cherchera plus à combattre. Si un autre dresseur est dans le champ de vision de premier dresseur, celui-ci ne nous verra pas. On se servira de ces mécanismes pour bloquer certains passages

Pour les besoins de la démonstration, on ne considérera que deux types de dresseurs ennemis : les dresseurs faibles et les dresseurs forts.

  • On supposera que notre avatar ne possède aucun objet utilisable et une équipe composée de un seul Pokémon avec une seule attaque : Fantominus (avec l'attaque Destruction, qu'il apprend dans la génération I ou II), ou Skelénox (avec l'attaque Souvenir, à partir de la génération III). Les attaques Destruction et Souvenir ont la particularité de mettre K.O. le Pokémon qui le lance. Ainsi, notre seule action possible lors d'un combat est de lancer l'autodestruction, et de perdre le combat si l'on attaque en premier.
  • Les dresseurs faibles seront forcément battu. Pour implémenter un tel dresseur, on pourra par exemple supposer qu'ils ne possèdent que un Pokémon, un Électrode de niveau 100 et de vitesse maximale possédant la seule attaque Destruction. Dans un combat, ce dresseur faible attaquera en premier, et la destruction lui fera perdre le match. Puisque notre Pokémon est de type spectre, il sera insensible à cette attaque de type Normal.
  • Les dresseurs forts sont imbattables. Ils possèdent deux Pokémon quelconques. Lorsque l'on combat un de ces dresseurs, on sera obligé d'utiliser l'attaque Destruction ou Souvenir, amenant nécessairement à la défaite.

Dans les modules suivants, le champs de vision des dresseurs sera représenté en rouge pour les dresseurs invulnérable, et en bleu pour les dresseurs faibles.

Module de départ / d'arrivée :
Rien de particulier pour ce module, on a juste à se fixer un point de départ et d'arrivée.

Module de chemin à sens unique :
Les routes à sens unique existent déjà dans tous les jeux de la série, grâce à l'existence des corniches. Il est tout de même possible de construire ces chemins uniquement grâce à des dresseurs :

Pokemon_sens_unique
Module de chemin à sens unique :
Quand on passe ce chemin dans un sens, le dresseur bleu s'avancera pour combattre (et perdre), ce qui laissera la voie libre au dresseur rouge du bas. Le chemin de retour implique donc de combattre ce dresseur invulnérable : le retour est impossible. 
L'autre dresseur rouge est présent pour nous empêcher d'aller parler au dresseur bleu.

Module d'assignation de variable :
Dans les jeux Pokémon, les combats contre les dresseurs peuvent être déclenchés de deux façons différentes : soit lorsque l'on rentre dans leur champ de vision (et le dresseur s'avance pour nous combattre), soit lorsqu'on leur parle. Ce sont ces mécaniques que l'on utilisera pour assigner les variables.

Pokemon_Variables (2)
Module d'assignation de variable :
On arrive par la gauche. Pour prendre la sortie de droite, il faut commencer par aller parler au dresseur sans être vu. Une fois immobilisé, la sortie de droite est disponible, et la sortie haute condamnée. Inversement, pour prendre la sortie haute, on commencera par faire avancer le dresseur en rentrant dans son champ visuel. Il laisse alors un accès au chemin du haut.

Module de clause :

Pokemon_Clause
Module de clause :
Il doit être traversé de droite à gauche. 
Si le module n'a pas été visité depuis les entrées A, B ou C, tous les dresseurs bleus s'avanceront pour combattre, laissant le champ libre au dresseur rouge qui regarde vers la gauche. Il bloquera alors le chemin. Il faut donc préalablement neutraliser ces dresseurs bleus, en allant parler à au moins l'un d'entre eux.

Module de carrefour :
Encore une fois, le module de carrefour est le plus compliqué. Celui-ci peut être traversé une fois de gauche à droite, ou une fois de haut en bas.
Ce module comprend 4 modules de chemin à sens unique.

Pokemon_carrefour
Module de carrefour :
Pour franchir ce carrefour de gauche à droite, on commencera par venir parler au dresseur bleu qui regarde loin vers la droite. Après avoir franchit deux des quatre modules de sens unique, la voie sera libre pour la sortie de droite. 

Puisque ces modules peuvent être réalisés, les 25 RPG Pokémon sont NP-difficiles ! CQFD.

Les sagas Metroid et Donkey Kong sont NP-difficiles !
D'un côté, il y a Metroid, où l'on incarne Samus, une chasseuse de primes en quête de retrouver les métroïdes volées par les pirates de l'espace. De l'autre, il y a Donkey Kong Country, où l'on incarne Donkey Kong, un gorille en quête de retrouver son stock de bananes volé par le roi K. Roll, un crocodile obèse. Les scénarios sont plutôt différents, mais la conclusion de Aloupis est la même : ce sont des jeux NP-difficile !
Encore une fois, les démonstrations s'appuient sur la construction des différents modules, mais je ne vais pas les détailler (allez consulter l'article de Aloupis !).

Pour le cas de Donkey Kong Country, les modules de carrefour et de sens unique sont présent directement dans le jeu, grâce aux tonneaux. Le module de variable est similaire à celui de Mario, tandis que le module de clause s'appuie sur l'existence des Zingers, monstres abeilloïdes. Ces éléments se retrouvent dans tous les autres opus 2D de la série, qui sont donc eux aussi NP-difficiles.

Pour Metroid, les modules de carrefour utilisent la capacité de Samus à se transformer en morphball, tandis que le module de clause s'appuie sur l'existence des Hépixors (Zoomers, en VO), monstres mollusquoïdes. Ces éléments sont également présents dans l'ensemble des autres épisodes de la série, les rendant eux aussi NP-difficiles.

Dans leur papier, Aloupis, Demaine, Guo et Viglietta ne s'arrêtent pas à la démonstration de la NP-difficulté de toutes ces licences Nintendo, mais ils démontrent également, pour Zelda et Donkey-Kong Country, leur PSPACE-difficulté. Ces deux jeux sont donc encore plus complexes que complexes !
Si un algorithme cherche à résoudre un problème de déplacement dans une carte de l'un de ces jeux, non seulement le temps de calcul demandé sera énorme (=non proportionnel à la taille de la carte), mais la mémoire demandée par l'algorithme sera elle aussi énorme. La méthodologie de la démonstration est similaire, mais ils montrent que ces jeux sont équivalent à un autre problème de logique (le problème TQBF), et construisent d'autres types de modules.

Bref, vous avez tout ce qu'il faut pour maintenant démontrer vous même que Sonic, Alex Kidd, Tomb RaiderMinecraft ou Mr Carré sont (ou non) NP-difficiles !


Sources
Classic Nintendo Games are (Computationally) Hard --  G. Aloupis, E. D. Demaine, A. Guo et G. Viglietta 

Posté par El Jj à 10:10 - Commentaires [10] - Permalien [#]
Tags : , , , , ,


Fin »