Les pavages dorés

Drapeau vert : Cet article ne demande aucune connaissance mathématique particulière


Une envie subite de refaire votre papier peint ou le carrelage de votre salle de bain ? En perfectionniste que vous êtes, vous exigez cependant de n’utiliser que des polygones réguliers pour votre décoration.

Pour satisfaire vos envies, vous pourrez peut-être opter pour un pavage carré. Après tout, dans carrelage, il y a la racine du mot carré, alors quoi de plus naturel que de disposer régulièrement ces quadrilatères dans votre nouvelle pièce.

Plus original, vous pourrez choisir des motifs hexagonaux. On trouve d’ailleurs ces motifs en observant les ruches ou les colonnes basaltiques des massifs volcaniques.

Colonnes hexagonales de basalte… Pas tout à fait régulières, certes, mais impressionnantes !

Mais les pentagones réguliers dans tout ça ? Eh bien, les malheureux n’ont pas autant de chance, et l’on peut s’en rendre compte rapidement en essayant de les accoler les uns aux autres : de toute évidence, ça ne rentre pas !

Rien à faire Robert, ça ne rentre pas…

Pourtant, vous n’en démordez pas : vous utiliserez des pentagones réguliers coute que coute ! Alors, qu’à cela ne tienne, voyons ce que nous pouvons faire de ces polygones

Le rapport d’or

Pour cela, nous allons utiliser une propriété de notre pentagone : si l’on prend la longueur d’une de ses diagonales – un segment lient deux sommets qui ne sont pas voisins – et qu’on le divise par la longueur d’un côté, on obtient une valeur que l’on appelle nombre d’or, environ égale à 1.618.

Ce nombre, noté φ et parfois appelé « Divine proportion« , possède une caractéristique fort utile à notre affaire de pavage : le multiplier par lui-même revient à lui ajouter 1.

φ x φ = φ + 1

Découpons alors notre pentagone en trois triangles isocèles – qui possèdent deux côtés de longueur égale – comme l’indique l’image suivante :

En observant le triangle central, on remarque que sa base est un côté du pentagone, et que ses deux côtés égaux correspondent à deux diagonales du pentagone. Ainsi, le rapport entre la longueur des grands côtés et la longueur de la base de ce triangle vaut φ. Un triangle qui respecte cette règle s’appelle un triangle d’or.

Inversement, les deux triangles des extrémités ont pour base une diagonale du pentagone et, pour côtés égaux, deux côtés du pentagone. Cette fois, c’est le rapport entre la longueur de la base et celle des deux côtés égaux – soit l’inverse de ce que nous avions précédemment – qui est égal à φ. Un tel triangle s’appelle un triangle d’argent.

Et là, nous allons voir pourquoi le nombre d’or possède ce surnom de Divine proportion. Nous allons accoler un triangle d’or et un triangle d’argent provenant du même pentagone régulier, comme sur la figure plus bas. Nous allons supposer que ce pentagone a un côté de longueur 1 unité.

Ses deux côtés égaux correspondent à la base du triangle d’argent, ou a un côté du triangle d’or : ils ont une longueur de φ. Sa base, en revanche, à une longueur de φ + 1, qui est égal à φ x φ. Ainsi, en faisant le rapport entre les longueurs de la base et de ses côtés égaux, nous obtenons φ x φ / φ. En d’autres termes, nous avons, à partir d’un triangle d’or et d’un triangle d’argent, formé un nouveau triangle d’argent.

Triangles d’or et d’argent, de plus en plus grands…

Prenons alors ce nouveau triangle d’argent, et collons un triangle d’or sur un côté. Cette fois, la base a une longueur de φ, et le côté une longueur de φ x φ comme calculé plus haut. Le rapport entre côté et base est donc de φ : c’est un triangle d’or.

Et nous pouvons continuer ainsi à l’infini, avec ce triangle d’or et le triangle d’argent précédents, nous formons un triangle d’argent. Avec ce nouveau triangle d’argent et le grand triangle d’or, nous formons un nouveau triangle d’or, et ainsi de suite, de proche en proche, nous pouvons couvrir tout le plan.

De proche en proche, nous finirons bien par paver le plan ! #30AnsTangente

Nombre d’or, le retour

Voilà donc une solution pour paver en utilisant des fragments de pentagone, mais combien de triangles nous faudra-t-il pour former nos nouveaux triangles, de manière récursive.

La suite des nombres de triangles correspond à une suite bien connue…

En commençant avec 1 triangle d’or et 1 triangle d’argent, nous avons fait un triangle d’argent composé de 2 triangles. Avec ce nouveau triangle et un triangle d’or, c’est un triangle composé de 3 petits triangles qui a été créé. Puis, il en a fallu 5, puis 8, puis 13…

Les amateurs de mathématiques auront vite reconnu la fameuse suite de Fibonacci, où chaque terme est calculé en faisant la somme des deux termes précédents. Et pour cause : chaque triangle est construit à l’aide des deux étapes précédentes, tout comme la suite ! Pas étonnant donc de la revoir dans nos triangles.

Cela devient encore plus intrigant lorsque l’on compte séparément le nombres de triangles de départ utilisés

Etape 1 2 3 4 5 6 7
Nombre total de triangles 1 1 2 3 5 8 13
Triangles d’or 0 1 1 2 3 5 8
Triangles d’argent 1 0 1 1 2 3 5

On remarque que les nombres de triangle d’or et d’argent utilisés sont des termes consécutifs de cette fameuse suite de Fibonacci. Encore une fois, tout est logique puisque les triangles sont construits grâce aux deux étapes précédentes.

Mais ce qui est intéressant, c’est que plus on progresse, plus le rapport entre le nombre de triangles d’or et le nombre de triangles d’argent tend vers… le nombre d’or, φ, encore lui !

Et cette convergence nous montre que le pavage que nous construisons ne peut pas être périodique, c’est-à-dire qu’il n’existe pas un petit modèle, de taille finie, avec lequel on puisse paver tout le plan rien qu’en le translatant ou en le tournant.

En effet, si c’était le cas, il serait composé d’un certain nombres de triangles d’or O et un certain nombre de triangles d’argent A. Le rapport O/A est ce que l’on appelle un nombre rationnel, une fraction. Or, φ ne peut pas être écrit sous une telle forme : il n’est donc pas possible d’avoir un tel modèle.

Pour plus d’allure

Bon, avouons-le, notre triangle n’est pas très beau. Rassurez-vous, car il existe des constructions bien plus élégantes faites avec ces triangles.

Une première construction consiste à utiliser des « fléchettes » et des « cerfs-volants » qu’on obtient en accolant respectivement deux triangles d’argent ou d’or. Par le même principe que pour le triangle, il est possible de construire alternativement des fléchettes et des cerfs-volants de plus en plus grands, jusqu’à paver le plan.

Cerf-volant (gauche) et fléchettes (droite). Il est possible de former un cerf-volant à partir de deux cerf-volants et deux demi-flechettes. Pour la fléchette, il faut un cerf-colant et deux demi-fléchette.

