L’art de mettre en relation

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é , , , | Laisser un commentaire

Des paradoxes et des ensembles

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

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

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 Non classé | Laisser un commentaire

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

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 Non classé | Tagué , , | 9 commentaires

La ronde des cavaliers : Deuxième prise !

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 | Laisser un commentaire

La ronde des cavaliers

Les jeux sont souvent la source de problèmes mathématiques intrigants. Prenez par exemple un plateau de jeu d’échec standard, de taille 8 x 8, et une pièce nommée « cavalier« .

Aux échecs, le cavalier se déplace selon un motif en L : deux cases horizontales puis une verticale, ou deux cases verticales puis une horizontale, indépendamment des pièces qui pourraient se trouver sur son chemin. Ce comportement peu ordinaire a donné lieu à de nombreuses énigmes, dont celle du parcours du cavalier.

Déplacement du cavalier

Déplacement du cavalier. Le cavalier noir peut se déplacer sur les cases marquées d’un point noir. Source de l’image : pousseurdebois.fr

Partant d’une case au hasard de notre échiquier classique, est-il possible de passer une et une seule fois sur toutes les cases du plateau ? Mieux encore, est-il possible de fermer ce parcours, de manière à ce que la première case de ce chemin soit accessible en un mouvement depuis la dernière ?

Une fois la réponse à cette question donnée, l’esprit curieux ne s’arrêtera pas là. S’il existe un parcours fermé, peut-être tentera-t-il de tous les déterminer. S’il n’en existe pas, encore doit-il être capable de le démontrer. Et si cet échiquier classique ne le satisfait pas totalement, alors il recommencera l’expérience sur des plateaux de tailles variées, pas forcément carrés.

Intéressons-nous plutôt à cette dernière question.

Tourne, tourne

Revenons d’abord à notre problème classique : oui, il est possible d’établir un parcours fermé sur un échiquier de 64 cases, et en voici une des possibilités.

Parcours fermé

Un parcours fermé du cavalier.

Le parcours présenté ici et trouvé par Euler, divise le plateau de jeu en deux sous-plateaux, reproduisant un chemin similaire en haut et en bas. Évidemment, puisque ce parcours est fermé, il est possible de partir de n’importe quelle case et de suivre les flèches pour aboutir à un nouveau parcours fermé.

Bien, ceci étant fait, passons aux choses plus amusantes, et concoctez-vous un plateau de 5 lignes et 5 colonnes par exemple. Essayez de faire un parcours fermé du cavalier dans cette configuration, en partant de la case de votre choix.

N’y passez tout de même pas trop de temps : il vous sera impossible de boucler un tel itinéraire dans ce cas !

Des arguments de parité

Il existe sur les plateaux d’échecs classiques une information de taille pour résoudre ce problème : la couleur des cases. En effet, une case sur deux est blanche, l’autre est noire. Finalement, il y a 32 cases blanches et 32 cases noires sur le plateau classique.

Or, un plateau de 5 par 5 cases comportent 25 cases, et donc aura forcément une case blanche ou noire en plus par rapport à l’autre couleur. Et c’est là toute l’astuce !

Lorsqu’il se déplace, notre cavalier parcourt au total 3 cases : ainsi, s’il est au départ sur une case blanche (B), il finit sur une case noire (N) et inversement. Si l’on regarde simplement l’enchaînement des couleurs sur le chemin du cavalier, on aura forcément une suite de B – N ou de N – B : les cases vont ainsi deux par deux.

Or, pour que notre parcours soit fermé, il faut que la dernière case du chemin soit de couleur différente de celle de départ : notre parcours comporte donc un nombre pair de cases, alors que l’échiquier en possède un nombre impair.

Ce résultat vaut donc pour n’importe quel échiquier rectangulaire qui comporte un nombre impair de cases : par cet argument de parité, il ne peut pas y avoir de chemin fermé sur ce type de plateau.

Plus compliqué cette fois, qu’en est-il d’un échiquier de taille 4 x 6 ?

