23 août 2009
Les classiques de chez classiques
Pour avoir une bonne culture générale, il est nécessaire de bien connaître la chronologie des rois de France, les plus grands peintres de la Renaissance (ou les tortues ninja, au choix) ou avoir lu les meilleurs tome des Rougon-Macquart. Avec ça dans la tête, vous n'aurez aucune difficulté à gagner chez Julien Lepers. Malheureusement, cela ne suffit pas pour ne pas se faire piéger par votre filleul à qui l'on vient d'offrir un bouquins d'énigmes...
Quelle est l'étendue de votre culture en amusette mathématique ? Voici ma petite sélection des 10 énigmes plus ou moins mathématiques qu'il est inadmissible de ne pas connaître ! Notez 1 point si vous ne la voyez pas pour la première fois, et 2 points si, en plus, vous vous rappelez de la solution !
A noter que le choix est purement subjectif. J'en ai surement oublié des ultra classiques, et que certaines ne méritent pas leur place dans le top 10 des énigmes sur-entendues !
------
La suite de Conway 1
Complétez cette suite logique : 1, 11, 21, 1211, 111221, ...
------
Les cocus de Bagdad 2
L'heure est grave : le calife de Bagdad a décidé de réunir ses concitoyens : "Il y a trop de femmes infidèles dans cette ville ! Si vous veniez à apprendre que votre femme est infidèle, je vous demande de la tuer le soir même, à minuit". Il ajoute ensuite "Il y a au moins une femme adultère dans cette ville !". Chaque homme de la ville sait qui sont les femmes infidèles, sauf évidemment s'il s'agit de la leur.
Le soir même, rien ne se passe...
Le lendemain soir, non plus...
...
Le 49e soir, par contre, tous les femmes infidèles sont assassinées.
Sachant que les habitants de Bagdad appliquent au mot le paroles de leur calife et qu'ils sont de parfaits logiciens, combien y avait-il de femmes infidèles à Bagdad ?
------
Le menteur et le sage 3
C'est le jour du jugement dernier, et Saint-Pierre en a assez de décider pour vous. Vous avez alors le choix entre deux portes : l'une donne sur l'Enfer, l'autre sur le paradis. Devant ces portes, deux anges : le premier, infiniment sage, ne dit que la vérité ; le second, infiniment fourbe, ne prononcera jamais une seule vérité. Avant de faire votre choix dans la porte, vous pouvez poser une question à l'un des deux anges. Quelle question faut-il poser ?
-----
La mouche et les trains 4
Deux villes, disons A et B, sont séparées par un chemin de fer long de 1000 km (chemin de fer à une seule voie). A un moment donné, un train part de A vers B, à une vitesse de 100km/h. Au même moment, un autre train part de B vers A, à la même vitesse.
Toujours au même moment, une mouche part à 150 km/h du premier train, et commence un aller-retour interrompu entre les deux trains.
Au moment où les deux trains vont rentrer en collision, quelle distance la mouche aura-t-elle parcouru ?
-----
Le bouchon et la bouteille 5
Une bouteille et son bouchon coûtent 11€. Sachant que la bouteille coûte 10€ de plus que le bouchon, combien coûte la bouteille ?
-----
Le triangle de Curry 6
Voici deux triangles isocèles de base 10 et de hauteur 12, réalisés avec les même pièces, au détail près qu'une 7ème pièce est nécessaire dans le deuxième assemblage... D'où vient cette pièce en trop ?
-----
Le nénuphar glouton 7
Un nénuphar vit paisible dans sa mare, et double de taille tous les jours. Au 50e jour de son existence, il a déjà recouvert la moitié de sa mare, combien de temps va-t-il mettre pour recouvrir la totalité de la mare ?
-----
Coupe le cake ! 8
Comment découper un cake en 8 parts avec seulement 3 coups de couteaux ?
-----
Le trentième euro 9
Trois amis décident de passer une nuit à l'hôtel, dans une chambre
coutant 30 € la nuit. Par une habile division, chacun paye 10 € à la
réceptionniste. Les trouvant très sympathiques, elle décide de leur
offrir une remise de 5€. En bons princes, les amis laissent 2€ de
pourboire à la réceptionniste, et récupèrent 1€ chacun.
Chacun a donc payé 9€, soit (3x9) 27€, et la réceptionniste a récupéré 2€.
Puisque 27+2=29, où est passé le 30e euro ?
-----
Où est le père ? 10
Une mère a 21 ans de plus que son fils. Dans 6 ans, le fils sera 5 fois plus jeune que sa mère.
Où est le père ?
1 C'est la suite de Conway ! La solution attendue est donc 312211, et la justification est derrière le lien.
La solution 444801 était évidemment aussi acceptée, puisqu'il s'agit de la suite des valeurs prise par le polynôme P(z) = 55595/3 z3-55595 z2 + 111220/3 z + 1... Avec beaucoup de mauvaise foi, on peut justifier n'importe quelle solution à des questions du genre "complétez la suite logique"
2 Ah, le raisonnement par récurrence ! S'il n'y avait qu'un seul cocu, il aurait tué sa femme le soir même, ne voyant aucune autre femme adultère. Supposons que seulement deux hommes soient cocus (il n'y a donc pas eu de meurtre le premier soir) : chacun ne connait qu'une seule femme infidèle. Si cette femme était la seule, elle aurait été tué le premier soir : ce n'est pas le cas, ce n'est donc pas la seule, et les deux cocus assassinent leur femme le 2eme soir. De manière générale, si les règlements de comptes ont lieu le n ième soir, c'est qu'il y a n femmes infidèles. Il y avait donc 49 femmes infidèles à Bagdad.
3 "Si je demande à ton pote quelle est la porte de l'Enfer, que va-t-il me répondre ?", et de prendre ensuite l'autre porte. Il existe aussi la variante avec 3 portes...
4 Deux raisonnements permettent de trouver la solution. La première est celle utilisée par John Von Neumann (mathématicien qui a beaucoup apporté à la logique mathématique, et à tout un tas d'autre chose). Sa méthode consiste à calculer la distance parcourue par la mouche pour aller du train 1 au train 2, puis pour le retour, puis pour le re-retour, et ainsi de suite. Au final, le nombre d'aller retour sera infinie, ce qui se traduira par une somme infinie... En appelant v1 la vitesse du premier train, v2 la vitesse du deuxième, vm la vitesse de la mouche et d la distance séparant les deux villes, la distance parcourue par la mouche ressemble à peu près à :
Ce qui vaut exactement, en remplaçant par les valeurs de l'énoncé, 750 km.
La seconde solution consiste à voir que les trains vont se rencontrer après 5 heures de trajets, le temps pour la mouche de faire 750 km, avec autant d'aller-retour que nécessaire...
5 10€ ? Bien sûr que non ! 10.5€, évidemment (et le bouchon coûte 0.50€)...
6 J'avoue, j'ai menti : ce ne sont pas des triangles, et ils sont encore moins identiques ! Sur le dessin, les points A, B et C ne sont pas alignés, pas plus que les points D, E et F. La pièce noire vient des deux quadrilatères que l'on peut faire avec les points A,B,C et E (et leur symétriques), chacun d'aire 1.
Cette énigme a été crée par un neuropsychiatre américain, L. Vosburgh Lions, pour illustrer un phénomène découvert par Paul Curry.
7 Mais non, pas 100 jours, mais 51 ! On a dit qu'il doublait tous les jours !
A noter tout de même que s'il s'agit d'une mare de taille moyenne (disons, 1000 m²), le nénuphar n'aura besoin que de 39 jours supplémentaires pour recouvrir la totalité de la planète Terre... Les puissances 2, ça grimpe vite !
8 Une belle énigme à la "penser hors du cadre" !
La solution basique consiste à couper dans le cake en 4 avec deux coups de couteaux, et de faire le dernier dans le sens de l'épaisseur du gâteau !
On peut également d'arranger pour toujours couper dans le sens de la hauteur en empilant les nouvelles parts découpées en un seul tas.
Mais on peut évidemment le faire un seul coup de couteau, en pliant le cake sur lui-même !
9 Comme quoi, mal écrire le raisonnement aboutit à des absurdités ! Les 2 € du pourboire font parti des 27€ payés, les 3 restants étant ceux qui ont été rendus.
A la fin des échanges, le patron de l'hôtel a 25€, la réceptionniste 2 € et chacun des amis en a 1€. 25+2+1+1+1=30, le compte est bon !
10 Énigme sans intérêt, où la solution passe simplement par la résolution d'un système linéaire. En posant x l'âge du fils et y l'âge de la mère, on a les équations x=+1=y et (x+6)=(y+6)/5. La résolution donne x=-3/4, soit -9 mois...
Le père est dans la mère. Cette énigme était juste la preuve que l'on peut allier équations linéaires et humour graveleux !
Vous pouvez retrouver ces énigmes dans n'importe quel bon livre d'énigmes ! (Et normalement, il devrait aussi y en avoir des pas connues, mais biens quand même)
16 août 2009
Penser hors du cadre
Le puzzle des 9 points
Neuf points étant disposés en carrés, comment faire pour les relier par 4 segments sans lever le crayon ?
Si vous ne connaissiez pas le problème avant de venir ici, cherchez au moins deux minutes (et sachez que mine de rien, vous manquez un peu de culture, avec tout le respect que je vous dois ;-) )
Illustration du problème des 9 points dans Cyclopedia of 5000 Puzzles.
Ce problème est apparu pour la première fois sous le nom de "puzzle de l'œuf de Christophe Colomb" en 1914 dans Cyclopedia of 5000 Puzzles de Sam Loyd (un grand créateur de problèmes d'échecs). Ce problème est également attribué à Henry Dudeney, à qui l'on doit notamment le problème des trois maisons (trois maisons, trois usines, comment relier les maisons aux usines, toussa).
Mais si ce problème est si populaire, c'est pour son utilisation par les consultants en management (notamment de chez Walt Disney) dans les années 70, qui proposaient à leur client de résoudre le casse-tête (et leur rire au nez d'un air hautain en leur exhibant la réponse en disant "c'était facile").
La difficulté de ce problème vient des barrières que l'on s'impose, en imaginant les segments seulement entre les points dessinés. Pour résoudre le casse-tête, il faut simplement penser différemment, et sortir du cadre ("Thinking outside the box").
Pour ceux qui bloquent toujours, passons sans suspens à la solution :
Et on s'arrête à cette solution, heureux que l'on est d'avoir pensé hors du cadre ! ...
Mais cette solution reste tout de même conventionnelle et, quitte à penser hors du cadre, autant le faire vraiment. L'énoncé amène une contrainte inutile de 4 segments, alors que l'on peut facilement faire 3, voire un seul !
La solution alternative
D'un point de vue mathématique, un point n'a pas de dimension, mais, sur le dessin, les points sont de petits cercles... Détail important, puisque l'on peut utiliser l'épaisseur de ces traits pour résoudre le casse-tête en seulement 3 segments :
La solution du géomètre
Le problème est un énoncé de géométrie euclidienne : on suppose implicitement que l'on travaille sur un papier plat... Rien n'interdit de supposer que la question est posée sur une autre surface, comme une sphère ou un cylindre. La solution précédente s'adapte alors, et donne une solution en un seul trait :
La solution probabiliste
Autre solution faisant intervenir l'épaisseur des points : la solution probabiliste !
La solution expéditive
On a parlé de l'épaisseur des points, mais quid de l'épaisseur du crayon ? Allez, hop, en un seul trait !
La solution origamiste
Ma préférée : penser en trois dimensions ! Par un pliage savamment étudié, on peut aligner les 9 points, avant de tracer le coup de crayon final !
On pourrait aussi imaginer des solutions faisant intervenir la découpe du papier, ou une solution probabiliste un peu plus réfléchie, où l'on aurait soigneusement plié le papier en 9 épaisseurs... Vous en voyez d'autre ?
01 août 2009
Encore plus fort - Sprague & Grundy
Jeu des bâtonnets :
20 bâtonnets sur la table. Chacun votre tour, vous prendrez 1, 2 ou 3 bâtonnets de votre choix. Celui qui prendra la dernière aura la main brûlé.
Le jeu du tableau :
Un tableau de 4x4 cases devant vous, un pion par
case sur la première colonne. Chacun votre tour, vous déplacerez le
pion de votre choix d'autant de case que vous voulez vers la droite ou
vers le bas, plusieurs pions pouvant se trouver sur la même case. Celui
qui ne peut plus jouer sera fusillé sur place publique.
Jeu de Nim :
Plusieurs tas de pièces devant vous. Chacun votre tour, vous prenez autant de pièces que vous voulez dans le tas de votre choix. Celui qui ne pourra plus prendre de pièce sera goudronné et emplumé.
Jeu de Grundy :
Devant vous, plusieurs piles de pièces. Chacun votre
tour, vous choisirez une pile, et la couperez en deux piles de taille
inégale. Celui qui ne pourra plus jouer (puisque toutes les piles
seront de taille 1 ou 2) sera condamné à écouter l'ensemble du r'n'b
français.
Quart de singe :
Chacun votre tour, vous dites une lettre, de manière à former un mot. Si la lettre que vous donnez ne permet pas de former aucun mot, vous serez coulé dans le béton.
-
Tellement d'exemples qui permettent de se rendre compte d'une chose : dans la société d'aujourd'hui, connaître le théorème de Sprague-Grundy est devenu quelque chose de vital !...
Tous ces jeux ont un point commun, ils sont impartiaux. Autrement dit :
- Le jeu est commun à tous les joueurs : pas de secrets, pas de hasard, les mêmes pions pour tout le monde.
- Le but du jeu est d'empêcher l'adversaire de jouer.
- On ne peut faire durer indéfiniment une partie, ni terminer en match nul.
Sprague et Grundy (qui ont découvert le même théorème chacun de leur côté dans les années 30) nous apprennent ceci :
Il existe une stratégie qui permet à l'un des deux joueurs de gagner à coup sûr
Suivant la configuration de départ du jeu, l'un des joueur sera chanceux, l'autre non. Si le joueur chanceux effectue les bons coups, il pourra gagner à coup sûr, le joueur malchanceux sera de son côté forcé de suivre. Au moindre coup de travers, le joueur malchanceux peut reprendre le contrôle de la partie, et emmener son adversaire à la défaite.
On peut résumer en disant que le joueur qui ne connaît pas Sprague-Grundy perdra dans 99% des cas !...
Le jeu du graphe - Jeu des bâtonnets
Il existe une stratégie gagnante, c'est chouette... Mais quelle est-elle ? Pour le comprendre, jouons ensemble au jeu du graphe (à un pion). Tout d'abord, il faut dessiner un graphe, c'est à dire, un ensemble de "nœuds" (ou case) reliés les uns aux autres par des flèches, les arcs, permettant le déplacement des pions. On place un pion sur la case initiale du graphe (le nœud en losange) et le but du jeu est de l'amener sur la case double-cerclée. Un coup consiste à déplacer le pion d'une case à l'autre en suivant un arc du graphe. Prenons par exemple le graphe ci-dessous.
On place le pion en A, il faut l'amener en Z. Au premier coup, le joueur commençant a le choix entre B, C et D.
Grâce au théorème de Sprague-Grundy, on peut le dire : le joueur qui commence risque fort de gagner, s'il y met un peu du sien. Pour en arriver à ce résultat, il faut marquer d'un entier (appelé "nimber", excellent jeu de mot entre "Nim" et "number") chaque point du graphe en appliquant la règle du mex (minimum excluded value). Pour cela, on commence par les cases finales, qui ont un nimber de 0. Ensuite, on marque les autres cases de proche en proche, en prenant le plus petit entier non accessible depuis la case considérée. Cette définition mérite un exemple :
On commence par marquer les cases finales. Ici, on marque d'un 0 le nœud Z.
Puisque à partir de K, on peut atteindre 0 (Z), le plus petit entier non atteignable depuis K est 1. Le nimber de K est donc 1. On continue en remplissant les autres cases de proche en proche.
Le graphe entièrement rempli ressemble à ça :
Graphe des nimbers
Grâce à cette numérotation des positions, on peut depuis n'importe quelle case amener le pion sur une case de nimber inférieur. Si le pion est sur une case nulle, il sera toujours amené sur une case non nulle.
La stratégie gagnante est de s'arranger pour toujours placer le pion sur une case de nimber nul.
Ici, la position initiale n'est pas nulle (elle vaut 3). Le premier joueur a donc tout le loisir de placer le pion en B, et de se ramener à un nimber nul. Peu importe le coup de son adversaire, il continuera à placer le pion sur une case de nimber nul, jusqu'à la case Z. Victoire du premier joueur !
Le jeu des bâtonnets est exactement un jeu du graphe à un pion. 20 cases, correspondant au nombre de bâtonnets restant. La case initiale est "20", la finale est "1" et un déplacement correspond à enlever 1, 2 ou 3 bâtonnets. Les cases de nimber nul (les positions gagnantes) sont bien celles de la forme 4n+1 !
Graphe du jeu des bâtonnets et son graphe des nimbers
Le jeu du tableau
Le jeu du graphe est plutôt facile finalement : il n'y a qu'un seul pion. Mais comment faire dans un jeu comme le jeu du tableau, où il faut maîtriser 4 pions à la fois ? La solution : le jeu de Nim !
Le jeu du tableau reprend les règles de bases des jeux impartiaux : chacun son tour, on bouge un pion, le perdant est celui qui ne peut plus en bouger. On joue sur un tableau 4x4 et, depuis une case donnée, on peut bouger le pion vers la droite ou vers le bas (Le pion en A2 peut aller en A3, A4, B2, B3 ou B4). Cette fois ci, on commence avec 4 pions, tous placés sur la première colonne.
Tableau initial
Nous sommes face à un jeu impartial, il existe donc une stratégie gagnante pour l'un des joueurs. Pour découvrir laquelle, appliquons à nouveau la technique du mex. La case finale est la case D4, son nimber est donc 0. On trouve ensuite que les nimber de D3 et C4 sont 1 (Depuis D3, on ne peut aller qu'en D4. le plus petit entier non atteignable est donc 1), celui de C3 est 0, etc.
Tableau des nimbers
Cette fois ci, on ne peut plus appliquer la technique du jeu du graphe, puisqu'il y a 4 pions. Mais Sprague-Grundy ne s'arrête pas à cette première difficulté ! Il y 4 pions, certes, mais il y a surtout quatre fois 1 pion ! Au lieu de calculer le nimber d'une case, il faut calculer celui de la configuration des 4 pions. Le nimber d'une configuration se calcule facilement : c'est la nim-addition des nimbers des cases où sont les pions (Vous savez, l'addition binaire sans la retenue !)
La stratégie gagnante reste toujours la même : il faut toujours amener son adversaire dans une configuration où le nimber est nul.
Reprenons le tableau. Au début, les pions sont en position 0, 1, 2 et 3. Leur nim-addition donne 0 : c'est une position perdante pour le premier joueur ! Imaginons que J1 avance le premier pion sur la case C1. Le nimber de la configuration est alors 2⊕1⊕2⊕3≠0. En déplaçant le 4eme pion en C4, on se retrouve dans une position nulle. J2 gagnera sans problèmes la partie !
Exemple de début de partie, où J2 applique la stratégie gagnante.
fig 1 : J1 doit jouer, la configuration des pièces correspond à une configuration de Nim (0,1,2,3), de nim-addition nulle
fig 2 : J1 joue au hasard, il place son premier pion en C1. La configuration de Nim correspondante est (1,2,2,3), de nim-addition non nulle.
fig 3 : J2 rééquilibre la parité des colonnes du jeu de Nim, en déplaçant le 4eme pion en C4. La configuration de Nim correspondante est alors (1,2,2,1), la nim-addition est nulle.
Le jeu de Nim
Le jeu de Nim est l'exemple de base de jeu de graphe multi-pions. Une configuration comme (1,3,5) revient à jouer sur les tableaux suivants :
Chaque case représente le nombre de jetons restant dans une ligne. Le but du jeu est donc d'amener les 3 pions sur les 3 cases 0. Chose tout à fait étonnante (en fait, pas du tout), le nimber des cases est déjà écrit dans les cases ! La stratégie décrite pour gagner au jeu du graphe multi-pions est exactement la stratégie pour gagner à Nim : placer son adversaire dans une configuration de nimber (de nim-addition) nul ! Tout concorde !
Le jeu de Grundy
Le théorème de Sprague-Grundy peut s'avérer très utile dans les situations où le jeu se divise progressivement en plusieurs sous-jeux. L'exemple le frappant est celui du jeu de Grundy, qui se joue avec des piles de pièces. Chacun son tour, on doit choisir une pile, et la couper en deux piles de tailles inégales. Celui qui ne peut plus jouer perd.
Exemple de partie de Grundy, menée d'une main de maître par J1. Les nombres en noir correspondent au nombre de pièces dans les piles, les nombre en bleu sont les nimber des tas.
a - Le jeu commence avec 8 pièces dans la pile
b - J1 sépare la pile de 8 en une pile de 7 et de 1
c - J2 sépare la pile de 7 en une pile de 4 et de 3
d - J1 sépare la pile de 3
e - J2 n'a pas le choix, et sépare la pile de 4
f - J1 sépare la dernière pile, et gagne
On s'intéresse alors au nimber d'une pile de taille n, que l'on va noter G(n).
Si n=1 ou n=2, on trouve que G(n)=0 (on ne peut décomposer ces piles en piles plus petites de taille inégale)
Si n=3, on peut découper la pile en 1 et 2, deux piles de nimber nul, donc de nim-addition nulle. Depuis une pile de taille 3, on ne peut arriver qu'en une configuration de nimber 0, on a donc G(3)=1.
Si n=4, on peut découper la pile en 1 et 3, qui est une configuration de nimber 1 (G(1)
⊕G(3)=1). On a donc G(4)=0.
Si n=5, on peut découper la pile en [1,4] (de nimber G(1)⊕G(4)=0) ou en [2,3] (de nimber G(2)⊕G(3)=1). On a donc G(5)=2 !
Tableau des premières valeurs de G(n)
Aujourd'hui, les valeurs de G(n) ont été calculées jusqu'à n=235, mais aucune régularité n'a encore été trouvée. Peut-être est-elle périodique, ou peut-être pas...
Quart de singe
Le jeu du quart de singe est avant tout un jeu de vocabulaire, mais il peut tout à fait rentrer dans la catégorie des jeux impartiaux. Prenons par exemple pour thème "Les animaux commençant par R". Il existe 46 animaux commençant par R (auquel on ne peut ajouter de lettre pour former un autre nom). Une fois tous passés en revue, on peut dire que celui qui commence gagnera la parti, il faudra toujours jouer les lettres de nimber 0 :
En rouge les lettres de nimber nul (cliquez pour agrandir)
Supposons que vous soyez le joueur qui commence : R (nimber 0)
Votre adversaire a le choix entre 6 lettres pour former un nom d'animal, il choisit le H : Rh (nimber 2)
Il pense au rhinocéros, ce qui le ferait gagner. Heureusement, il existe un cheval qui vous fera gagner : Rhé (nimber 0)
Votre adversaire s'incline !
Théoriquement, le quart de singe se joue sans thème, sur l'ensemble du dictionnaire... On pourrait facilement faire un programme qui gagnerait à presque tous les coups à ce jeu !
La clé de la réussite appartient à celui qui sait calculer un nimber
[proverbe polonais]
Sources :
Stratégies magiques au pays de Nim - Pour la science - n°377 - Mars 2009
25 juillet 2009
Vraiment plus fort - le jeu de Nim
Le jeu des bâtonnets de Fort Boyard est maintenant bien connu : celui qui gagne, c'est celui qui laisse 1 bâtonnet modulo 4. Le gros problème de ce jeu, c'est que tout le monde sait comment gagner (ou du moins, tout le monde sait qu'il existe une stratégie gagnante), et donc, plus moyen de proposer des paris gagnés d'avance.
C'est sans doute pour cela que le fan-tan a été inventé il y a bien longtemps par les Chinois : un jeu gagné d'avance pour celui qui le propose, mais qui n'y paraît pas !
Pour jouer à ce jeu, vous devez disposer de pièces, de jetons, d'allumettes, de cailloux, de grenouilles ou de n'importe quel petits objets manipulables. On présente les jetons en ligne, chaque ligne possédant un nombre différent de jetons (ou pas). Il s'agit d'un jeu à deux participants, au tour par tour. Lorsque c'est à votre tour de jouer, vous choisissez l'une des ligne, et prenez autant de jetons que vous le souhaitez dans cette ligne (même tous les jetons de la ligne si vous le souhaitez). Celui qui prend le(s) dernier(s) jeton(s) de la dernière ligne gagne la partie.
Vous pouvez y jouer en ligne contre l'ordinateur ici.
Exemple de partie, avec 3 lignes de jetons (1, 3 et 5 jetons). Ici, J1 n'est qu'un manipulateur qui n'a laissé aucune chance à sa victime.
Alors que les Africains l'appellent "Tiouk-tiouk", on connait aujourd'hui ce jeu sous le nom de "jeu de Nim", donné par le mathématicien américain Charles Bouton, en 1901. Le mot "Nim" provient de l'allemand "Nimm" qui signifie "prends"... à moins que cela vienne de l'ancien anglais "Nim" signifiant la même chose... Ou alors, il s'agit de "WIN" écrit la tête à l'envers... L'origine du nom reste obscure, en fait !
Son étude, par contre, n'a rien d'obscure, puisqu'il a complètement résolu le jeu. Pour gagner à ce jeu, il faut connaître les deux secrets : le théorème de Bouton et la maîtrise du XOR mental ! (alias nim-addition)
Par la suite, j'appellerai "configuration" d'un jeu de Nim la liste des nombres de jetons. L'exemple d'au-dessus commençait dans la configuration (1,3,5).
Le théorème de Bouton est le suivant : un joueur qui se trouve dans une configuration dont la nim-addition est non-nulle peut appliquer une stratégie lui assurant la victoire.
Prenons le cas de l'exemple, qui commence par la configuration (1,3,5), sa nim-addition est 7 : puisque J1 commence dans une configuration gagnante (sa nim-adddition n'est pas nulle) et qu'il connaît parfaitement le truc, il n'a eu aucun mal pour gagner !
Reste la question : pourquoi 1⊕3⊕5=7 ?
Pour faire la nim-addition de 1, 3 et 5, il faut simplement poser l'addition, au détail près qu'il faut la faire sans les retenues, et en binaire !
Concrètement, il faut commencer par écrire les nombres sous forme binaire, c'est à dire, trouver sa décomposition en somme de puissances de 2 (1, 2, 4, 8, 16, 32...). Par exemple, le nombre 6 s'écrit 6=4+2, et s'écrit en binaire 110.
On trouve alors que 1 s'écrit 1, 3 s'écrit 11 et 5 s'écrit 101.
Il suffit donc ensuite de poser l'addition, toujours en base 2 et sans les retenues (poser l'addition en admettant que 1+1=0). On peut travailler par colonne : s'il y a un nombre pair de 1, le résultat est 0, sinon, le résultat est 1.
1 (1)
+ 1 1 (3)
+ 1 0 1 (5)
________
1 1 1 (7)
On repasse ensuite le résultat en décimal : on trouve bien que 1⊕3⊕5=7.
On peut calculer également la nim-addition de la configuration (1,3,2) : 1⊕3⊕2=0.
(Pour les flemmards, la calculatrice de Windows fait très bien le travail avec la touche XOR)
Il y a alors deux types de configurations : les non-nulles (comme (1,3,5)) et les nulles (comme (1,3,2)). Les non-nulles sont les gagnantes, les nulles sont les perdantes. En enlevant le bon nombre de jetons de la bonne ligne, on peut toujours passer d'une configuration non-nulle à une configuration nulle ; et quelque soit le nombre de jetons que l'on enlève à une situation nulle, elle devient non nulle.
La stratégie gagnante consiste donc à toujours faire en sorte que l'adversaire ait une configuration nulle, ce qui est toujours possible.
Tout ça, c'est de la théorie. Dans la pratique, lon ne cherche qu'à savoir si la nim-addition sera nulle ou non. Les choses sont plus faciles à manipuler : la règle d'or est de "réparer les colonnes".
Pour cela, il faut se matérialiser la décomposition binaire des lignes de jetons en disposant mentalement les jetons par paquets dans des colonnes. Il y aura alors une colonne de paquets de 1, une colonne de paquets de 2, une colonne de paquets de 4 etc.
Par exemple, il faut voir la configuration (1,3,5) de la façon suivante :
Décomposition binaire de la configuration (1,3,5)
On se matérialise ainsi la Nim-addition. Puisqu'il y a au moins une des colonnes qui possède un nombre impair de tas (Dans le cas précis, elles sont toutes dans ce cas), la nim-addition n'est pas nulle.
Il faut donc annuler la nim-addition. Pour cela, il faut "réparer les colonnes", c'est à dire, trouver un moyen pour que chaque colonne ait un nombre pair de paquets (ce qui n'est pas forcément évidement.) Dans notre cas, enlever 3 jetons de la dernière ligne fait l'affaire. On obtient alors la configuration (1,3,2), qui est une configuration perdante pour l'adversaire.
Il faut enlever 3 jetons de la dernière ligne pour se ramener à une situation perdante
Il est maintenant temps de s'entrainer ! Nous sommes dans la configuration (12,8,7,4,1). Est-il préférable que vous jouiez en premier et, si oui, que jouer ?
Solution :
Il faut commencer ! Plusieurs solutions s'offrent alors :
(A) - retirer 2 jetons à la ligne 1
(B) - retirer 6 jetons à la ligne 3
(C) - retirer 2 jetons à la ligne 4
Pour trouver ce résultat, il faut considérer la la décomposition binaire en paquet :
Avant
La colonne (8) et la colonne (1) contiennent un nombre pair de paquets, on ne touchera donc ni à la 2eme, ni à la dernière ligne. Il faut donc chercher à parifier les deux autres colonnes. Pour cela, deux solutions s'offrent : on peut tenter d'avoir 2 paquets par colonnes en décalant les paquets de 4 de la ligne 1 ou 4 (solution (A) ou (C)) ou bien d'avoir 2 paquets dans la 2ème colonne, et aucun dans la troisième, en enlevant le trop plein de la ligne 3 (solution (B)).
Après - solution (B)
Un peu d'entraînement, et, à vous les paris gagnés d'avance !
Sources :
Stratégies magiques au pays de Nim - Pour la science - n°377 - Mars 2009
18 juillet 2009
Toujours plus fort - Le jeu des bâtonnets
Vous sortez de la star Academy, votre single "Toi ma lova yeah" a fait un carton, on ne parle plus que de vous ! Pour votre image, vous acceptez de parrainer une association qui réalise les rêves d'enfants handicapés (nager avec les dauphins, toussa). Sans même savoir pourquoi, vous acceptez de participer à Fort Boyard pour défendre les couleurs de cette association. Pour votre réputation, c'est tout ou rien : vous remportez le jackpot, gagnez en sympathie auprès du public et rempilez tout de suite pour un nouvel album, ou bien, vous vous plantez monumentalement, et du jour au lendemain, vous redeviendrez serveur dans un bar.
Seulement 5 clé en votre possession, très peu d'indices, l'émission est mal partie. Pour espérer gagner un minimum, il faudra un maximum de temps dans la salle aux trésors. Tout va donc se jouer dans la salle du conseil... A votre tour de passer : votre défi contre le maître du temps sera le jeu des bâtonnets :
"Face à vous, 20 bâtonnets. Chacun votre tour, vous pourrez en retirer 1, 2 ou 3. Celui qui tire le dernier bâtonnet perd le duel, c'est à vous de commencer à jouer".
Le duel se déroule de la façon suivante :
(20) Vous en retirez : 1 - reste 19
(19) Le maître en retire : 2 - reste 17
(17) Vous : 1 - reste 16
(16) Le maître : 3 - reste 13
(13) Vous : 2 - reste 11
(11) Le maître : 2 - reste 9
(9) Vous : 3 - reste 6
(6) Le maître : 1 - reste 5
(5) Vous : 1 - reste 4 (Vous comprenez à ce moment là que vous êtes foutus)
(4) Le maître : 3 - reste 1
(1) Vous : 1 - reste 0 : vous avez perdu
Le duel est raté, votre équipe perd le moral, vous ne trouvez pas le mot-code, vous passez à côté du jackpot.... Les enfants handicapés vous en veulent, votre maigre réputation en prend un coup et votre carrière est ruinée. Le lendemain, vous pointez à l'ANPE. Fin.
Ce drame, pourtant, vous auriez pu l'éviter ! Il aurait suffit de réfléchir un peu... Pour le comprendre, essayons de remonter au coup que vous avez mal joué.
Configuration (1)
Configuration (1) : il y a un seul bâtonnet en jeu, et c'est à vous de jouer. Vous n'avez pas le choix, vous le prenez : vous avez perdu. La situation (1) est une configuration de perte.
Configuration (5) : 1+4
Configuration (5) : il y a 5 bâtonnets en jeu, et c'est à vous de jouer. Trois choix s'offrent à vous : prendre 1, 2 ou 3 bâtonnets. Dans tous les cas, votre adversaire pourra vous ramener à la configuration (1), en prenant respectivement 3, 2 ou 1 bâtonnet. La situation (5) est donc aussi une configuration de perte.
Configuration (9) : 1 + 2x4
Configuration (9) : de la même façon, peu importe le nombre de bâtonnet que vous prenez, votre adversaire vous ramènera à la configuration de perte (5), en faisant en sorte que 4 bâtonnets soit retirés. Plus généralement, toute configuration de la forme (4n+1) (des paquets de 4 plus une) est une configuration de perte : quiconque se retrouve dans cette situation sera amené à perdre.
Configuration (20) : 1+4x4+3
Configuration (20) : Vous commencez à jouer. Cette configuration n'est pas de la forme (4n+1), ce n'est donc pas une configuration de perte, mais vous pouvez amener votre adversaire dans une situation de perte. Quel est le plus petit nombre inférieur à 20 de la forme 4n+1 ? C'est 17 (1+4×4). Prenez donc 3 bâtonnets !
A partir de là, c'est vous qui contrôlez le jeu : s'il prend 1, 2 ou 3 bâtonnets, prenez en respectivement 3, 2 ou 1. Vous vous assurez que votre adversaire reste toujours dans une configuration de perte jusqu'à la fin du jeu.
De façon plus générale, si vous commencez à jouer avec un autre donné de bâtonnets (qui n'est pas de la forme 4n+1), il faut faire en sorte au premier coup qu'il en reste un nombre de la forme 4n+1 (en comptant les bâtonnets par paquets de 4). Si vous commencez dans une situation perdante, il y a juste à espérer que votre adversaire ne connaisse pas le truc, et il faudra profiter d'un coup hasardeux pour que le jeu vous redevienne favorable.
Les jeux impartiaux
Le jeu des bâtonnets est un jeu que l'on classe dans la catégorie des jeux impartiaux : un jeu ne faisant pas intervenir le hasard (pas de lancé de dé, de cartes), qui ne peut pas se terminer en match nul (les échecs n'est pas un jeu impartial) et où le but est de placer l'adversaire dans une situation où il ne peut plus jouer. (Ou, dans le cas du jeu des bâtonnets, d'être le joueur qui ne peut plus jouer). Le jeu des bâtonnets est un jeu impartial, et de nombreuses techniques ont été développé pour gagner à coup sûr à ce genre de jeu.
Un jeu impartial est toujours équivalent à un jeu de déplacement sur un graphe. On place un pion sur la case initiale du graphe, le but étant de lui faire atteindre une position finale. Chacun leur tour, les joueur doivent déplacer le pion le long d'une arrête du graphe.
Prenons comme exemple le jeu des bâtonnets, avec 12 bâtonnets Les 12 sommets du graphe correspondent aux 12 configurations du jeu (de 12 à 1 bâtonnets restant). La case initiale sera la configuration (12), et la finale sera la configuration (1). Les déplacement sur le graphe correspondent à retirer 1, 2 ou 3 bâtonnets. Le but du jeu est d'amener le pion sur la position 1.
Graphe du jeu des bâtonnets
La stratégie pour gagner à ce type de jeu est de retrouver les positions gagnantes, que l'on appelle "noyau" du graphe. Ce noyau, ce sont les cases du graphe que l'on peut atteindre depuis n'importe quelle autre case, et jamais reliées l'une à l'autre. Dans le cas du jeu des bâtonnets, ce sont les cases correspondant aux positions (1), (5) et (9) (On peut vérifier facilement que l'on peut atteindre l'une de ces 3 cases depuis n'importe quelle autre case).
Pour son premier coup, le premier jouer a donc tout intérêt à retirer 3 bâtonnets, pour se retrouver en configuration (9). Peu importe le coup du deuxième joueur, on pourra atteindre la configuration (5), et donc la configuration (1) !
La prochaine fois que vous irez à Fort Boyard, vous saurez... A moins que vous inauguriez un nouveau type de duel, variante d'une jeu de Nim, et vous échouerez lamentablement, puisque je manque de temps pour les aborder dans mon article de cette semaine... La suite, la semaine prochaine !
Sources :
Interstices - Jeux de Nim (d'où proviennent les illustrations des graphes)
19 avril 2009
Carré au scalpel
Aujourd'hui, pour célébrer la fermeture de la BU qui m'a empêché de faire un article ce week-end, voici un petit problème récréatif tout simple, qui a le seul mérite de m'avoir fait chercher trop longtemps.
Le problème est le suivant : comment découper un carré en triangles acutangles (les 3 angles de ce triangle sont aigus, strictement inférieur à 90°) qui ne se chevauchent pas ?
Le temps que vous griffonniez des carrés découpés en triangles acutangles, histoire de trouver la solution avant que je la donne, une petite interlude musicales
=== Interlude ===
=== /Interlude ===
Avant de s'atteler à la découpe du carré, on peut se poser la question de la découpe du triangle obtus, qui donne tout de suite une solution universelle. Celle-ci, en 7 ou 8 morceaux, se révèle plutôt simple (et ingénieuse). Si le triangle ABC est obtus en B, on trace le cercle de rayon OB centré en O, où O est le centre du cercle inscrit (point de concours des bissectrices). Ce cercle coupe le triangle en 5 points, découpant le triangle obtus en 5 triangles aigus.
Découpe d'un triangle obtus en 7 triangles acutangles
Cette solution ne marche pas pour tous les triangles obtus, puisqu'il faut que les angles B-A et B-C soient inférieurs à 90°. Si l'un de ces deux angles est trop grand, il faut prendre un point D sur AC, et tracer BD. En plaçant bien le point D, on peut appliquer la construction précédente au nouveau triangle obtus BDC :
Découpe d'un triangle obtus en 8 triangles acutangles
Grâce à cette construction, on peut aboutir facilement à une découpe du carré en 10 ou 11 morceaux :
Carrés découpés en 10 et 11 triangles acutangles
Évidemment, cette astuce ne marche pas pour les solution optimales à 8 et 9 morceaux. Pour la découpe en 8 morceaux, l'astuce consiste à diviser le carré en deux rectangles égaux, puis à y tracer les deux demi-cercle d'un des rectangles. En plaçant un point à l'extérieur des demi-cercle, on retrouve facilement le découpage :
Découpe du carré en 8 triangles acutangles
A noter que la découpe en 8 triangles est minimale. Le découpage à 9 triangles est finalement le plus difficile à trouver : on y retrouve un pentagone, mais aucun triangle obtus :
Découpe du carré en 9 triangles acutangles
Ce problème (qui ne restera pas gravé dans l'histoire des mathématiques) possède tout de même deux subtilités notables :
- Parmi les dissections présentées ici, seule la découpe en 8 triangles est une triangulation au sens topologique. En effet, c'est la seule découpe où aucun sommet ne tombe sur le côté d'un autre. La triangulation en triangles acutangles se pose alors. On connaît la solution en 8 pièces (c'est la même), on en connaît en 10 ou 11 morceaux, mais on n'en connaît aucun en 9 morceaux. En fait, on a même démontré qu'il n'en existe aucune !
- Tout problème en deux dimensions doit se poser en dimensions supérieur : comment découper un cube en polyèdres dont chacune des faces est un triangle acutangle ? La réponse, cette fois-ci, est inconnue ! Si une telle découpe existe, elle doit être d'une difficulté déconcertante ; si aucune découpe n'existe, il ne reste plus qu'à le démontrer, ce qui ne semble pas bien évident non plus.
Sources :
Martin Gardner - Pour la Science n°47 - septembre 1981
12 avril 2009
Becotages au pays des sphères
De quoi pourrais-je parler sur ce blog pour fêter Pâques ?... J'aurais pu parler des courbes en cloches, 11 jours après la journée de la loi de Poisson, et ainsi célébrer le mois de la probabilité, mais finalement ça sera pour l'année prochaine. Non, Pâques, c'est plutôt les œufs ! Et comme les œufs sont presque des sphères, c'est la journée idéale pour parler de sphères !
La treizième sphère
1854 : gros débat entre Gregory et Newton, à propos du grave problème du nombre d'embrassade des sphères ("kissing number").
A ma droite, Isaac Newton, physicien anglais découvreur de la gravitation universelle, et mathématicien inventeur du calcul infinitésimal (et plein d'autres trucs), soutient que l'on ne peut mettre que 12 sphères autour d'une sphère donnée.
A ma gauche, David Gregory, mathématicien et physicien écossais, inventeur (théorique) du télescope qui porte son nom, soutient que l'on peut glisser une 13e sphère !
Retour en dimension deux, pour comprendre le problème : étant donné un disque, combien peut-on placer de disques tangents au premier ne se recoupant pas. On peut expérimenter facilement la question avec des pièces de monnaies, et la réponse se trouve facilement. En effet, une fois 6 pièces posées autour de la première, on s'aperçoit que chaque pièce est tangente à ses voisines, ce qui ne laisse aucune place libre pour une septième pièce. On remarque que les centres se placent sur un hexagone régulier.
6 cercles embrassant, placés aux sommets d'un hexagone
L'objet de la querelle se passe en dimension 3. C'est maintenant aux balles de ping-pong que l'on s'intéresse : combien de balle peut-on placer autour d'une balle donnée. On peut procéder de la même façon que pour le cas à deux dimensions : par l'expérimentation !
12 sphères, placés sur les sommets d'un icosaèdre
On peut facilement placer 12 boules autour de la boule centrale, mais, contrairement au problème à 2 dimensions, les boules ne sont pas tangentes les unes aux autres, il reste de la place entre les boules ! Peut-être qu'avec un peu d'astuce, on pourrait réussir à placer les boules de manière à ce qu'il reste suffisamment de place pour en placer une treizième ? C'est ce que soutient Gregory !
Il appuie sa position sur sur le fait que le rapport entre l'aire d'une calotte sphérique et celle de la sphère vaut 14,9... Explications (en deux dimensions, c'est plus simple !) :
Plaçons deux cercles de même rayon côte à côte, tangents. En se plaçant au centre du premier cercle, on voit le deuxième cercle sous un angle de 60°. Si le cercle est de rayon 1, l'arc de cercle délimité par l'angle (la calotte) aura une longueur de π/3. La longueur totale du cercle étant de 2π, on peut voir que l'on peut placer au maximum 2π/(π/3))=6 cercles autour du premier. Puisqu'une configuration à 6 cercles a été trouvée, c'est que cette configuration est maximale !
Retour en 3 dimensions. Depuis le centre d'une sphère (simplifions : de rayon 1), une deuxième sphère tangente sera vue dans un cône d'angle 60°. On peut également calculer l'aire de la surface de la calotte, qui vaut ici (2-√3)π (environ 0.2679π). L'aire de la surface de la sphère est de 4π, et 4/(2-√3) ≈ 14.92. Ce calcul montre que l'on peut placer au maximum 14 surfaces d'aire (2-√3)π sur le pourtour de la sphère ; on peut potentiellement placer 14 calotte autour de la sphère, ie, 14 sphères autour de la sphère !
Cette démonstration ne permet pas de donner le nombre maximum de sphère répondant au problème, mais permet au moins d'en donner une limite supérieure. Gregory ne croit pas vraiment aux 14 sphères, mais pourquoi pas 13 sphères ?
≈≈≈≈≈≈≈
Admirez la richesse des effets spéciaux !
De l'eau a coulé sous les ponts, et c'est au XXe siècle que de nouvelles démonstrations tombent. De nombreuses incomplètes, jusqu'en 1953, où Bartel et Schütte publient la première preuve notable, donnant raison à Newton. Avec ces preuves, on est sûr d'une chose : il ne peut y avoir 14 sphères s'embrassant autour d'une autre. C'est pour éliminer la treizième sphère que les choses se corsent, mais la démonstration est bonne si on ne se plonge pas dans les détails. De nombreux auteurs ont revu la démonstration en l'améliorant, mais il n'existe aucune preuve 100% vérifiée que la conjecture de Newton est correcte (mais on en est quand même plutôt proche !)
Pourquoi avoir mis autant de temps pour résoudre ce problème ? Contrairement au problème en 1ere ou 2eme dimension, les sphères autour de la sphère centrale ne sont pas rigide, et disposent chacun d'un petit espace où glisser. On dispose donc d'une infinité de possibilité de placer les 12 sphères. On peut notamment les placer sur les sommets d'un icosaèdre (polyèdre à 20 faces triangulaires) ou d'un cuboctaèdre (polyèdre à 14 faces : 6 carrés, 8 triangles équilatéraux) :
A gauche, l'icosaèdre ; à droite, le cuboctaèdre
Comme très souvent, quand les mathématiciens bloquent sur un problème, ils essaient d'en résoudre un plus difficile (ça permet souvent de statuer sur les cas particuliers). Dans ce cas là, c'est le problème équivalent dans les dimensions supérieures qui sont intéressantes. Je ne parle pas du problème en dimension 4, 5, 6 ou 7, puisque le problème est toujours ouvert (on ne dispose que d'encadrements), mais en dimension 8, les choses sont meilleures...
En effet, le problème en dimension 8 (résolu à la fin du XIXe siècle) est d'une incroyable facilité comparé à la troisième dimension : le plus grand réseau que l'on peut faire autour d'une sphère centrale est de 240 sphères ! Encore une fois, c'est la rigidité de la construction qui permet de trancher : le 8-polyèdre donnant le réseau à 240 sphères est unique, et c'est toujours plus facile de reconnaître une réponse quand elle est unique !
Pour l'anecdote, les 240 sphères sont de rayon √2, et les centres des sphères sont positionnées aux points ayant des coordonnées de la forme (0,0,0,±1,±1,0,0,0) (deux 1 en n'importe quelle position et de n'importe quel signe) et (±½,±½,±½,∓½,∓½,∓½,∓½,∓½) (un nombre impair de signes -).
Ce réseau est la base du groupe de Lie E8, un objet fondamental de la théorie des groupes en algèbre, décodé en mars 2007 ; ses applications ne sont pas encore connues, mais il est certain qu'elles auront d'énormes retombées pratiques dans le domaine de l'informatique, la physique, la chimie et de tous les domaines des mathématiques !
On connaît également la solution exacte pour la dimension 24 : c'est un réseau qui comporte 196 560 sphères !
Sources :
La treizième sphère (Marcel Berger) - Octobre décembre, Pour la science/Dossier n°41
10 janvier 2009
Ca vous défrise ?
(Jj - "5 ans et demi", classe de CP)
Après avoir recopié du mieux que je pouvais 6 fois la lettre "a" en attaché, la maîtresse nous laissait une liberté : dessinez une frise en bas de la page !
(Jj - "5 ans et demi", 3 jours plus tard)
A l'époque, le concept de la frise, c'était pour moi un motif qui se répète sur une ligne. Au cours de mon premier mois de prépa, toutes mes frises se ressemblait plus ou moins, jusqu'au jour où j'ai innové :
(Jj - "5 ans et demie", 1 mois plus tard)
La grande innovation, c'est que je venais de briser la symétrie ! Dans cette nouvelle frise, il n'y a plus que des translations ! Je ne m'en étais pas encore rendu compte, mais c'est surement à partir de ce jour là où j'ai compris qu'il existait plusieurs groupes cristallographiques distincts de frises !
Avant tout, définissons une frise un peu plus formellement : une bande de papier, c'est que que l'on trouve entre deux droites parallèles dans un plan. Sur cette bande, un dessin D est fait (un dessin, c'est simplement un sous-ensemble des points de la bande). On dit que D est une frise si on peut trouver une translation qui ne bouge pas la frise (Répétition d'un motif).
Quelle est exactement le point commun entre les deux premières frises, et qui la différencie de la troisième ? Leur groupe cristallographique, évidement !
Les isométries
Une isométrie, rappelons-le peut-être, est une transformation qui "bouge" un objet sans modifier ses proportions (qui conserve les distances). Dans le plan, il n'en existe que 4 type :
- La translation (De vecteur donné)
- La rotation (De centre et d'angle donné). Ce que l'on appelle "symétrie centrale" est en fait une rotation, dont l'angle vaut un angle plat.
- La symétrie axiale (D'axe donné)
- La symétrie glissée (D'axe et de vecteur donné), moins connue. Elle s'obtient en effectuant d'abord une symétrie axiale, puis en effectuant une translation dont le vecteur est dans la même direction que l'axe.
Et ces différentes isométries, on peut les retrouver dans nos frises.
La translation se retrouve obligatoirement dans toutes les frises (par définition)
La symétrie se retrouve dans mes deux premières frises : ce sont des symétries d'axe horizontale.
Groupe cristallographique
On appelle "groupe cristallographique" d'une frise l'ensemble des isométries que l'on peut trouver dans cette frise (Quand je dis "que l'on peut trouver", ce sont les isométries qui laissent le dessin invariant). Prenons par exemple cette frise de WOUF :
En cherchant un peu, on trouve :
- Des translation (de vecteur horizontal)
- Des centres de symétries centrales (des rotations)
- Des symétries axiale : une d'axe horizontal et un tas d'axes verticaux
- Des symétries glissées (puisqu'il il y a une symétrie d'axe horizontal et des translation)
Le groupe cristallographique de cette frise est donc composé des translations, symétries centrales, symétries axiales verticales, horizontales et glissées.
Finalement, on peut définir une frise seulement à partir de son groupe d'isométries. Quelles sont les isométries que l'on peut à priori trouver dans une frise ? Il faut réfléchir aux isométries qui vont laisser la bande de papier tranquille (On supposera que la bande est horizontale):
- Des translations ? Il nous la faut forcément de vecteur horizontal !
- Des rotations ? Seule la symétrie centrale est une rotation acceptable, et son centre doit être sur l'axe horizontal de la bande !
- Des symétries axiales ? Seules les symétries d'axes verticaux ou horizontaux sont acceptés, et pour ce dernier, le seul axe accepté est l'axe de la bande !
- Des symétries glissées ? Il faut que son axe soit celui de la bande !
Moralité : dans un groupe cristallographique, on peut avoir, au choix :
- Des translations
- Des symétries d'axe verticaux
- Des symétries (glissées ou non) d'axe horizontaux (de même axe que la bande)
- Des symétries centrales (le centre étant sur l'axe de la bande)
Et quand on prend deux transformations, la composée des deux sera forcément dans le groupe également. par exemple, si on a une translation et une symétrie horizontale, on aura forcément une symétrie glissée.
Les n types de frises
Combien de types de frises sont possibles ?...
Maintenant que l'on sait ce que l'on peut mettre dans notre groupe cristallographique, il n'y a plus qu'à expérimenter. On va adopter la notation des cristallographes, qui notent les groupes sous la forme px1x2x3 :
p : le premier caractère est p si le groupe contient des translations (ce qui est toujours le cas, c'est le b.a.-ba des frises !)
x1 : ce caractère est m s'il y a des symétries d'axe verticaux, et 1 sinon
x2 : ce caractère est m s'il y a des symétries d'axe horizontaux, a si elles sont toutes glissées et 1 sinon
x3 : ce caractère est 2 s'il y a des symétries centrales, et 1 sinon.
Cela donne à priori 12 configurations possibles, mais certaines vont s'avérer impossibles
* pmm2 (Translations, symétries verticales, symétrie horizontale, symétries centrales)
* pmm1 (Translations, symétries verticales, symétrie horizontale)
Impossible ! Si on a une symétrie verticale et une symétrie horizontale, on aura forcément la composée des deux, c'est à dire, une symétrie centrale !
* pma2 (Translations, symétries verticales, symétries glissées, symétries centrales)
* pma1 (Translations, symétries verticales, symétrie glissées)
Impossible ! Quand on fait dans l'ordre une symétrie horizontale glissée, une symétrie verticale et une translation, on peut se retrouver avec une symétrie horizontale non glissée !
* pm12 (Translations, symétries verticales, symétries centrales)
Impossible ! Comme dans le cas précédent, la composée des trois risque de donner une symétrie horizontale.
* pm11 (Translations, symétries verticales)
(Les deux premières fraises de l'article sont de ce type)
* p1m2 (Translations, symétrie horizontale, symétries centrales)
Impossible ! Symétrie d'axe horizontale + symétrie centrale = symétrie d'axe vertical.
* p1m1 (Translations, symétrie horizontale)
* p1a2 (Translations, symétries glissées, symétries centrales)
Impossible !
* p1a1 (Translations, symétrie glissées)
* p112 (Translations, symétries centrales)
* p111 (Translations)
Cela donne donc 7 frises possibles ! A présent, sortez tous vos cahiers de primaires, et comparez votre niveau de créativité !
Sources :
Tangente, les transformations de la géométrie à l'art (HS n°35)
03 janvier 2009
Et la lumière fut
(Il convient, avant tout autre chose, à vous souhaiter une très bonne année 2009 ! (Car, est-il bon de le rappeler, 2009 est divisible par 7, et 7, ça porte bonheur ! Si si !). Passons à présent à un article qui n'a absolument aucun rapport !)
La chambre de Penrose
Au matin du deuxième jour, Dieu dit "Que la lumière soit". Et comme Dieu est super fort, la lumière fut !... Sauf dans la chambre de Penrose !
Dans les années 50, Ernst Straus remarqua que quand on recouvrait une pièce de miroirs et que l'on allumait une bougie quelque part, toute la pièce était éclairée, peut importe la forme de la pièce et la position de la bougie. Pour vraiment n'importe quelle pièce ?...
St
rauss posa alors les deux questions suivants :
- Existe t'il une forme de chambre inilluminable depuis un point précis : si une bougie se trouve à ce point-ci, il restera des zones d'ombres ? (1)
- Existe t'il une forme de chambre inilluminable depuis n'importe quel point : peu importe où la bougie se trouve, il restera des zones d'ombres ? (2)
On dit qu'une pièce est illuminable depuis une source lumineuse, si on peut arriver à n'importe quel autre point de la pièce par réflexions. Par exemple, dans cette chambre en L, on peut arriver au point M depuis la source S par réflexion. Peu importe la position de S et de M, on pourrait trouver un chemin par réflexion.
Les questions ne sont pas restées longtemps sans réponse, puisqu'en 1958, Penrose trouva une solution, à base d'ellipses, solution qui répond aux deux questions à la fois (Ici, peu importe la position de la lampe (en jaune), il restera toujours au moins une zone d'ombre) :
La chambre de Tokarsky
Mais cette solution n'est pas complètement satisfaisante : il y a des arcs d'ellipses ! Et si on cherchait à répondre à la question en considérant seulement des polygones ?
Il faudra attendre 1995 pour avoir enfin des bribes de réponse pour cette question : il existe bien des pièces polygonales où certains emplacement de lampe empêcheront d'illuminer totalement la pièce. La chambre trouvée est une chambre à 26 murs. Une pièce à 24 murs, partageant les mêmes propriétés, a été découverte 2 ans plus tard par Castro. En voici les plans :
En plaçant une bougie (ponctuelle) sur l'un des point rouge de la chambre de Tokarsky ou de Castro, il restera effectivement des zones d'ombres. Mais il y a un petit hic : si on déplace un tout petit peu la bougie, la pièce sera à nouveau entièrement éclairée ! Si on considère une bougie non ponctuelle, la question reste à l'heure actuelle toujours ouverte !
Dans le cas polygonal, la question 2 est également toujours ouverte ! Avis aux amateurs !
Sources :
Illumination Problem.html, depuis MathWorld (D'où proviennent les illustrations de l'article)
13 décembre 2008
Prendre le bon pli
Pendant de très nombreux siècles, les mathématiciens se sont cassé les dents sur 4 problème de géométrie, qu'il faut résoudre à la règle et au compas (les plus précis des instruments de géométrie)...
- Diviser un angle donné en 3 anges donnés (trisection de l'angle)
- Pour un cube donné, tracer la base d'un cube ayant un volume double (duplication du cube)
- Pour un cercle donné, tracer un carré ayant une aire égale au cercle (quadrature du cercle)
- Tracer un heptagone régulier (problème des polygones réguliers)
... jusqu'à ce qu'un petit malin (Pierre-Laurent Wantzel, pour ne pas le nommer) démontre que tout ça est impossible : à la règle et au compas, on ne peut tracer que des nombres qui peuvent s'écrire avec des racines carrées, ce qui n'est pas le cas de tout ce que l'on devrait tracer dans ces 4 problèmes.
Mais un mathématicien qui n'arrive pas un problème s'arrange toujours pour y répondre, quitte à utiliser une certaine mauvaise foi : "Qui a dit que l'on avait pas le droit de plier le papier ?".
Même plus besoin de règle ni de compas, on peut résoudre tous les problèmes avec seulement des pliages !
La trisection de l'angle
En supposant que l'angle est tracé sur le bord de la feuille (ici, on considère l'angle formé entre le bas de la feuille et la droite d)
- On commence par replier le bas de la feuille pour former les droites h0, h1 et h2.
- On plie la feuille la feuille de manière à ce que le point A atteigne h1 et que B atteigne d
- Il n'y a plus qu'à tracer AA', qui trisecte l'angle, l'autre trisectrice n'est pas difficile à obtenir.
Il est également possible de faire en pliage la quintisection de l'angle, mais c'est un peu plus ardu !
La duplication du cube
Pour dupliquer un cube, il faut simplement savoir tracer la proportion ³√2. En effet, si un carré est tracé, on considère que son côté est l'unité. Le volume du cube est alors de 1. Pour construire un cube de volume 2, il nous faut juste tracer son côté, de longueur ³√2.
On peut résumer rapidement le pliage à faire :
Il faut préalablement couper la feuille carrée en 3 bandes égales, ce que l'on fait ainsi :
Une fois que l'on a trouvé ³√2 comme rapport entre 2 longueurs, on peut dupliquer le cube de côté 1 facilement (le 1 qui a été construit). Pour un côté quelconque, il suffira de reporter le rapport (grâce à Thalès).
L'heptagone régulier
Comment partager une (grande) crêpe entre 7 convives affamés ? Impossible à faire avec l'association règle-compas seulement ; mais le bon côté de la crêpe, c'est qu'on peut la plier très facilement !
Voici la démarche à suivre pour aboutir à cet heptagone, et ainsi, partager n'importe quelle crêpe entre 7 personnes ! (Parce que si vous pliez votre tarte aux litchis, vos invités risquent e faire la gueule)
- On commence par se donner un repère, puis on positionne les points A(-0.5,1) et B(1,0).
- On plie de manière à ce que le point A soit sur Ox et que B soit sur Oy. On note V le point où tombe B.
- On trace la droite Δ, médiatrice de VO
- On plie de telle façon que le pli passe par O et que B tombe sur la droite Δ. Le point d'arriver est K.
- L'angle φ, formé par VOK, représente alors 1/7 de cercle ! En reportant cet angle, on peut découper facilement la crêpe !
La quadrature du cercle
Les pliage, c'est vrai que c'est génial, mais on ne peut quand même pas faire tout ce que l'on veut ! Il reste des choses impossibles à faire, notamment la quadrature du cercle. Il existe cependant un moyen de s'approcher de 4π/3 quand même, moyennant un origami assez technique...
Sources :
Origami and Geometric constructions [pdf] (Illustration de la partie duplication du cube)
Résolution par le pliage de l'équation du 3eme degré [pdf](Justification de la construction de l'heptagone)