Et voici une partie du résultat qui peut être obtenu :

Pavage avec fléchettes et cerf-volants

De la même manière, en collant les triangles selon leur base, on obtient des losanges que l’on peut encore une fois construire successivement, jusqu’à recouvrir tout le plan. Autant dire que tout cela a plus d’allure que notre pavage de départ !

Pavage avec des losanges d’or et d’argent

Pour compléter

Publié dans Curiosités et récréation | Tagué , , , , | Laisser un commentaire

L’art de mettre en relation

Drapeau vert : Cet article ne demande aucune connaissance mathématique particulière


Vous avez ces trois chapeaux devant vous, et une question simple : quel est l’intrus ?

chapeaux

Là, plusieurs réponses sont possibles :

  • On peut exclure le premier chapeau puisqu’il n’a pas la même forme que les deux autres.
  • On peut écarter le deuxième vu qu’il est vert alors que les autres sont rouges.
  • Enfin, on peut désigner le troisième chapeau, plus grand que les deux autres.

Il n’y ni bonne ni mauvaise solution : tout dépend ce que l’on entend par intrus. Dans votre réponse, vous avez en tout cas certainement raisonné en trouvant un point commun à au moins l’un d’entre eux, point que ne partageait pas le dernier. En d’autres termes, vous avez classé ces chapeaux, selon le critère qui vous semblait le plus judicieux.

En mathématiques également, il est courant de classer les objets selon leurs propriétés. On rassemble ainsi des objets similaires en classe d’équivalence.

Mettre en relation.

Plutôt que d’exclure, il est ici question de regrouper à l’aide de ce que les mathématiciens nomment les relations d’équivalence. Alors, attention, on ne parle pas de n’importe quelle relation, il faut qu’elle respecte certaines propriétés :

  • Elle doit être réflexive : n’importe quel objet doit être en relation avec lui-même.
  • Elle doit être symétrique : si un premier objet est en relation avec un second objet, alors ce second objet est lui-même en relation avec le premier objet.
  • Elle doit être transitive : si un premier objet est en relation avec un deuxième objet lui-même en relation avec un troisième objet, alors le premier objet est en relation avec le troisième objet.

Prenons par exemple la relation « être de la même couleur » dans notre ensemble de chapeau.

  • Un chapeau est forcément de la même couleur que lui-même.
  • Si un chapeau 1 est de la même couleur que le chapeau 2, alors le chapeau 2 est de la même couleur que le chapeau 1.
  • Si un chapeau 1 est de la même couleur que le chapeau 2, lui-même de la même couleur que le chapeau 3, alors le chapeau 1 est de la même couleur que le chapeau 3.

Nous venons de prouver sans trop de difficulté que la phrase « être de la même couleur » définissait bien une relation d’équivalence. Alors à quoi ça sert tout ça ?

Eh bien, une fois notre relation d’équivalence trouvée, nous pouvons regrouper ensemble tous les éléments qui sont en relation les uns avec les autres dans ce que l’on appelle des classes d’équivalence. Par exemple, en utilisant la couleur comme relation d’équivalence, nous pouvons construire deux classes, la première constituée des chapeaux 1 et 3, et la deuxième uniquement constituée du chapeau 2. En prenant la taille, nous aurions une classe d’équivalence qui regroupe les chapeaux 1 et 2 tandis que le chapeau 3 serait tout seul dans une autre classe.

Plus précisément, nous réalisons une partition de notre ensemble des chapeaux : chaque chapeau appartient à une et une seule classe d’équivalence. Dès l’instant où vous tentez de grouper des objets, des concepts par similarité, ce sont des classes d’équivalence que vous formez.

Calendrier et arithmétique modulaire

Une application de ces relations particulières se trouve dans le domaine de l’arithmétique. Pour deux nombres entiers, nous dirons qu’ils sont en relation si leur différence est un multiple de 7 (on dit aussi qu’ils sont congrus modulo 7)

Par exemple, 15 – 1 = 14, qui est un multiple de 7. 15 et 1 sont donc congrus modulo 7. En revanche, 13 – 2 = 11, qui n’est pas un multiple de 7. 13 et 2 ne sont donc pas congrus modulo 7.

Nous pouvons ainsi former 7 classes. La première, composée des nombres 1, 8, 15, 22… La deuxième, composée de 2, 9, 16, 23… et ainsi de suite… Plutôt que d’écrire chaque classe en entier, nous pouvons en choisir un élément particulier, que nous appellerons représentant. Pour nos 7 classes, choisissons simplement 1, 2, 3, 4, 5, 6, 7, et disposons-les sur un cercle.

Airthmétique modulaire

Les entiers de 1 à 7 sont disposés en cercle, de telle sorte qu’après le 7 vient le 1

Cette disposition en cercle donne tout son sens à notre relation d’équivalence : faisons par exemple l’opération 5 + 4. Classiquement, on dirait simplement que 5 + 4 vaut 9. Sur notre cercle, nous allons démarrer sur le 5, puis avancer de 4 pas dans le sens des aiguilles d’une montre : nous nous retrouvons sur le 2. Ce n’est pas surprenant, puisque 2 et 9 sont dans la même classe d’équivalence ! Autrement dit, 5 + 4 est congrus à 2 modulo 7

Quel intérêt me direz-vous ? Ces congruences, on ne les rencontre pas tous les jours. Eh bien, justement, il s’avère qu’une semaine compte 7 jours. Imaginons que nous numérotions les jours de l’année : si le jour 1 est un lundi, alors les jours 8, 15, 22 et les suivants de 7 en 7 – autrement dit, tous ceux congrus à 1 modulo 7 – seront aussi des lundis.

Si nous sommes un mercredi, quel jour serons-nous dans 25 jours ?

  • En notant 1 le premier lundi, le 3ème jour est un mercredi
  • 25 est dans la classe de 4 modulo 7 (puisque 25 – 4 = 21 qui est un multiple de 7)
  • 3 + 4 = 7, qui correspond au dimanche.

25 jours après un mercredi, nous serons donc un dimanche.

D’autres exemples peuvent être trouvées dans la vie quotidienne : la grande aiguille revient toutes les 60 minutes à la même position, définissant cette fois des classes d’équivalence modulo 60. L’arithmétique modulaire, combinée aux nombres premiers, donne naissance à de magnifiques applications en cryptographie, afin que vous fassiez vos transactions en ligne l’esprit tranquille…

Les entiers selon Frege

Prenons un nouvel exemple et voyageons à la ferme !

La ferme

Bienvenue à la ferme des animaux !

Pour nous, il serait commode de compter les animaux : il y a 1 âne, 2 oies, 4 cochons, 4 chevaux, 4 vaches, 6 poules et 6 moutons. Mais oublions tout cela, oublions les nombres : ici ils n’existent pas.

Procédons plutôt par association. Choisissons parmi toutes celles-ci, deux espèces d’animaux, potentiellement les deux-mêmes, et regardons s’il est possible d’associer un animal de la première espèce à un animal de la seconde sans laisser personne de côté.