C’est un nouvel argument de parité, avancé par Louis Posa qui va nous donner la réponse ici. En effet, il est possible de colorier les cases de notre plateau de deux manières différentes :

  • D’abord, un coloriage une case sur deux, comme on a l’habitude d’en voir
  • Mais aussi en coloriant d’une couleur la première et la dernière ligne, et d’une autre les deux lignes restantes.

Nous avons déjà vu qu’avec le premier coloriage, on a forcément une alternance entre le noir et le blanc sur le chemin de notre cavalier. Pour le second, il est facile de se convaincre qu’un cavalier qui figure sur les cases rouges devra forcément aller sur une case bleue par la suite. Puisqu’il y a autant de cases rouges que de bleues, on en déduit que dans son parcours fermé, le cavalier doit alterner : Rouge, puis bleu, puis rouge, puis bleu…

Nous allons désormais « mélanger » ces deux coloriages. Supposons qu’on parte de la case en haut à gauche : dans le premier échiquier, cette case est noire ; dans le second, elle est rouge. Par conséquent, au déplacement suivant, le cavalier sera sur une case blanche du premier échiquier, bleue sur le second. Au déplacement d’après, le cavalier sera de nouveau sur une case noire et rouge, puis bleue et blanche, puis noire et rouge, et ainsi de suite.

Finalement, en faisant son tour, le cavalier ne passe que sur des cases qui sont noires et rouges, ou qui sont blanches et bleues. Jamais il ne pourrait passer par une case noire sur le premier échiquier et bleue sur le deuxième. Pourtant, un parcours fermé doit passer par toutes les cases ! Cette contradiction indique donc qu’un tel parcours fermé ne peut exister.

Ce raisonnement vaut pour tous les échiquiers ayant 4 lignes ou 4 colonnes : il est impossible de trouver un parcours fermé du cavalier sur ceux-ci.

En passant par les graphes

Nous avons prouvé qu’il n’existait pas de parcours fermé du cavalier dans les cas suivants :

  • il y a un nombre impair de lignes et un nombre impair de colonnes
  • il y a 4 lignes ou 4 colonnes

Pour comprendre la suite, il nous faut passer par la théorie des graphes. Un graphe, c’est simplement un ensemble de points (les sommets) qui sont reliés entre eux par des arêtes.

Dans le cas de l’échiquier, nous allons matérialiser notre plateau par des sommets. S’il est possible de déplacer le cavalier d’une case à l’autre en un seul coup, alors nous placerons une arête entre les deux sommets de ces cases.

Dans un graphe, un chemin est une suite de sommets connectés par une arête. Si je note (1,2) la case de la ligne 1, colonne 2, alors je peux tracer un chemin qui passe par les cases (1,2) – (2, 4) – (4, 3) – (6, 5)…

Trouver un parcours fermé du cavalier, ça revient dans le graphe à trouver un chemin qui passe une et une seule fois par chaque sommet et qui revient à son point de départ : c’est ce que l’on appelle un cycle hamiltonien.

Imaginez un collier de perles : ces perles, ce sont les sommets du graphe, et le fil qui les relie, c’est le cycle hamiltonien que nous cherchons. Si je retire une perle de mon collier, en coupant de part et d’autre de la perle, mon collier n’est encore qu’en un seul morceau. Certes, il n’est plus relié à lui-même, mais il tient toujours. Si je retire deux perles, alors soit j’ai toujours un seul morceau, soit deux, mais pas plus.

Pour les graphes, le même phénomène se produit : si un graphe comporte un cycle hamiltonien et que je lui retire 2 sommets, il n’est pas possible de créer strictement plus de deux morceaux différents.

Prenons alors l’échiquier a 3 lignes et 6 colonnes : voici ce qu’il se passe lorsque l’on supprime les sommets des lignes 1 et 3 sur la troisième colonne.

Supprimer deux sommets sur l’échiquier coupe le graphe en trois morceaux.

En supprimant les sommets matérialisés par des croix, j’isole les sommets rouges et verts des sommets bleus, et crée ainsi trois morceaux : il ne pouvait donc pas y avoir de cycle hamiltonien dans mon graphe de départ, et donc pas de parcours du cavalier dans un graphe 3 x 6.