En bref, on détermine s’il y a autant d’animaux de la première espèce que d’animaux
de la seconde espèce sans avoir à les compter. Si c’est le cas, on dira que la première espèce est en relation avec la seconde espèce. Par exemple, les vaches sont en relation avec les chevaux, mais ne sont pas en relation avec les poules. En revanche, les poules sont en rapport avec les moutons.

Nous pouvons vérifier que notre relation « avoir autant d’animaux » est bien une relation d’équivalence

  • Une espèce est toujours en relation avec elle-même. Il y a autant de cochons que de cochons, autant de poules que de poules, et ainsi de suite.
  • Si une espèce A est en relation avec une espèce B, alors l’espèce B est en relation avec l’espèce A. S’il y a autant de poules que de moutons, alors il y a autant de moutons que de poules.
  • Si une espèce A est en relation avec une espèce B qui est elle-même en relation avec une espèce C, alors l’espèce A est aussi en relation avec l’espèce C.
    S’il y a autant de cochons que de chevaux, et autant de chevaux que de vaches, alors il y a autant de cochons que de vaches.

Une fois cette relation en place, on peut par exemple construire une classe d’équivalence qui comporte l’ensemble des poules et l’ensemble des moutons. Pour plus de commodités, cette classe pourra être notée « 5 ». De même, nous avons la classe d’équivalence qui rassemble les chevaux, les cochons et les vaches. Cette classe sera notée « 4 ». Certaines classes n’ont qu’une seule espèce, comme celle des ânes, notée « 1 » ou celle des oies, notée « 2 ».
Nous pouvons également imaginer la classe des lions et des girafes. Celle-ci sera notée 0.

C’est ainsi que Frege définit les entiers naturels, contrairement à Peano qui les définit de manière axiomatique : ce sont les classes d’équivalence pour la relation que nous avons utilisée. Le nombre 4, c’est le nom de la classe d’équivalence qui regroupe tous les ensembles qui comportent autant d’élément qu’il y a de roues dans une voiture.

Par la suite, il est possible de définir les entiers relatifs grâce à une relation d’équivalence sur les couples d’entiers naturels, puis les rationnels à l’aide d’une nouvelle relation sur les couples d’entiers relatifs, puis les réels avec une troisième relation sur les suites de rationnels… Bref, les classes d’équivalence sont à la base des nombres, et donc, dans une certaine mesure, des mathématiques elles-mêmes !

Pour compléter

Publié dans Non classé | Tagué , , , | 1 commentaire

Des paradoxes et des ensembles

Drapeau jaune : Cet article demande quelques connaissances mathématiques et un peu d’abstraction pour être entièrement compris


Souhaitez-vous une énigme ?

Dans une petite bourgade, très loin d’ici, réside un barbier. Dans cette bourgade, le maire a fait voter une loi : le barbier doit raser tous les hommes du village qui ne se rasent pas eux-mêmes, et seulement eux !

Question : le barbier se rase-t-il lui-même ?

Raisonnons : si le barbier ne se rase pas lui-même, alors la loi l’oblige à se raser. Mais dans ce cas-là, il se rasera lui-même, et est donc hors la loi. Voici notre barbier fort désoeuvré ! A vrai dire, une telle loi, aussi stupide soit-elle, pourrait très bien exister. On ne peut en dire autant du barbier qui pourra l’appliquer.

Illustration : 3dman_eu sur pixabay https://pixabay.com/fr/users/3dman_eu-1553824/

Et en mathématiques, cela peut poser problème ! Que dire alors de l’ensemble de ces hommes qui se rasent eux-mêmes : inclut-il, oui ou non, le barbier ?

On pourrait croire qu’une propriété partagée par des éléments – un prédicat – suffirait à décrire un ensemble : l’ensemble des nombres plus grands que 3, l’ensemble des fonctions qui valent 0 en un point… Le barbier nous montre qu’il n’en est rien ! La prudence est de mise.

Une des pistes pour « résoudre » ces paradoxes est de hiérarchiser les ensembles : prenons donc un nouvel exemple, plus numérique celui-ci.

Exprimer les nombres

Il existe de nombreuses manières de définir un nombre avec des mots : prenons par exemple l’entier 42.

Celui-ci peut-être défini à l’aide de son écriture en lettres, « quarante-deux ». Il peut également être défini par l’addition, comme étant « trente-sept plus cinq », par une multiplication, puisqu’il vaut « six fois sept », ou encore par des phrases plus alambiquées comme « le nombre qui vaut vingt-quatre si l’on inverse les deux chiffres qui composent son écriture ».

Il est naturellement possible de pousser le vice très loin en imaginant des phrases aussi longues que l’on veut, toujours pour désigner le même nombre 42, mais restons raisonnables, et limitons-nous à une définition qui ne dépasse pas 100 mots.

Nous pouvons alors nous demander s’il est possible de définir tous les entiers naturels en moins de 100 mots, et avec un peu de réflexion, nous réalisons que c’est impossible. En effet, puisque nous avons un nombre fini de mots dans notre dictionnaire, nous avons également un nombre fini de suite de 100 mots mis cote à cote. Ce nombre a beau être très grand, il n’est rien comparé à l’infinité de nombres entiers qui existe !

« L’ensemble des entiers naturels qui ne peuvent être définis en moins de 100 mots » est donc non vide, il contient des éléments.

Puisque c’est une partie non vide de l’ensemble des entiers naturels, elle admet forcément un plus petit élément, unique, qui sera donc défini comme étant « le plus petit élément de l’ensemble des entiers naturels qui ne peuvent être définis en moins de 100 mots »… Or, nous venons justement de définir cet entier naturel en moins de 100 mots !

Hiérarchiser les définitions

Bertrand Russel

Le problème de ce paradoxe, connu sous le nom de « Paradoxe de Berry » et formulé en 1906 par Bertrand Russel est un problème de langage : que veut réellement dire le mot « définir » et jusqu’à quel point pouvons-nous l’utiliser à tort et à travers ?

Avant de définir notre entier problématique, nous avons d’abord « défini » un ensemble. C’est seulement ensuite que nous avons défini son plus petit élément et, par conséquent, nous avons défini notre entier en passant par la définition d’un ensemble. Il y a donc deux niveaux de définitions dans ce raisonnement qui ne doivent pas être traitées de façon équivalentes.

Pour essayer de s’en démêler, il va falloir être plus précis dans cette définition, et leur accorder différents degrés, différents niveaux.

Partons de rien : nous appellerons « 0-définition » un assemblage de mots qui permet de caractériser, de manière unique et non ambigüe, un ensemble, un entier, un objet.

Toutefois, nous devons nous imposer de ne pas utiliser le mot « 0-définition » dans cet assemblage de mots, pour ne pas avoir une notion qui tourne en rond. Ainsi, « six fois sept » est une 0-définition du nombre 42. Nous pouvons alors reprendre notre argument précédent et prouver, de la même manière, qu’il existe un « ensemble des entiers naturels qui ne peuvent être 0-définis en moins de 100 mots« . Seulement, cette manière de désigner notre ensemble comporte une 0-définition, ce que nous nous sommes interdits de faire !

Il faut donc passer au niveau supérieur : nous appellerons « 1-définition » un assemblage de mots dans lequel le mot « 0-définition » est autorisé et qui permet de caractériser, de manière unique et non ambigüe, un ensemble, un entier, un objet. En d’autre termes, une 1-définition utilise une 0-définition pour désigner un autre ensemble, un autre objet.

Notre ensemble est donc caractérisé par une 1-définition. De même, le plus petit élément de cet ensemble est déterminé comme étant « le plus petit élément de l’ensemble des entiers naturels qui ne peuvent être 0-définis en moins de 100 mots ». Certes, il y a moins de 100 mots dans cette phrase… Mais cette phrase n’est pas une 0-définition, puisqu’elle fait justement intervenir une 0-définition. Il n’y a donc plus de paradoxe ici !

De la même manière, il est possible de penser à des 2-définitions, des 3-définitions et ainsi de suite, autant que l’on veut.

Dans la même classe de problème, nous pouvons imaginer un génie aux pouvoirs magiques qui vous accorde un voeu. Vous, plus malin, faites le voeu d’avoir une infinité de voeu !

Eh bien, là encore, ce n’est pas un voeu simple, mais un voeu qui parle de voeu, ce que l’on pourrait appeler un 1-voeu sur le modèle précédent. Hélas, le génie ne peut exaucer que des 0-voeux et ne pourra accéder à votre demande.

Quel dommage…

Publié dans Paradoxes mathématiques | Tagué , , | 2 commentaires

Poser des multiplications : plusieurs écoles

Drapeau vert : Cet article ne demande aucune connaissance mathématique particulière


Nous avons pas mal parlé d’addition ces derniers temps, qu’il s’agisse d’en retracer les premières propriétés ou de se demander ce qui pouvait bien se trouver avant. Il est temps de la laisser de côté pour se concentrer sur sa petite cousine, la multiplication.

Rassurez-vous, pour cette fois, nous n’entrerons pas dans l’abstraction la plus totale, vous pouvez ranger votre boîte d’aspirine…

L’apprentissage de la multiplication passe d’abord par une généralisation de l’addition : plutôt que d’écrire 3 + 3 + 3 + 3, nous allons écrire 3 x 4, pour signifier que le nombre 3 est présent 4 fois dans une addition. A partir de là, il est temps d’apprendre les fameuses tables de multiplication, pour que ce calcul fastidieux devienne un automatisme.

Par la suite, on apprend à faire des multiplications plus compliquées, avec des nombres comportant plusieurs chiffres, en les décomposant en étapes plus simples : on apprend tout simplement à poser la multiplication.

Et pour poser des multiplications, il y a plusieurs écoles !

La méthode japonaise / maya / chinoise… Bref, celle avec des lignes et des noeuds.

Alors, d’où vient réellement cette méthode, j’avoue que je ne saurais l’affirmer. Cependant, je suis au moins en mesure de l’expliquer.

Vous avez probablement vu, en vous aventurant sur les réseaux sociaux par exemple, une technique de multiplication révolutionnaire qui rend totalement obsolète l’apprentissage des tables de multiplications.

Le principe est simple : les chiffres d’un nombre sont représentés par des segments, regroupés en petits tas. Par exemple, le nombre 213 peut s’écrire avec 3 tas de segments que l’on place dans l’ordre : le premier en comporte 2, le deuxième en a 1 et le dernier en a 3. Ces segments sont tracés dans une certaine direction – disons horizontale ici.

Dans la direction perpendiculaire, nous allons cette fois tracer de nouveaux segments, qui permettent de représenter un autre nombre. Ces nouveaux segments vont alors croiser les précédents en de nombreux points, appelés noeuds. Faire la multiplication de nos deux nombres revient finalement à compter les noeuds ainsi formés !

Voici une animation pour y voir un peu plus clair dans ce que je raconte.

Multiplication japonaise

Multiplication japonaise

On regroupe ainsi les noeuds par paquet, en partant du bas à droite pour aller en haut à gauche. De cette manière, on obtient les chiffres du produit de nos deux nombres de départ.

Séduisante sur le papier, puisqu’elle semble reléguer les tables de multiplications au rang de gadget, cette méthode comporte toutefois plusieurs inconvénients.

D’abord, il faut savoir former les paquets correctement sur le quadrillage : il n’est pas toujours évident de s’y retrouver entre nos différents tas. Lequel est utilisé pour le chiffre des dizaines ? Celui des centaines ?

Il s’agit là d’un jeu d’appariement assez récurrent en mathématiques : considérons pour le moment que nous n’avons le droit qu’aux nombres 1, 10, 100, 1000, etc…Pour obtenir 100 à l’aide d’une multiplication de deux nombres parmi les précédents, je n’ai guère que trois choix : 100 x 1, 10 x 10 ou 1 x 100.

Remarquez alors comment est formé le paquet rose sur l’animation : celui-ci est le compte total des noeuds formés par les segments…

  • des unités de 213 et des centaines de 132 (on est dans le cas 1 x 100)
  • des dizaines de 213 et des dizaines de 132 (on est dans le cas 10 x 10)
  • des centaines de 213 et des unités de 132 (on est dans le cas 100 x 1)

En gros, il faut trouver les bonnes paires de chiffres dans les deux nombres que nous multiplions. Naturellement, plus les nombres seront grands, plus il y aura de tas à prendre en compte. Cela se compliquera encore un peu plus si les deux nombres à multiplier n’ont pas la même taille.

Un petit souci vient également lorsque le chiffre 0 figure dans l’un des nombres : il suffit alors de placer une ligne en pointillé et d’ignorer tous les croisements que celle-ci peut engendrer. Par ailleurs, nous nous sommes contentés ici d’utiliser de petits chiffres. Avec cette méthode, la présence d’un 8 ou d’un 9 rend notre décompte assez laborieux, si bien qu’on préfèrera revenir à nos bonnes vieilles tables de multiplication…

La méthode russe

La méthode russe est directement inspirée de la multiplication qu’utilisaient les égyptiens dans l’antiquité… mais en mieux.

L’idée est de décomposer nos nombres en faisant de petites multiplications, plus simples, moins fastidieuses. En l’occurrence, il faudra simplement multiplier (et un peu diviser) par 2 !

Pour cela, nous allons dans un premier temps écrire nos deux nombres côte à côte, le plus grand à gauche – cela nous facilitera la tâche. Puis nous allons multiplier le premier nombre par 2. En même temps, nous diviserons le second nombre par 2. Si cette division ne tombe pas juste, pas de souci ! On prend la partie entière, on ne s’occupe pas de ce qui vient après la virgule. On continue ainsi jusqu’à ce que le nombre de droite vaille 1.