Un nouveau raisonnement plus complexe sur ces cycles permet de conclure qu’il n’existe pas non plus de parcours du cavalier fermé sur un échiquier de taille 3 x 8.

Le théorème de Schwenk

Trouver les cas où ça ne fonctionne pas, c’est bien beau. Trouver ceux qui fonctionnent c’est encore mieux. Ca tombe bien, puisque le théorème de Schwenk nous donne toutes ces informations

Théorème de Schwenk : Pour tout échiquier de taille m x n, ou m est inférieur ou égal à n, il existe un parcours fermé du cavalier, sauf si :

  1. m et n sont impairs
  2. m vaut 1, 2 ou 4 et n est différent de 1
  3. m = 3 et n = 4, 6 ou 8

Nous avons vu plus haut un bon nombre de ces situations. Le cas où un côté est de longueur 1 ou 2 est évident : il est impossible pour le cavalier de faire demi-tour sur son échiquier. En revanche, nous n’avons nulle part montré qu’il s’agissait des seuls cas où le parcours fermé était impossible.

Pour ce faire, Schwenk raisonne par induction : il va d’abord trouver des cycles hamiltoniens dans un certain nombre de graphes, puis il va montrer que ces cycles peuvent être « fusionnés » pour former tous les cas possibles.

En effet, Schwenk va montrer que s’il existe un parcours fermé du cavalier sur un échiquier de taille m x n, alors ce parcours peut être prolongé dans un sens sur un échiquier de taille (m+4) x n ou dans l’autre sur un plateau de taille m x (n + 4).

En progressant ainsi par prolongement successif, on atteint ainsi toutes les tailles souhaitées.

Extension d'un cycle

Le cycle hamiltonien sur un graphe de taille 5 x 6 est prolongé sur un graphe de taille 5 x 10. Source en fin d’article.

Par exemple, connaissant la solution pour un échiquier 5 x 6, on peut en déduire une solution sur un échiquier 5 x 10, puis 9 x 10, puis 13 x 10, puis 13 x 14, et ainsi de suite. Il ne suffit alors que d’une poignée de graphes de départ (9 dans ce cas) pour obtenir toutes les solutions.

Les neuf cycles hamiltoniens de base trouvés par Schwenk. Source en fin d’article

Pourquoi 9 ? Puisque l’on progresse en ajoutant lignes ou colonnes par paquet de 4, il suffit de s’intéresser à un nombre restreint d’entiers. Les entiers peuvent se répartir en 4 classes, qui sont les suivantes :

  • 1, 5, 9, 13, 17… et tous les entiers de la forme 4k +1, avec k entier
  • 2, 6, 10, 14, 18… 4k + 2
  • 3, 7, 11, 15, 19, 23… 4k + 3
  • 4, 8, 12, 16, 20, 24… 4k

Il suffit donc de prendre un représentant convenable dans chacune de ces classes. Nous savons qu’il nous est impossible de créer des parcours fermés du cavalier si l’un des côtés de l’échiquier est de longueur 1, 2 ou 4. Aussi, nous choisirons pour représentants le nombre 5 pour la première classe, 6 pour la deuxième, 3 pour la troisième et 8 pour la quatrième, puis nous combinons tout ce beau monde pour faire nos échiquiers de base.

5 x 5 – 5 x 6 – 5 x 3 – 5 x 8 – 6 x 6 – 6 x 3 – 6 x 8 – 3 x 33 x 8 – 8 x 8

Parmi ceux-ci, nous devons supprimer les cas où les deux côtés sont de longueur impaire, car il n’est pas possible d’y trouver un cycle hamiltonien. Pour le cas 3 x 6, également impossible, il faut passer aux représentants suivants : on obtient les cas 7 x 6 et 3 x 10. Même chose pour le 3 x 8 qui est remplacé par les échiquiers 7 x 8 et 3 x 12.

Finalement, nos 9 échiquiers de base sont les suivants :

5 x 6, 5 x 8, 6 x 6, 7 x 6, 3 x 10, 6 x 8, 7 x 8, 3 x 12, 8 x 8

Et le tour est joué !

Pour compléter

Publié dans Curiosités et récréation | 1 commentaire