Prenons un exemple : 24 x 21

  • Je multiplie 24 par 2, cela fait 48. Je divise 21 par 2, cela me donne 10.5. Je garde donc 48 et 10
  • Je multiplie 48 par 2, je divise 10 par 2, cela me donne 96 et 5
  • Je recommence, il me reste 192 et 2
  • Puis 384 et 1

Maintenant, j’écris tous ces nombres dans un tableau, et je vais seulement garder les lignes où le nombre de droite est impair :

24 21
48 10
96 5
192 2
384 1

J’additionne alors les nombres de gauche que je n’ai pas rayé, et j’obtiens finalement :

24 x 21 = 24 + 96 + 384 = 504

Et voilà comment multiplier deux nombres en ne connaissant que sa table de 2… Le principe se base sur ce que l’on appelle l’écriture binaire d’un nombre : usuellement, nous écrivons les nombres en écriture décimale, en faisant des paquets de 10. 10 paquets de 10 forment un paquet de 100, puis 10 paquets de 100 donnent un paquet de 1000 et ainsi de suite. On peut ainsi écrire 24 = 2 x 10 + 4 x 1 ou 504 = 5 x 100 + 0 x 10 + 4 x 1.

La méthode russe utilise plutôt le regroupement par paquet de 2. En l’occurrence, 21 peut s’écrire 21 = 1 x 16 + 0 x 8 + 1 x 4 + 0 x 2 + 1 x 1. On remarque que seuls les paquets de 16, de 4 et de 1 sont utilisés. Plus simplement, on pourrait écrire 21 = 16 + 4 + 1. Et c’est justement cette écriture que l’on trouve à la fin, lorsque l’on multiplie par 24

  • 24 x 1 =… 24 !
  • 24 x 4 = 96
  • 24 x 16 = 384

Pas magique… Mathématique !

La méthode arabe

Comment parler d’arithmétique sans parler du monde arabe ? Impossible, je ne le ferai donc pas. Et d’ailleurs, même problème d’origine que notre première multiplication : on ne sait pas vraiment si les Arabes en sont les inventeurs ou les transmetteurs…

La méthode arabe ne change pas beaucoup de la nôtre à vrai dire (il va falloir sortir vos tables, je vous le dis !). C’est simplement la présentation qui varie. Nous allons cette fois multiplier 147 par 456, et pour cela, nous allons présenter le calcul sous la forme d’un tableau. Nous écrirons sur la première ligne le premier nombre, puis sur la dernière colonne, le second.

Toutes les cases seront ensuite divisées en deux en diagonale. On remplit les cases avec les produits des chiffres, suivant la ligne et la colonne : dans la partie haute, la dizaine, et dans la partie basse l’unité. Il suffit ensuite d’additionner diagonalement les nombres pour trouver le résultat.

Et puisqu’une illustration vaut mieux qu’un texte, voici notre exemple tout frais !

 

Multiplication arabe

Par exemple, la case en haut à droite, entourée en rouge, correspond à la multiplication de 7 et de 2, qui vaut 14. On place donc 1 dans la partie haute et 4 dans la partie basse. Une fois tout le tableau rempli, on ajoute les nombres suivant les diagonales. S’il y a des retenues, on les remonte dans la diagonale du dessus (ce à quoi correspondent les flèches ici)

Ici, le « décalage d’un cran » que l’on peut apprendre quand on passe au chiffre suivant dans une multiplication est remplacé par ce parcours en diagonal, mais le principe est le même. Résultat : 147 x 256 = 37632

Vous êtes désormais parés à toutes les éventualités (multiplicatives en tout cas). Quelle est votre méthode préférée ?

Publié dans Curiosités et récréation | Tagué , , | Laisser un commentaire

Avant l’addition : Problèmes de succession

Drapeau rouge : Cet article demande quelques connaissances mathématiques intermédiaires ainsi qu’une bonne capacité d’abstraction


Suite des réflexions du dernier article sur l’opération qui pourrait venir avant l’addition. Si vous ne voyez pas de quoi je parle, je vous conseille fortement d’aller faire un petit tour sur cette page.

Vous voilà à jour ! Parfait, nous pouvons continuer !

L’opération de succession

Notre but était de trouver une opération dont l’addition serait une écriture « compactée », comme la multiplication peut l’être pour l’addition, et la puissance pour la multiplication. A cette question, j’ai pu voir de nombreux commentaires sur Facebook, Twitter, ou la vidéo de Micmaths – qui ne m’étaient pas destinés, mais je lis tout de même hein ! – parlant de « Successeur », d’incrémentation, ou tout un tas d’autres noms qui se résume à une seule idée : Additionner des entiers, c’est simplement « Ajouter 1 » plusieurs fois.

Définissons alors notre opération, notre loi, comme suit :

L’opération « Succession« , noté S, est définie pour n’importe quels entiers a et b par :

a S b = a + 1

Nous créons une nouvelle opération – la succession – agrémentée d’un nouveau symbole – S . Par exemple 2 S 3 est égal à 2 + 1, c’est-à-dire 3.

Alors, d’entrée, on peut être un peu titillé par cette définition. Si l’on veut définir l’addition comme la généralisation de cette opération S, il va peut-être falloir éviter de définir S elle-même par une addition !

L’avantage des entiers dans notre cas, c’est leur discrétion. Je ne parle pas de nombres silencieux, mais de nombres distants les uns des autres. Prenons un entier : 2 par exemple. On sait qui vient après, il s’agit du 3. On sait aussi qui vient avant, il s’agit du 1.

Intuitivement, vous avez peut-être fait une addition ou une soustraction pour obtenir ces résultats, mais il n’y en a aucunement besoin. On peut, par exemple, représenter nos entiers sur un axe et remarquer que le 2 est situé entre le 1 et le 3. Redéfinissons alors proprement notre opération :

L’opération « Succession« , noté S, est définie pour n’importe quels entiers a et b par :

a S b = le nombre entier qui vient après a

Oui, l’idée est la même, mais c’est simplement une question de logique de construction : définir S à l’aide d’un signe + puis définir le signe + à l’aide d’une répétition de signes S pourrait nous mener à de sérieux problèmes !

Dans un précédent article, je parlais de la définition de l’addition mathématique, et celle-ci se faisait par récurrence, par « pas de 1 ». Tout devrait donc bien se passer, non ?

Alors, est-ce que ça marche tout ça ? Prenons par exemple la somme 2 + 3, dont on sait qu’elle vaut 5. Avec notre écriture, nous aimerions que 2 + 3 soit égal à 2 S 2 S 2, où le 2 apparaît trois fois

  • (2 S 2) S 2 = (le nombre qui vient après 2) S 2, soit 3 S 2
  • 3 S 2 = (le nombre qui vient après 3), soit 4

Ah… Raté…

Il y a en fait une petite subtilité supplémentaire à noter lorsqu’il s’agit de « compacter » nos opérations :

  • Lorsque nous faisons 2 + 2 + 2, nous l’écrivons 2 x 3, mais ce n’est pas l’opération qui apparaît trois fois : c’est le nombre lui-même.
  • Même chose avec la puissance : 2^3 = 2 x 2 x 2. Le signe de la multiplication n’apparaît que deux fois.
  • Ainsi, lorsque nous faisons 2 + 3, pour avoir une généralisation cohérente avec celles fournies par la multiplication et l’addition, et bien il faut appliquer 2 fois l’opération que nous créons, alors qu’intuitivement, cette opération revient à ajouter 3 fois le nombre 1.

Il faudrait donc se débarrasser de ce décalage, et nous pourrions procéder ainsi :

L’addition de deux entiers a et b est définie par :

a + b = a S a S a S… S a où a apparaît (b+1) fois

Dans ce cas là, nous aurions bien 2 + 3 = 2 S 2 S 2 S 2. D’accord, ça fonctionne… Pour autant, cette opération me déplait fortement, et cela n’est pas uniquement la faute de ce décalage horripilant.

Des propriétés peu engageantes…

On ne va pas se le cacher, l’addition est une opération confortable : elle est commutative et associative, ce qui signifie, dans le jargon mathématique, que si l’on doit additionner plusieurs nombres, on peut commencer à droite, à gauche, au milieu, changer l’ordre, et tout cela ne perturbera pas le résultat.

La « Succession » peut-elle s’en vanter ?

  • 2 S 3 = « le nombre qui vient après 2 » = 3
  • 3 S 2 = « le nombre qui vient après 3 » = 4

Déjà, oubliez la commutativité. Quant à l’associativité…

  • (2 S 2) S 2 = (le nombre qui vient après 2) S 2 = 3 S 2 = le nombre qui vient après 3 = 4
  • 2 S (2 S 2) = 2 S (le nombre qui vient après 2) = 2 S 3 = le nombre qui vient après 2 = 3

On ne peut donc pas commencer où l’on veut. C’est d’ailleurs une lacune de notre définition : il faudrait préciser que le calcul se fait de gauche à droite, ou parenthéser les expressions pour éviter toute ambiguïté.

Tout ceci n’est déjà pas glorieux. A vrai dire, cela provient du fait que la succession, contrairement à l’addition ou la multiplication, n’agit que sur un seul des deux nombres qu’on lui donne – on parle d’opération unaire. Cette absence de propriété nous force à choisir un sens pour notre opération – en l’occurrence, pour que tout colle, il faut faire les calculs de la droite vers la gauche.

Bien, la succession seule n’est pas très intéressante. L’est-elle lorsqu’on la regarde avec d’autres opérations ? Combinons par exemple l’addition et la succession.

  • Que vaut 4 + (2S3) ? 2 S 3 est égal à 3, et 4 + 3 = 7
  • Que vaut maintenant (4+2)S(4+3) ? Cela vaut 6S7, soit le nombre qui vient après 6 – vous l’aurez compris, 7.

Nous retrouvons la même chose, et nous pourrions nous amuser avec d’autres nombres pour vérifier que tout fonctionne correctement : il est possible de distribuer les nombres dans la parenthèses. On dit d’ailleurs que dans ce cas, la Succession est distributive à gauche par rapport à l’addition. Et puisque l’addition est bien sympathique, elle, nous pouvons également trouver la distributivité à droite. Enfin une bonne nouvelle !

A rebours

La succession n’est pas très attrayante… Mais est-ce que l’opération qui vient avant l’addition peut seulement l’être ? Nous allons désormais lister tout ce que doit respecter notre opération pour être érigée en digne prédécesseur de l’addition.

Je reprends donc ma notation du dernier article et vais supposer qu’il existe une opération, le coeurage, de symbole ♥, tel que a + b = a ♥ a ♥ a ♥… ♥ a où a apparait b fois. Nous allons de plus imposer que tous les calculs doivent se faire de la gauche vers la droite (ceci est une convention, pour nous faciliter la tâche, plus qu’une propriété).

Dressons alors une table de coeurage, comme on fait des tables de multiplication et d’addition.

Ainsi 0 ♥ 0 = 0 + 2 = 2, puisque le 0 est coeuré avec lui-même et apparaît une fois. De même 1 ♥ 1 = 1 + 2 = 3, 2 ♥ 2 = 2 + 2 = 4 et ainsi de suite. Bref, coeurer un nombre avec lui-même revient à lui ajouter 2, et nous avons une première diagonale.

Et hors de la diagonale, que peut-on remplir ?

Considérons l’expression 0 ♥ 0 ♥ 0. Ceci vaut 0 + 3, donc 3. Mais cela vaut aussi 2 ♥ 0, si l’on rassemble les deux premiers 0 coeurés ensemble. Nous avons donc 2 ♥ 0 = 3. De même, nous pouvons trouver 0 ♥ 0 ♥ 0 ♥ 0 = 0 + 4 = 4 = 3 ♥ 0.

Ce que nous faisons avec 0, faisons-le avec 1 ! 1 ♥ 1 ♥ 1 = 1 + 3 = 4, mais 1 ♥ 1 ♥ 1 = 3 ♥ 1. Nous pouvons alors remplir en partie notre table de coeurage comme suit.

Table de coeurage

Table de coeurage.

Etrange n’est-ce pas ? Les lignes se remplissent jusqu’à la case avant la diagonale, impossible à déterminer sans faire de nouvelles suppositions. Plus surprenant, ces nombres sont à chaque fois les successeurs des nombres que nous coeurons. Ainsi, 7 ♥ 0 = 7 ♥ 1 = 7 ♥ 2 = 7 ♥ 3 = 7 ♥ 4 = 7 ♥ 5 = 8 ! Il n’y a que sur la diagonale que la règle change, et où nous ajoutons 2 au lieu d’un  (et nous observons de nouveau le décalage constaté avec la succession).

Il se peut finalement – et à ma grande déception – que nous n’ayons pas vraiment le choix des opérateurs.

Encore une fois, tout ce qui est présent dans cette article est loin d’être irréfutable. Si votre avis diffère du mien, si vous décelez une erreur de raisonnement, n’hésitez pas à en discuter dans les commentaires !

Publié dans Actualité | Tagué , , | 2 commentaires

Réflexions : Qu’est-ce qui vient avant l’addition ?

Drapeau rouge : Cet article demande quelques connaissances mathématiques intermédiaires ainsi qu’une bonne capacité d’abstraction


Dans sa dernière vidéo sur Micmaths, Mickaël Launay nous pousse à la recherche,à l’interrogation, avec une question aussi intrigante que vague : qu’est-ce qui vient avant l’addition ?

Précisons le sens de cette question : l’addition est la première opération que nous apprenons à l’école. Ensuite vient la multiplication, et les fameuses tables que nous avons dû réciter par coeur. 3 x 4 ? 12 ! Mais ne serait-ce pas là une manière plus simple d’écrire 3 + 3 + 3 + 3, où le chiffre 3 apparait 4 fois ? La multiplication peut être vue comme une addition répétée, présentée sous une forme plus compacte, plus brève. De la même manière, la puissance est une façon d’écrire la répétition d’une multiplication de manière plus agréable, et il existe des notations pour la répétition de puissance, pour la répétition de répétition de puissances, et ainsi de suite.

Mickaël Launay interroge alors : l’addition pourrait-elle être une façon d’écrire une autre opération de manière plus compacte ? Et cette opération, est-elle également une écriture d’une autre opération ? Et ainsi de suite, peut-on remonter indéfiniment ?

Dans cet article, je vous propose mes réflexions sur le sujet. Attention, elles ne doivent absolument pas être prises au pied de la lettre : il ne s’agit que des essais d’un modeste passionné de mathématiques qui se prête au défi lancé par un vidéaste qu’il suit et apprécie. Certaines idées vous plairont peut-être, d’autres vous sembleront grotesques, c’est le jeu de la recherche après tout ! Il se peut d’ailleurs que, dans la précipitation, je sorte de grosses âneries, mais vous ne manquerez pas de m’en faire part dans les commentaires ! Il faut savoir confronter ses avis, alors… avisons !

Dans quel ensemble ?

Analysons d’abord la question : quelle opération pourrait venir avant l’addition ? A cette question, j’en apporte une autre : l’addition, oui, mais l’addition de quoi ?

Tous comme les opérations, notre connaissance des nombres et des objets mathématiques ne cesse de s’étoffer au cours de notre scolarité, et même après. Nous commencer par des entiers, puis découvrons les rationnels, enchaînons sur les réels avant de se frotter aux complexes. Entre temps, nous faisons connaissance avec les vecteurs, les suites, les fonctions, les égalités, les équations, les polynômes, et tout un tas d’autres objets pour lesquels il existe une addition.

Seulement, le réflexe que nous pouvons avoir, c’est de penser immédiatement aux nombres entiers (et je dirais même plus, aux entiers naturels). A vrai dire, cette pensée n’est sans doute pas mauvaise : dans sa construction dans sa définition de l’addition, Peano ne se souciait guère de toutes ces fantaisies. Ses axiomes décrivaient parfaitement l’arithmétique, et nous pouvons nous en contenter.

Lorsque l’on observe plus en détails la construction des ensembles de nombres, nous nous rendons compte par ailleurs que toutes les additions sur ces ensembles ne sont en fait que les prolongations de l’addition que nous avons sur les entiers naturels. Pour les relatifs, il suffit de symétriser. Pour les rationnels, c’est un passage au quotient. Pour les réels, c’est un peu plus compliqué, et cela dépendra fortement de la construction que l’on préfère à cet ensemble. Bref, comprendre l’addition des entiers suffit à définir celle des réels. Il est d’ailleurs intéressant de noter que l’addition est définie par prolongement d’une opération d’un ensemble plus petit vers un ensemble plus grand, plutôt que comme la restriction d’un ensemble plus grand vers un plus petit.

Faisons simple : contentons-nous d’addition d’entiers pour le moment !

Posons le problème

Le but est d’écrire l’addition comme la répétition d’une autre opération, à laquelle nous donnerons un nouveau signe. Comme je suis un grand sentimental, je désignerai cette nouvelle opération par le signe ♥. Prenons un exemple : l’écriture 2 + 3 désignerait en fait 2 ♥ 2 ♥ 2 où 2 apparaît 3 fois.

Nous savons par ailleurs que l’addition sur les entiers est commutative, nous pouvons inverser l’ordre des nombres dans le calcul. 2 + 3 = 3 + 2. En utilisant notre nouvelle notation, nous obtenons des égalités intéressantes. Par exemple :

2 ♥ 2 ♥ 2 = 3 ♥ 3 = 5

Mais le plus intéressant nous viendrait du nombre 1. En effet, si nous transposons l’addition 4 + 1 dans notre nouvelle notation, nous obtenons simplement 4. Inversement, nous savons que 4 + 1 = 1 + 4, et 1 + 4 s’écrit 1 ♥ 1 ♥ 1 ♥ 1. Par conséquent,

4 = 1 ♥ 1 ♥ 1 ♥ 1

Oui mais voilà, ce que nous avons écrit est la généralisation des écritures 1 + 4 et 4 + 1… Et, dans un monde où tout se passe bien, cela devrait être 5… Sauf que là, je me retrouve avec 4 !

Pire encore ! Je peux bien écrire 0 + 4 comme étant la notation compacte de 0 ♥ 0 ♥ 0 ♥ 0, lequel doit valoir, d’après l’addition, 4. Oui mais, comment écrire 4 + 0 ? Comment écrire une opération où le 4 n’apparaît 0 fois ?

Et à partir de ce moment-là, je commence à avoir mal au crâne à réfléchir à beaucoup de choses… Mais je ne reste pas moins sans piste !

Eléments neutres et nombre de fois

Il existe, pour l’addition, un nombre assez sympathique : 0. On l’appelle l’élément neutre pour l’opération « addition » (ou plutôt, pour la loi de composition interne d’addition), et cela se traduit assez simplement : pour n’importe quel nombre a, a + 0 = 0 + a = a. Ajouter 0 ne change pas le nombre. Pour la multiplication, l’élément neutre est 1. Pour l’opération de puissance, celui-ci disparaît néanmoins.

Quel pourrait-être l’élément neutre de cette opération ? Et surtout, que pourrait-il apporter ?

Pour la réponse à la deuxième question,  il arrive parfois aux mathématiciens de faire des sommes d’éléments d’un ensemble vide… Autrement dit, de n’additionner rien du tout ! Cette somme vaut alors 0, puisque c’est l’élément neutre de l’addition. De même, le produit de rien du tout vaut 1.

Avec notre nouvelle opération, nous pourrions alors imaginer « coeurer » rien du tout. Cela pourrait peut-être lever les « soucis » que nous rencontrons avec notre écriture du 4 + 0, quand il faut « coeurer 4 zéro fois », autrement dit, ne rien coeurer du tout. Cela pourrait également résoudre le problème d’ambiguïté que nous avions plus haut avec l’égalité suivante :

4 = 1 ♥ 1 ♥ 1 ♥ 1 = 1 + 4 = 5

Se pourrait-il que nous manquions d’un élément neutre pour « corriger cette égalité » ?

Une autre pensée, un peu plus philosophique, me vient cependant à l’esprit. Lorsque nous essayons de compacter certaines opérations qui sont répéter un certain nombre de fois. Mais quelle est l’opération qui compte justement ce nombre de fois, si ce n’est l’addition elle-même ?

Autrement dit, il se pourrait que, pour donner une définition correcte d’une nouvelle opération, il faille être capable de compter un nombre de fois qui soit compatible non pas avec l’addition, mais avec le coeurage. Oui, le coeurage, parfaitement !

D’ailleurs, ce parti pris de ne choisir que les entiers est-il finalement si légitime que cela ? Faudrait-il considérer un ensemble plus grand ? Créer un nouvel ensemble ?

J’espère que ces réflexions n’auront pas fait exploser votre cerveau. Je reviendrai peut-être à la charge si d’autres idées me viennent à chaud, ou un peu plus tard, lorsque tout sera décanté. D’ici là, n’hésitez pas à réfléchir vous-même à la question !

 

 

Publié dans Actualité | Tagué , , | 9 commentaires

La ronde des cavaliers : Deuxième prise !

Drapeau jaune : Cet article demande quelques connaissances mathématiques et un peu d’abstraction pour être entièrement compris


Dans le précédent article, nous avions vu qu’il était impossible de faire un tour – ou parcours fermé – du cavalier sur des échiquiers de taille particulière. Si vous ne l’avez pas consulté, je vous le recommande vivement, car je reprends dans les lignes qui suivent certains éléments abordés dans l’article en question.

Voilà ? C’est fait ? Parfait ! Continuons.

Parmi les situations impossibles, il en subsistait une sur la quelle je n’avais touché mot. Soyez rassurés, car le temps est venu de remédier à cet oubli. Dans cet article, nous démontrerons pourquoi, sur un échiquier de taille 3 x 8, il est impossible de faire un tour du cavalier. Accrochez-vous à vos ceintures, c’est parti.

Des réductions

Non, pas question de soldes ni de promotions, mais de graphes. Comme nous l’avons déjà vu, nous pouvons modéliser les mouvements de notre cavalier par un graphe.

Les cases de notre échiquiers sont matérialisées par des sommets. Ces sommets sont eux-mêmes reliés entre eux lorsqu’il est possible de joindre l’une et l’autre en un seul tour pour notre cavalier – lequel, rappelons-le, se déplace selon une trajectoire « en L ».

Si nous prenons un plateau de 3 lignes et 8 colonnes, voici à quoi pourrait ressembler notre graphe.

Graphe du cavalier

Graphe du cavalier sur un échiquier 3 x 8

Le but est donc de trouver un chemin qui passe une et une seule fois par tous les sommets, et qui en plus, revient à son point de départ.

Une solution consisterait à tous les essayer. Et là, je ne dis pas qu’une telle solution ne fonctionnerait pas, j’affirme simplement qu’elle ne serait pas élégante, car elle ne mettrait pas en avant toute l’astuce dont les mathématiques peuvent se vanter. Ce serait fort dommage.

Plutôt que de partir tête baissée, nous allons plutôt nous intéresser à certains sommets particuliers. Regardez par exemple le sommet de la deuxième ligne, première colonne. De ce sommet, seules deux arêtes partent (ou y arrivent, c’est selon).

Or, nous cherchons un chemin qui passe pas tous les sommets du graphe : un tel chemin, s’il veut arriver à notre sommet (2,1) – notation pour dire 2ème ligne, 1ère colonne – devra forcément passer par ces deux arêtes.

Un chemin qui décrit un tour du cavalier devra forcément passer par toutes les arêtes rouges de ce graphe.

Et c’est là qu’intervient la réduction. Le sommet (2,1) est relié aux sommets (1,3) et (3,3). Un tour du cavalier devra forcément passer successivement par la chaîne (1,3) – (2,1) – (3,3), ou dans l’autre sens, (3,3) – (2,1) – (1,3). Du coup, plutôt que de s’embêter à garder ces trois sommets, nous allons les regrouper en un seul super-sommet. A ce sommet, nous allons relier tous les sommets qui arrive à l’une ou l’autre des extrémités. Nous réduisons ainsi le nombre de sommets à étudier.

On se ramène à un graphe plus simple en réduisant le nombre de sommets.

De cette manière, si j’ai un tour du cavalier dans mon graphe de départ, alors j’aurai forcément un « tour du cavalier » – ou cycle hamiltonien, rappelons ce mot – dans mon graphe réduit. Un chemin qui passe par mes trois sommets dans mon graphe d’origine passera par mon super-sommet dans mon graphe réduit. Attention, l’inverse n’est pas forcément vrai, puisque mon super-sommet a créé de nouvelles connexions !

Par ailleurs, vous aurez peut-être aussi remarqué que les coins également n’avaient que deux arêtes, alors pourquoi ne pas les réduire eux aussi ? Voyons les deux coins de droite.

Ce que l’on peut voir, c’est que ces deux sommets sont reliés à un même troisième sommet, celui situé à la position (2,3). Cela limite mes mouvements : pour ne passer qu’une et une seule fois par chaque sommet, je dois parvenir au sommet (2,3) depuis l’un des coins, puis repartir vers le deuxième coin. En fait, je peux supprimer les arêtes qui relient (2,3) à (1,5) et (3,5), je sais déjà que je ne les utiliserai pas.

Graphe des coins

Aux quatre coins n’arrivent que deux arêtes. Avec un peu de logique, je m’aperçois que je dois forcément passer par les arêtes vertes et oublier les noires.

De la même manière que précédemment, je peux donc réduire mon graphe, en ramenant à un seul super-sommet tous les sommets qui sont reliés par une arête verte.

Chemin obligatoire

Le chemin obligatoire lorsque j’approche des coins

Couper le graphe

Allez, résumons ! Voici notre graphe tel que nous l’avons étudié : nous devons passer par les arêtes rouges et vertes, mais nous ne pouvons passer par les arêtes noires qui ont été barrées

Total

Au total…

Il ne nous reste plus qu’à réduire la bête pour nous ramener à un graphe plus simple à étudier.

Réduction totale

On réunit tous les sommets reliés par une arête coloré ensemble, et on efface les arêtes interdites

Plus sympathique non ? Nous passons de 24 sommets à seulement 8 avec un peu d’astuce. Encore un peu de réflexion et nous aurons notre résultat tant espéré !

Nous voyons ici deux sommets qui sont reliés chacun à trois autres sommets. Que se passe-t-il si l’on supprime ces deux polissons ?

On supprime les deux sommets reliés à 3 autres sommets

Vous voyez apparaître trois segments : notre graphe est divisé en trois morceaux, alors que nous n’avons retiré que deux sommets. Si nous avions un tour du cavalier, ce serait impossible !

Dans un graphe qui comporte un cycle hamiltonien, si on retire deux sommets, on ne peut pas créer plus de deux morceaux ! Pensez encore au collier ou au bracelet fermé : si vous le coupez à deux endroits différents, dans le pire des cas, vous n’aurez que deux morceaux. C’est la même chose ici.

Donc il n’y a pas de cycle hamiltonien ou de tour du cavalier dans notre graphe réduit. Or, s’il y en avait eu un dans le graphe d’origine, on en aurait trouvé un dans ce graphe réduit… C’est donc que notre graphe d’origine, notre échiquier 3 x 8, ne comporte aucun tour du cavalier.

Voici notre preuve bouclée. Avouez que c’est plus élégant que de tout essayer !

 

Publié dans Curiosités et récréation | Tagué , , | Laisser un commentaire