5 nuances d’Aubrey de Grey

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


Pas besoin d’être un pro des mathématiques pour s’amuser avec des graphes. Avec seulement quelques points et des arêtes, il est possible de concocter des problèmes au apparences simplistes qui résistent pourtant plusieurs décennies.

Récemment, c’est le problème du nombre chromatique du plan qui a fait parler de lui, puisqu’un certain Aubrey de Grey, biologiste de métier, a apporté une avancée significative à cette question vieille de plusieurs décennies : de combien de couleurs a-t-on besoin pour colorier le plan ?

Tout ceci semble un peu flou, alors apportons sans plus tarder un peu de précisions, si vous le voulez bien.

Colorier un graphe

Un graphe, comme mentionné dans cette introduction, c’est un ensemble de points – appelés sommets – dont certains sont reliés entre eux par des traits, des arêtes. Les graphes sont très utiles pour représenter certaines situations : on peut penser au réseau du métro, à un arbre généalogique ou à un graphe d’amis sur les réseaux sociaux.

Une fois devant un graphe, on peut alors se donner à toutes sortes de jeu. Celui qui nous intéresse aujourd’hui concerne le coloriage : à chaque sommet du graphe, je souhaite assigner une couleur, mais en faisant cela, je ne veux pas que deux sommets reliés par une arête aient la même couleur.

Naturellement, en bon mathématicien radin que je suis, je veux utiliser le moins de couleurs possibles pour réaliser mon coloriage – sans pour autant déroger à la règle instaurée deux lignes plus haut ! – : dans ce cas, le nombre de couleurs utilisé s’appellera nombre chromatique du graphe.

Graphe de Moser. Son nombre chromatique est de 4 : 3 couleurs ne suffisent pas à le colorier correctement.

Trouver le nombre chromatique d’un graphe n’est pas une affaire aisée : il faut, en gros, essayer tous les coloriages de ce graphe et déterminer le meilleur, ce qui peut prendre beaucoup de temps lorsque le graphe comporte beaucoup de sommets et – surtout- beaucoup d’arêtes.

Et ça le devient encore plus lorsque ces deux ensembles sont… infinis !

Graphe unitaire

Pour notre coloriage, nous allons choisir un graphe un peu particulier. Comme sommets de ce graphe, nous considérerons tous les points du plan. Tous. Sans exception. Imaginez une feuille blanche qui s’étend à l’infini dans toutes les directions, choisissez un point dessus. Gagné, il est dans le graphe !

Reste alors à décrire les arêtes : deux sommets de ce graphe seront reliés si la distance qui les sépare vaut 1 (1m, 1 cm, 1 année-lumière, que sais-je, vous prendrez bien l’unité qui vous convient). Cela revient à tracer un cercle de rayon 1 autour de chaque point du plan, et de relier tous les points de ce cercle au centre. Autant dire que ça en fait des arêtes.

La question est donc la suivante : quel est le nombre chromatique de ce graphe ? De combien de couleurs ai-je besoin, au minimum, pour le colorier sans que deux sommets voisins aient la même couleur ? En bref, quel est le nombre chromatique du plan ?

Une autre manière de s’imaginer ce problème est le suivant : si je possède un bâton de longueur 1, il faut trouver un coloriage du plan tel que, où que je pose mon bâton, ses deux extrémités se trouvent sur des points de couleurs différentes.

Ce problème, appelé problème de Hadwiger-Nelson, a été pour la première fois mentionné en 1950, avant d’être relayé par Martin Gardner dix ans plus tard. Et pourtant, il résiste encore et toujours, non pas à l’envahisseur, mais au commun des mortels.

Rassurez-vous, tout n’est pas aussi noir, et nous pouvons tout de même formuler quelques résultats.

D’abord, le nombre chromatique du plan ne peut excéder 7 : nous devons ce résultat à John Isbell qui s’est inspiré d’un pavage hexagonal pour établir cette borne supérieure.

En plaçant une baguette de longueur 1 sur ce pavage, ses deux extrémités se trouvent forcément sur deux couleurs différentes.

Isbell utilise des hexagones de diamètre légèrement inférieur à 1 et les colorie de 7 couleurs différentes. De cette manière, peut importe le point que je choisis, tous les points se trouvant à distance 1 de celui-ci se trouvent dans des zones d’une couleur différente à la première.

Graphe de Golomb

Graphe de Golomb, impossible à colorer avec seulement 3 couleurs

Ensuite, on sait depuis quelques années que le nombre chromatique du plan est d’au moins 4 : il existe en effet certains graphes unitaires, comme le graphe de Mosel ou le graphe de Colomb, qui ne peuvent être coloriés en utilisant seulement 3 couleurs.

Ne restent alors que 4 options pour notre nombre chromatique : 4, 5, 6 ou 7… Et voilà, l’histoire s’est arrêtée là pendant un bon bout de temps, jusqu’à ce que le précédemment mentionné Aubrey de Grey ne vienne mettre son nez dans cette affaire.

Le graphe de De Grey

Dans son article intitulé « The chromatic number of the plane is at least 5« , De Grey annonce la couleur (ah, ah !) : le nombre chromatique du plan est d’au moins 5, et pour le montrer, De Grey a construit un graphe impossible à colorer avec seulement 4 couleurs.

De Grey commence par observer un graphe, qu’il appelle H, ayant la forme d’un hexagone régulier avec un point en son centre. Le nombre chromatique de ce graphe est 3, mais ce n’est pas ce qui nous intéresse ici. De Grey remarque en effet que si on utilise au plus 4 couleurs, certaines colorations de ce graphe présentent un triangle monochromatique, alors que d’autres non.

Colorations du graphe H. Les deux versions du haut possèdent au moins un triplet de points de la même couleur – trois bleus, en l’occurrence. Image tirée de l’article de De Grey.

Partant de ce point, De Grey va alors construire deux graphes, chacun d’eux contenant au moins une copie de H. Concentrez-vous bien, car même si ce n’est pas très compliqué, il y a de forts risques de se perdre là-dedans.

  • Le premier graphe, appelé L – oui, c’est intime tout ça – est obtenu en dupliquant le graphe H de départ. Au final, ce graphe L contient 52 copies du graphe H, mais le plus important est que, si l’on essaye de colorier L à l’aide de 4 couleurs, alors au moins une copie de H de ce grand graphe présentera un triplet de point de même couleur.

Construction du graphe L à partir du graphe H

  • Le second graphe, appelé M, est une extension du graphe H – on rajoute des sommets et des arêtes, d’une façon un peu intelligente tout de même – qui vérifie une propriété contraire : si j’essaye de colorier M avec 4 couleurs, alors le graphe H ne contiendra cette fois aucun triplet de la même couleur.

Le graphe M de De Grey compte 1345 sommets et 8268 arêtes. Autant dire qu’il est impossible de vérifier à la main tous les coloriages possibles.

Bref, nous avons deux graphes L et M. Chacun peut être colorié avec 4 couleurs, mais le premier implique la présence d’un triplet monochromatique de points sur les copies de H, alors que c’est le contraire pour ce second graphe. Il n’y a plus qu’à les combiner ensemble et faire marcher la contradiction ! Le graphe obtenu ne peut pas être colorié avec seulement 5 couleurs.

Le graphe obtenu possède alors 20425 sommets, autant dire que ce n’est pas un petit graphe ! Heureusement, il est possible de retirer certains sommets pour aboutir à un graphe plus petit – 1581 puis 1577 sommets -, sans que celui-ci ne devienne colorable avec 4 couleurs pour autant.

Le graphe de De Grey à 1581 sommets. Source : Aubrey de Grey

On peut alors vérifier à l’aide d’un programme que 4 couleurs ne suffisent à colorer ce graphe : cela prend à peine 5 heures et demis avec du bon matériel, tandis que colorier ce graphe avec 5 couleurs prend moins d’une seconde.

Bref, le nombre chromatique du plan est au moins 5. C’est peut-être 5, 6 ou 7, mais 4 a disparu de la liste des choix.

Depuis la publication de l’article, un projet Polymath a d’ailleurs été lancé pour trouver des graphes toujours plus petits mais impossible à colorier avec seulement 4 couleurs. Ainsi, Marijn Heule est parvenu à réduire le nombre de sommets à 826.

Graphe de Marijn Heule, à 826 sommets. Source : Marijn Heule

En outre, ce projet a deux autres objectifs :

  • d’abord, voir si cette méthode peut s’étendre à la découverte de graphes unitaires qui ne peuvent être colorié avec 6 couleurs ou à des problème liés, comme le nombre chromatique des espaces de dimensions supérieurs
  • mais aussi réduire autant que possible l’utilisation de l’ordinateur dans cette preuve : les mathématiciens sont très attachés aux démonstrations « à la main ».

En bref, il y a encore du travail, mais cette avancée en appellera peut-être de nouvelles dans les mois à venir ?

Compléments et références

  • Soifer, A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators
  • De Grey, A. The Chromatic Number of The Plane is At Least 5
  • L’article de Quanta Magazine qui parle de cette découverte.
  • Deux articles sur le blog Short, Fat Matrices : ici, avec notamment les temps de calcul pour la coloration de graphe et , pour la description de la méthode
  • Le projet Polymath et les graphes sont décrits à cette adresse
  • Un article sur le blog de Gil Kalai, Combinatorics and more
  • En français cette fois, Eljj avait fait un article de blog sur la couleur du plan, c’est à cette adresse.
  • Un article sur le blog de David Madore qui traite également de la coloration du plan.
Publié dans Actualité, Conjectures et théorèmes | Tagué , , , | 1 commentaire

D’élégantes démonstrations

On le dit souvent, en mathématiques, le cheminement importe plus que le résultat. Que l’on soit d’accord ou non avec l’affirmation, il faut tout de même avouer que résoudre en une ligne certains problèmes d’apparences très difficiles a quelque chose de… magique.

Alors, forcément, dans le domaine, on pourrait en imaginer beaucoup, chacun aura son avis sur la question. D’ailleurs, certains trouveront de la beauté dans certaines preuves que d’autres jugeront absolument inélégantes : tout n’est que subjectif et relatif.

Voici, en tout cas, trois problèmes et leurs solutions que je trouve, pour ma part, fort élégantes ! Faites chauffer les méninges !

Le puzzle impossible ?

Drapeau vert : Cette partie ne demande aucune connaissance mathématique particulière


Celui-ci ne prendra que peu de place, puisque je lui ai consacré toute une vidéo que vous devriez aller voir, si ce n’est déjà fait. Le principe est de recomposer une forme donnée à l’aide de 5 tetrominos (autrement dit, des pièces formées de 4 cases carrées).

Le chien coureur

Drapeau vert : Cette partie ne demande aucune connaissance mathématique particulière


Deux personnes, que nous nommerons Alphonse et Bernadette, A et B pour les intimes, se trouvent à 2 kilomètres l’une de l’autre et chacune marche en direction de l’autre à une vitesse approximative de 1 m/s. A côté d’Alphonse se trouve un chien qui s’élance vers Bernadette en même temps qu’Alphonse commence sa marche.

Sauf qu’un chien, ça ne prend pas son temps celui-ci trace en effet sa route à environ 5 m/s. Une fois arrivé au niveau de Bernadette, il repart en sens opposé retrouver Alphonse, toujours à la même vitesse, et fait ainsi des allers-retours jusqu’au moment où Alphonse et Bernadette se croisent.

Quelle est alors la distance totale parcourue par le chien ?

Il court, il court, le chienchien…

En se lançant tête baissée dans ce genre de problèmes, on peut se retrouver vite désemparé : il faut faire la somme de tous les déplacements de l’animal, avec des distances qui varient après chaque étape. En développant les calculs, on se trouve alors avec une série géométrique assez classique, et je laisse le soin aux lecteurs habitués de vérifier que je ne dis pas de bêtises.

Voilà, voilà…

Eh oh, t’avais dis que c’était un drapeau vert, c’est quoi ce bazar ?

Oui, j’y viens, mais d’abord, commentons toutefois un petit peu cette formule :

  • Le 2 correspond aux 2 kilomètres qui séparent A et B au début.
  • Le 5/6 vient du fait que le chien va 5 fois plus vite que les personnages. S’il se dirige vers Alphonse, il couvre 5/6 de la distance tandis qu’Alphonse fait le 1/6 restant dans le même temps.
  • A chaque fois que le chien croise un personnage, il fait demi-tour. La distance entre Alphonse et Bernadette a alors diminué d’un tiers – je vous laisse les calculs hein.

Bon, enfin, c’est bien joli tout ça, mais est-ce que ce ne serait pas prendre le canon pour tirer sur une mouche ?

Raisonnons mieux : Puisque nos deux personnages vont à la même vitesse, ils se croiseront pile à mi-distance. Ils auront fait 1 kilomètre chacun. Le chien allant 5 fois plus vite que chacun d’eux, il en aura fait 5 fois plus… soit 5 kilomètres…

Tadam !

Des graphes connexes

Drapeau jaune : Cette partie demande quelques connaissances mathématiques de base et un peu d’abstraction pour être entièrement saisie.


Pour l’exemple suivant, il faudra un peu plus de travail, mais rien d’insurmontable.

Donnons d’abord quelques définitions :

  • Un graphe (non orienté), c’est simplement un ensemble de points – appelés sommets –  reliés par des traits, que l’on nomme des arêtes. Pour faire simple, on va supposer qu’il ne peut pas y avoir plusieurs traits qui joignent deux même points, et qu’un point ne peut pas être lié à lui-même par un trait. Dans les faits, ça ne change rien, mais autant faire simple.
  • On dit qu’un graphe est connexe si l’on peut passer de n’importe quel point à n’importe quel autre en empruntant les arêtes du graphe

Le graphe de gauche n’est pas connexe : on ne peut pas, par exemple, aller d’un sommet rouge à l’autre en passant par les arêtes du graphe.

  • Enfin, nous en aurons besoin, si on se donne un graphe, appelé G, on définit son complémentaire de la manière suivante : c’est le graphe G* avec les mêmes sommets, et deux sommets sont liés dans G* si et seulement s’ils ne le sont pas dans G. C’est une définition aux airs compliqués mais qui ne casse pas des briques quand on le voit graphiquement. En gros, c’est le graphe qui complète le graphe de départ.
Complémentaire

Le graphe tracé en vert est le complémentaire de celui en rouge. Ensemble, ils forment un graphe complet dont les arêtes sont soit vertes, soit rouges (mais aucune n’a les deux couleurs à la fois).

Alors, voilà donc la question : on se fixe un nombre de sommets supérieur ou égal à 4, noté n : existe-t-il plus de graphes connexes ou non connexes ayant n sommets ?

On pourrait essayer de les compter, de les dénombrer, et alors, la réponse serait toute donnée. Hélas, ce n’est pas une affaire aisée… Remarquons que la question ne demande pas le nombre exact de graphes connexes ou non connexes, simplement la catégorie la plus remplie.

Alors ? Une idée ?  Pas de triche hein ?

Réglons ce problème avec un argument massue : le complémentaire de tout graphe non connexe est connexe !

Admettons un instant cette propriété. En d’autres termes, si on a un graphe non connexe, on peut lui associer un graphe connexe, à chaque fois différent : il y a donc au moins autant de graphes connexes que de non connexes.

Pour terminer la preuve il suffit donc de trouver un graphe connexe dont le complémentaire est lui même connexe et le tour sera joué. Et cela fonctionne puisque nous avons pris au moins 4 sommets : il suffit de relier les points en formant une « ligne » non fermée.

Allez, le tour est presque joué. Oui parce que quand je parle d’une propriété, il faut bien la prouver tout de même, vous n’allez pas non plus gober tout ce que je dis, si ?

Alors voilà, prenons donc un graphe non connexe, que l’on appelle allègrement G, et montrons que son complémentaire est connexe. Prenons deux points, nommés x et y, dans ce graphe complémentaire.

  • S’il n’était pas possible de passer de x à y dans le graphe d’origine, alors x et y seront liés par une arête dans le graphe complémentaire.
  • Au contraire, s’il était possible de passer de x à y dans le graphe d’origine, alors il va falloir s’aider d’un troisième point. En l’occurrence, nous choisirons un point z qui n’est pas relié à x par un chemin (et donc, pas relié à y non plus, sinon on pourrait passer de z à y puis de y à x, et donc de z à x.). Ceci est possible car notre graphe de départ n’est pas connexe, rappelons-le. Alors, dans le graphe complémentaire, z est relié à x d’une part et à y d’autre part. Il est donc possible de passer de x à y en empruntant les arêtes du graphe complémentaire.

En bref, pour n’importe quel couple de points (x,y) du graphe complémentaire, on peut passer du premier au deuxième en passant par les arêtes. Bref, notre graphe complémentaire est connexe.

Le tour est joué !

Pour compléter

Encore plus de démonstrations élégantes ? En voici !

  • Le Professeur Culture Précieuse vous propose de trouver le plus court chemin possible pour installer un magasin.
  • Eljj passe en revue des démonstrations du célèbre théorème de Pythagore.
  • Le livre Raisonnements Divins : quelques démonstrations mathématiques particulièrement élégantes de M. Aigner et G.M Ziegler.
Publié dans Conjectures et théorèmes, Curiosités et récréation, Vidéo | Tagué , , | Laisser un commentaire

[Vidéo] De l’ordre dans les tiroirs

Voilà, je me lance dans l’arène ! La première vidéo Automaths est disponible depuis presque une semaine maintenant sur Youtube et concerne un principe simple et pourtant redoutablement efficace : le principe des tiroirs !

Vous souhaitez aller un peu plus loin ? Voici peut-être de quoi satisfaire votre curiosité !

La vidéo est classée Drapeau vert, accessible à tous, mais les précisions qui suivent tiennent davantage du Drapeau rouge.

Rationnels et périodes

Parmi les nombres dits réels, il existe deux sous-catégories de nombres : ceux dits rationnels, qui peuvent s’écrire sous la forme d’une fraction, résultats d’une division de deux nombres entiers, et les irrationnels, ceux qui ne le peuvent pas.

Dans la première catégorie se rangent ainsi les nombres comme 1/3, 47/99 ou 42/187. Ces nombres, si on essaye de les écrire sous leur forme décimale, ont une propriété intéressante :

1/3 = 0.3333333…
47/99 = 0.4747474747…
42/187 = 0.224598930481283422459893048128342245989304812834…

Pourvu que notre calculatrice aille assez loin, on voit apparaître une suite de chiffres qui se répète à l’infini : c’est ce que l’on nomme la période. Il s’avère en fait que tout nombre rationnel, toute fraction, possède une écriture décimale périodique. Et il s’avère que c’est une conséquence du principe des tiroirs !

En effet, lorsque l’on fait une division décimale, soit il n’y a pas de reste, et on s’arrête là : la suite du nombre n’est donc qu’une infinité de zéro après la virgule.

Soit on ne s’arrête jamais. Or, les restes de la division sont toujours inférieurs au dénominateur (il ne peut pas rester 48 morceaux si l’on essaye de partager en 47 parts : en effet, il suffit de retirer de nouveau 47 morceaux et en donner un à chacun. C’est tout de même plus cool non ?)

Nous avons donc un nombre fini de reste possibles alors que notre développement se poursuit à l’infini. Si l’on développe alors le quotient p/q, il n’y a donc que q – 1 restes possibles, allant de 1 à q – 1 (on a exclu le cas du reste valant 0 un peu plus haut). Fatalement, il y aura, au sein des q premières étapes de la division, au moins deux restes identiques, c’est le principe des tiroirs qui nous le dit !

Et puisque la division ne dépend pas de ce qu’il se passe avant ce stade, forcément, les développements à partir de ces deux étapes aux restes identiques sera le même.

Approcher des rationnels

Dans la deuxième catégorie, celle des irrationnels, entrent par exemple √2, π, e et bien d’autres encore. Dans un certain sens, ils sont d’ailleurs bien plus nombreux que les nombres rationnels, mais c’est une autre histoire.

En revanche, il est possible d’utiliser les nombres rationnels pour les approcher d’aussi près que l’on veut. Une méthode est par exemple de prendre ce que l’on appelle les « développements décimaux tronqués ». Par exemple, √2 = 1.41421356237… avec des décimales qui continuent ainsi à l’infini. Ainsi, la suite 1, 1.4, 1.41, 1.414, 1.4142 est une suite de nombres rationnels (et mêmes décimaux) qui approche de plus en plus finement le nombre √2. Seulement, cette approche n’est pas efficace, dans le sens où les dénominateurs de ces fractions sont grands – et donc, les numérateurs sont obligés de suivre. On aimerait ainsi gagner en précision tout en restant avec des dénominateurs raisonnables, plus agréables pour des calculs à la main, comme dans l’ancien temps.

Par exemple, le nombre π a souvent été remplacé par la fraction 22/7 qui est la meilleure approximation au sens où, pour tout dénominateur plus petit que 7, l’approximation de π sera forcément moins bonne.

L’approche de Dirichlet utilisant le principe de tiroirs permet ainsi de contrôler ce dénominateur : si je me donne un entier n et un réel x, je peux approcher ce réel avec une fraction p/q telle que l’erreur est inférieure à 1/nq, mais surtout avec un dénominateur q inférieur à n.

Alors, c’est bien gentil, mais le principe des tiroirs dans tout ça, où intervient-il ?

Pour un nombre, on peut s’intéresser à sa partie fractionnaire, c’est-à-dire, celle qui vient après sa virgule. La partie fractionnaire de 1.5 est 0.5, celle de 1.4978 est 0.4978 et ainsi de suite. Cette partie fractionnaire se situe donc entre 0 et 1, 1 étant exclu, ce que l’on note [0;1[. On notera la partie fractionnaire d’un nombre A entre accolades : {A}.

Nous allons donc regarder les parties fractionnaires {0x}, {1x}, {2x}, {3x}, et ainsi de suite jusqu’à {nx} – il y en a en tout n + 1.

Or, il est possible de découper l’intervalle [0 ; 1 [ en n plus petits intervalles : [0;1/n[, [1/n;2/n[, … [(n-1)/n;1[. Ainsi, si l’on veut ranger les n+1 parties fractionnaires dans les n intervalles construits, il y aura forcément un intervalle qui contiendra deux de ces parties fractionnaires.

Ainsi, on a deux nombres différents, k et h, telles que la différence |{hx} – {kx}| est inférieure à 1/n. Il suffit alors de choisir comme nombre p la différence entre les parties entières de kx et hx, puis comme nombre q la quantité q = k – h, et on aura alors :

|x – p/q| < 1/nq

Ouf, c’est terminé !

Pour compléter

  • L’excellent article de Jean-Paul Delahaye dans Pour la Science de Janvier 2018 (n°483)

 

 

 

Publié dans Vidéo | Tagué , , | Laisser un commentaire

Des codes et des grilles

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


La dernière fois, nous avions parlé de méthodes de chiffrement que l’on appelle « par substitution » : une lettre était remplacée par une autre dans l’alphabet. Ces méthodes, aussi ludiques soient-elles, s’avéraient finalement peu fiables.

Pour renforcer la sécurité de la communication, il est possible de transposer les lettres, d’en inverser l’ordre. Aussi, on peut penser à les dissimuler au milieu d’un message bien plus grand, à condition d’avoir une méthode simple pour notre destinataire de trouver les lettres utiles.

Voici quelques exemples simples de ces procédés

La scytale

Utilisée par les spartiates, la scytale est un bâton autour duquel on enroule de manière régulière une bande de papier avant d’écrire un message dessus. Ainsi, en déroulant la bande, l’ordre des lettres du message d’origine est chamboulé.

Une scytale tant artisanale que subliminale. En déroulant le message ABONNEZVOUSAUBLOG!, on obtient ANOUO BEUBG OZSL! NVA

Pour décoder le message ainsi obtenu, il suffit d’enrouler de nouveau la bande autour d’un bâton similaire, rien d’extraordinaire.

Conceptuellement, ce procédé revient à écrire le message selon les lignes d’un tableau qui comporte autant de colonnes que de lettres nécessaires pour faire un tour de la scytale. Dans l’exemple plus haut, je pouvais placer 4 lettres sur une rangée, on utilise donc un tableau à 4 colonnes.

A B O N
N E Z V
O U S A
U B L _
O G !

Vous apercevez un caractère manquant sur la quatrième ligne :  c’est tout simplement parce que je manquais de papier pour l’écrire sur ma bande ! Pas de panique, le message reste déchiffrable. Le message codé correspond à la suite de lettres obtenue en lisant colonne par colonne.

Le problème, c’est que le nombre de combinaison à tester pour déchiffrer le message est très réduit : pour celui qui intercepte le message, il suffit de lire toutes les deux lettres, ou toutes les trois lettres, ou toutes les quatre et ainsi de suite pour arriver au bon résultat. Bref, il n’y a pas vraiment besoin de posséder une exacte réplique du bâton d’origine pour décrypter le message…

Il se peut que la scytale ait également été utilisée comme une méthode d’identification plutôt que de codage, une sorte de mot de passe avant l’heure si l’on veut.

Ainsi, pour être certain de l’identité de l’expéditeur d’un message, il fallait que celui-ci ait rédigé son message à l’aide d’une scytale d’une certaine forme et d’un certain diamètre. Si, en enroulant le message sur la scytale, celui-ci produisait un texte incompréhensible, alors le message était rejeté. Ce procédé aurait permis d’empêcher les espions ennemis de diffuser de fausses informations au sein d’une armée.

La grille de Cardan

Autre époque, autre méthode. La grille de Cardan, du nom du mathématicien Jérôme Cardan, a pour but de masquer un message secret au sein d’un message bien plus long. Pour cela, on utilise une grille à trou que l’on pose sur une feuille de papier et on y inscrit le message à dissimuler. Ensuite, en retirant le cache, on complète le reste de la feuille. Le destinataire n’a plus qu’à utiliser un cache identique pour voir apparaître le message d’origine.

Naturellement, il est possible de compléter le message avec des lettres prises au hasard, mais le but de la manoeuvre ici est de paraître totalement innocent : un message inintelligible attirerait à coup sûr l’attention. Il valait donc mieux compléter intelligemment, en faisant mine de transmettre un message anodin.

Grille de Cardan

Un message secret apparaît lorsque l’on utilise la grille.

La grille de Cardan n’est d’ailleurs pas une méthode de cryptographie à proprement parler. Généralement, on remarque immédiatement qu’un message est crypté puisqu’il est inintelligible, ce qui n’était pas le cas ici. On parlera plutôt de stéganographie, l’art de dissimuler le message.

Toute la difficulté était d’ailleurs ici : à une époque où l’ordinateur n’existait pas, il fallait garder une écriture régulière, ne pas laisser de grands espaces ou trop resserrer les caractères, mais aussi posséder un vocabulaire fourni pour pouvoir compléter le message.

Le problème de cette méthode se trouvait également dans la transmission et la conservation de la grille de décodage : si celle-ci était volé ou perdue, c’est toute la communication qui était rompue !

Les grilles du colonel Fleissner

Restons das les grilles, mais d’un autre genre, puisque nous allons les faire tourner. Ces grilles tournantes ont été popularisées par le colonel autrichien Fleissner dans son ouvrage Handbuch der Kryptographie. Fleissner remplit cette fois une feuille de papier divisée en 36 petits carreaux, ordonnée en carré de 6 carreaux de côté.

La grille, maintenant, est également un carré de 6 carreaux de côté dans laquelle on a toutefois retiré 9 d’entre eux. Mettons que l’on souhaite crypter notre message favori : LESMATHEMATIQUESCESTFANTASTIQUE.

  • D’abord, on place la grille sur la feuille et on complète les trous des 9 premières lettres, ici LESMATHEM.
  • On tourne ensuite la grille d’un quart de tour, dans un sens ou dans l’autre. De cette manière, on masque les lettres déjà inscrites et on révèle 9 nouveaux espaces vides.
  • On continue alors le remplissage de la feuille de papier en utilisant les trous de la grille.
  • On répète le procédé jusqu’à remplir nos 36 cases. Si le message fait plus de 36 lettres, on utilise une autre grille. S’il en fait moins, on complète avec des lettres aléatoires.

Voici une animation de cette méthode :

On remplit la grille case par case, puis on la fait tourner d’un quart de tour et on recommence.

Avec cette grille, le message codé est IASQLTTEIQUSMFEAAUPNTEHTASSESLETCMA. Avec une autre grille, il serait bien sûr différent.

Pour déchiffrer le message, on utilise la même grille que l’on pose sur la feuille, puis on la fait tourner comme pour chiffrer.

La sécurité de cette méthode dépend donc du nombre de grilles qu’il est possible de fabriquer. D’abord, il convient de remarquer qu’il ne faut pas prendre 9 trous absolument au hasard. En effet, si l’on regarde le carreau tout en haut à droite, celui-ci se retrouve en haut à gauche, puis en bas à gauche et enfin, en haut à droite à mesure que nous effectuons les quarts de tours.

Il ne faut donc trouer une et une seule case parmi celles-ci : ne pas en trouver rendrait ces cases inatteignables, en trouer plusieurs demanderait d’écrire plusieurs lettres sur une même case. En observant plus en détails notre grille, on en déduit qu’il faut percer un et un seul trou de chaque couleur sur la grille suivante :

En voilà des couleurs… Pour une grille de Fleissner valable, il faut percer un et un seul trou pour chaque couleur / numéro.

Puisque nous avons 9 couleurs / numéros et que pour chacun deux il y a 4 possibilités de trous, cela donne 49 possibilités, soit 262144 grilles différentes. Alors évidemment, parmi elles il y en a de trop simples comme la grille qui consistes à enlever toute la partie supérieure droite, mais cela fait un nombre raisonnable quand on n’a pas d’ordinateur à portée de main.

D’ailleurs, il est possible d’utiliser des grilles plus grandes, toujours en trouant un quart des positions à chaque fois. En utilisant non pas 6 mais 8 carreaux de côté, il y aura alors 4294967296 possibilités de grilles.

Pour casser un tel chiffrage, il faut alors utiliser une attaque par mot probable : on suppose que le texte contient un mot et l’on essaye de recomposer la grille – ou au moins de réduire les possibilités par ce biais.

Naturellement, il est possible, comme mentionné au début, de combiner ces approches au chiffrement par substitution. Ainsi pourrez-vous espérer communiquer sans vous faire prendre ?

Pour compléter

Publié dans Cryptographie | Tagué , , , , | Laisser un commentaire

Vos papiers, s’il vous plait !

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


L’une des grandes questions de votre enfance, outre la fabrication des bébés, aura peut-être concerné les dimensions de vos feuilles de papier et de vos cahiers à l’école : le fameux format A4 mesure ainsi 21 cm de large pour 29,7 cm de long.

Alors, pourquoi ce 29,7 précisément ? Pourquoi ne pas arrondir à 21 x 30, ou même 20 x 30, histoire d’avoir de jolis nombres ?

L’explication cachée derrière cette fantaisie est -évidemment – d’ordre mathématique.

Plier et replier

S’il existe un  format A4, vous vous doutez bien qu’il existe un format A3, A2, A1 et également un format A0. A vrai dire, pour obtenir une feuille au format A3,il suffit de mettre côte a côté deux feuilles A4 en les collant suivant la longueur.

Inversement, en pliant une feuille A3 en deux, suivant sa longueur, on obtient une feuille de format A4.

Formats papier

Les différents formats de papier s’obtiennent par pliages successifs.

Ainsi, le format A1 est obtenu par un pliage d’une feuille de format A0, le A2 par deux pliages, le A3 par 3 pliages et ainsi de suite. Et puisqu’à chaque fois, la surface est divisée par deux, cela signifie que les surfaces des feuilles A1, A2, A3 sont respectivement 2, 4 et 8 fois plus petites que la surface du format A0.

Toutefois, cela ne nous en dit pas plus sur les longueurs des côtés de nos feuilles de papier. Simplement, il suffit de déterminer les mesures du format A0 pour que les mesures des formats suivants en découle.

Format A. On passe du A0 au A1 eu découpant en deux parts égales selon la longueur.

En fait, il y a deux autres propriétés que l’on souhaite avoir avec nos feuilles de papiers.

D’abord, on souhaite garder les mêmes proportions, la même valeur pour le rapport entre la longueur et la largeur. En gros, on veut que toutes nos feuilles conservent la même forme.

Prenons alors notre feuille au format A0, et notons sa longueur L et sa largeur l. En la pliant en deux selon la longueur, on obtient une feuille au format A1. La longueur de cette nouvelle feuille vaut l et sa largeur vaut la moitié de la longueur de notre feuille de départ, soit L/2.

Or, nous voulons que les formats A0 et A1 aient les mêmes proportions, ce qui se traduit par l’égalité

\frac{L}{l} = \frac{l}{L / 2}

En modifiant légèrement cette égalité, on obtient \left(\frac{L}{l}\right)^{2} = 2 soit L/l = √2, soit environ 1.414.

Ensuite, il suffit de fixer la surface d’une feuille au format A0 pour en déduire toutes nos mesures. En l’occurrence, une feuille A0 recouvre 1m², ce qui nous donne, en exprimant la longueur L et la largeur l en mètres, le système d’équations suivant :

  • L x l = 1
  • L / l =√2

On en vient aux valeurs L = \sqrt{\sqrt{2}} et l = 1 / \sqrt{\sqrt{2}}. Malheureusement, ces valeurs sont irrationnelles. Pas le choix, il faut les arrondir. Ainsi, la longueur d’une feuille A0 est d’environ 1.189 m, soit 118,9 cm tandis que sa largeur est de 0.841 m soit 84,1 cm.

De proche en proche on calcule alors les longueurs et largeurs des formats A0, A1, A2 et ainsi de suite…

Format Longueur (cm) Largeur (cm) Surface voulue (cm²) Surface réelle (cm²)
A0 118,9 84,1 10000 9999.49
A1 84,1 59.4 5000 4995.54
A2 59,4 42,0 2500 2494,80
A3 42,0 29,7 1250 1247,40
A4 29,7 21,0 625 623,70
A5 21,0 14,8 312,5 310.80
A6 14,8 10,5 156,25 155,4

Nous retrouvons bien 21 x 29,7 pour la feuille au format A4, et nous pouvons continuer ainsi, de plus en plus petit.

D’autres formats

Nous avons ici parlé du format A, mais il existe également des formats B et C.

Ainsi, les dimensions de la feuille B0 sont de 1.414 mètres de longueur et 1 mètre de largeur, puis on passe aux formats B1, B2 et ainsi de suite en pliant selon la longueur.

Outre le fait d’avoir une « valeur ronde » pour la largeur de la feuille, ce format est aussi la moyenne géométrique du format A : pour passer du format B0 au format A0, on procède à la même réduction que pour passer du format A0 au format B1, du  B1 au A1, du A1 au B2 et ainsi de suite. Les formats A et B s’intercalent ainsi régulièrement : il faut toujours multiplier ou diviser les mesures par la même quantité pour passer de l’un à l’autre.

Ce format est toutefois bien moins utilisé que le format A ou que le C, employé pour les enveloppes. Pour obtenir une enveloppe au format C0, il faut prendre cette fois la moyenne géométrique d’une feuille A0 et d’une feuille B0. Ainsi, une enveloppe C0 peut contenir une feuille A0 sans que celle-ci ne soit pliée. La même opération permet d’obtenir les formats C1, C2, C3 qui s’intercalent à chaque fois entre les formats A et B.

Format B Format C

Et puisque nous parlons d’enveloppes, autant parler d’affranchissement. Classiquement, les feuilles que nous utilisons tous les jours ont un grammage de 80 g/m². Or, nous l’avons vu, une feuille A4 correspond à 1/16 d’une feuille A0 qui elle, fait environ 1m² et pèserait donc 80 grammes.

Un petit argument de proportionnalité et hop : 80 / 16 = 5, votre feuille A4 pèse donc 5g. Un timbre seul permettant d’affranchir jusqu’à 20g, vous en déduirez combien de feuilles vous pouvez glisser dedans – mais attention à ne pas oublier de prendre le poids de l’enveloppe en compte !

Pour compléter

  • La page Wikipédia des formats de papier, d’où proviennent ces images
  • Un article du blog Wattsupscience sur les formats A
Publié dans Curiosités et récréation | Tagué , , , | Laisser un commentaire

Le code secret

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


Comment communiquer sans être lu par des indésirables ? Cette question est à la base de ce que l’on appelle la cryptographie, destinée à protéger vos messages des regards indiscrets. Son principe est simple : remplacer le message, l’information d’origine, par un nouveau message dit chiffré que seul votre destinataire devrait être en mesure de décoder.

Tout ceci semble simple sur le papier, et pourtant… Une technique trop simple rend vulnérable votre message, alors qu’un procédé trop compliqué rend difficile sa traduction par votre correspondant.

Note : dans la suite de l’article, j’utiliserai parfois le mot « coder » ou le mot « chiffrer ». Sachez qu’ici, ils désignent la même chose, alors ne soyez pas perturbés !

Le chiffre de César

La première chose qui vient à l’esprit lorsque l’on parle de coder un message sera peut-être de tout bêtement remplacer une lettre par une autre. C’est d’ailleurs sur cette idée que se base le chiffre dit de César.

Prenons un message en clair, par exemple : « Les Mathématiques, c’est fantastique ».

Dans un premier temps, nous allons supprimer les espaces et la ponctuation. Après tout, ce sont là des signes bien trop distinctifs pour être conservé, et nous souhaitons un minimum protéger notre message. Nous souhaitons donc envoyer à notre correspondant le message : LESMATHEMATIQUESCESTFANTASTIQUE.

Le chiffrage par Code César consiste simplement à décaler toutes les lettres de cette phrase d’un certain nombre de crans fixé à l’avance. Par exemple, en décalant les lettres de trois crans, le L devient un O, le E devient un H et ainsi de suite… Si l’on doit coder la lettre Z, il suffit de reprendre au début de l’alphabet : Z -> A -> B -> C. Le Z devient donc un C.

Notre phrasé codée est donc OHVPDWKHPDWLTXHVFHVWIDQWDVWLTXH. Pour le déchiffrer, rien de plus simple : il suffit de faire l’opération inverse, c’est-à-dire de prendre, pour chaque lettre, celle qui vient trois crans avant.

Vous l’aurez sans doute compris : ce codage est trop simple ! Même sans connaître le décalage, il n’existe que 25 possibilités à tester, une broutille. Nous pourrions imaginer corser l’affaire en n’utilisant pas l’alphabet classique ABCD… mais plutôt un autre alphabet, par exemple l’ordre d’apparition des lettres sur un clavier AZERTY. En décalant de trois lettres vers la droite, le A devient R, le Z devient T, le E devient Y et ainsi de suite.

L’ennui, c’est qu’une lettre est toujours codée de la même manière. Pour déchiffrer le code, il suffit alors de regarder les fréquences d’apparition de chaque lettre, et de les analyser. En effet, en Français, la lettre la plus courante dans un texte est la lettre « E ». Il y a donc de fortes chances que la lettre qui apparaisse le plus souvent dans un texte codé de la sorte corresponde à la lettre qui code le E du message de départ.

S’il s’agit d’un code de César classique, alors le décalage est trouvé, nous pouvons retrouver le message d’origine sans peine. Regardons le message codé suivant :

DORUVTXLOUHJDUGDLWVRQHQIDQWVDPXVHUDHPSLOHUGHVFXEHVOHPDW
KHPDWLFLHQGXGOHBODQJIRUGVHSULWDREVHUYHUSOXVHQGHWDLOVODW
RXUDLQVLIRUPHHFRPSRVHHGHWURLVSDLUHVGHFXEHVGHFRXOHXUVGLIIH
UHQWHVGLVRQVMDXQHURXJHHWEOHXFHOOHFLSUHVHQWDLWXQHSURSUL
HWHTXLOWURXYDHWRQQDQWHHQWUHOHVGHXAFXEHVMDXQHVVHWURXY
DLWXQFXEHHQWUHOHVGHXAURXJHVVHQWURXYDLHQWGHXAHWHQWUHO
HVGHXAEOHXVVHQWURXYDLHQWWURLV

Comptons maintenant le nombre d’apparitions de chacune des lettres dans ce message codé.

Comptage code César

Comptage des lettres dans le message codé. La lettre k apparaît le plus souvent.

La lettre « K » est la plus fréquente : il y a de fortes chances que ce soit le codage de la lettre « E ». Pour passer du « E » au « K », il y a un décalage de 5 lettres. Il est alors possible de décoder le message, qui se trouve être le début du précédent article sur le problème de Langford.

Si l’alphabet utilisé est un peu plus complexe, il faut fournir davantage de travail. Par exemple, une fois ce E trouvé, on peut également regarder autour. Le E est souvent associé au N, il se peut que les lettres autour du E codent donc le N du message clair, et ainsi de suite. Bref, il faut compliquer notre méthode.

Le carré de Vigenère

L’idée du chiffrage de Vigenère est d’utiliser plusieurs décalages différents, selon la position de la lettre dans le message. Nous allons pour cela avoir recours à une clé -c’est-à-dire un mot qui nous servira à chiffrer et à déchiffrer notre message – et à un tableau.

Pour la clé, prenons par exemple le mot « AUTOMATHS ». Nous allons écrire le message à coder et la clé l’un au-dessus de l’autre. Evidemment, la clé n’est pas aussi longue que le message, alors nous allons la répéter jusqu’au bout, ce qui donne ceci :

Pour chiffrer le message, il suffit alors de décaler la lettre du message clair d’un nombre de cran qui dépend de la lettre de la clé correspondante, auquel on retire 1.

  • Par exemple, la première lettre du message clair est L, celle de la clé est A, qui est la 1ère lettre de l’alphabet. Je décale donc le L de (1-1) = 0 ce qui me donne toujours la lettre L.
  • Pour la suivante, E, la lettre de la clé est U, qui est la 21ème lettre de l’alphabet : je décale donc le E de 21 – 1 = 20 crans, ce qui me donne un Y, et ainsi de suite.

En codant le même message que tout à l’heure, nous obtenons :

AFHFEQNPDRYZODDTPLSIGSZFTULSUFIEEKHWMJBZQRW

LKCOUSELXTSTBXAMTBJAEHWIPLXFDAHZTARWZWPLBH
MOUZWRPXFBLNZWNXXHMIEZDANHIDABUKIZHFYEXJG
MJHGQEWLLRIBGBABYWSXXQGBXZVEWHIXENYKDCYTQR
XULEMWWEOGZBAOGSDONNWENUZQUVLDLYVWBRXZW
NNTWFUGLHRIIFUEMLIUCEHDONCSENHBZAGAWEHMFQ
LXZVEOQQGBXZBAOGSESXAJOOOOUTNUUUVXSZTKLDEM
WSGXKVMGYLGQNMYGUPTWQNMKWURXHQNMYWLYLR
QUQIDEOLGQNMYGUPTWQNMAJOCL

Le procédé peut ainsi être résumé en un tableau à double entrée : une pour la lettre du message à chiffrer, l’autre pour celle de la clé.

Tableau de Vigenère

La lettre M du message en clair est codée par la lettre O de la clé. La lettre du message codé sera donc le A.

Encore une fois, il est possible d’utiliser un autre alphabet que celui d’origine, ou une autre règle pour la conversion. Le message sera vraisemblablement plus compliqué à décoder : nous pouvons le voir en regardant de nouveau les fréquences d’apparition des lettres dans le message codé ; aucune ne semble beaucoup plus importante que les autres.

Fréquence d’apparition des lettres dans un message codé par le chiffre de Vigenère.

Pour décoder le message, il suffit alors de mettre le message codé et la clé l’un en-dessous de l’autre. Pour chaque lettre de la clé, on cherche alors la lettre du message codé, puis on remonte la colonne pour trouver la lettre du message clair.

Par exemple, si mon message codé présente un « S » codé avec la clé « K », je regarde où se situe le « S » sur la ligne du « K » dans mon tableau : cela correspond à la colonne du I.

Cette méthode est-elle pour autant infaillible ? Pas vraiment…

Ici, notre clé a 9 lettres, ce qui signifie que toutes les 9 lettres, nous utiliserons la même lettre en guise de clé. Autrement dit, dans ce cas, le chiffre de Vigenère n’est rien d’autre que 9 codes César mis côte à côte. Il est donc possible de les casser 1 par 1 pour tout décoder.

Trouver la clé

Pour autant, en règle générale, la clé est inconnue, et il n’est donc pas possible de savoir combien de décalages différents ont été utilisés pour coder le message. Il serait envisageable de toutes les tenter, de regarder si l’on arrive à quelque chose qui a du sens, mais nous sommes plus malins, n’est-ce pas ?

Rappelons donc le message que nous devons décoder :

AFHFEQNPDRYZODDTPLSIGSZFTULSUFIEEKHWMJBZQRWLKCOUSELXTSTBXAM
TBJAEHWIPLXFDAHZTARWZWPLBHMOUZWRPXFBLNZWNXXHMIEZDANHIDABU
KIZHFYEXJGMJHGQEWLLRIBGBABYWSXXQGBXZVEWHIXENYKDCYTQRXULEM
WWEOGZBAOGSDONNWENUZQUVLDLYVWBRXZWNNTWFUGLHRIIFUEMLIUCEH
DONCSENHBZAGAWEHMFQLXZVEOQQGBXZBAOGSESXAJOOOOUTNUUUVXSZ
TLDEMWSGXKVMGYLGQNMYGUPTWQNMKWURXHQNMYWLYLRQUQIDEOLGQN
MYGUPTWQNMAJOCL

Dans ce message codé, il est possible de déceler certaines suites de trois lettres – ou trigrammes – qui reviennent à différentes positions. Il y a alors deux possibilités :

  • soit il y avait deux trigrammes identiques dans le texte d’origine qui ont tous deux été codé par la même partie de la clé, aboutissant à deux trigrammes encore identiques dans le message codé.
  • soit deux trigrammes différents du message clair ont abouti par un heureux hasard à deux trigrammes identiques dans le message codé.

La probabilité de cette seconde possibilité est très faible, alors nous pouvons supposer que nous sommes dans le premier cas. En relevant alors les positions des trigrammes répétés, nous avons :

  • XZV aux positions 152 et 251
  • YGU aux positions 306 et 342

L’écart entre les deux répétitions des trigrammes est donc respectivement de 99 et 36. Or, nous avons supposé que les deux XZV étaient issus du même morceau de clé, ce qui signifie que 99 est forcément un multiple de la longueur de notre clé. C’est la même chose pour 36.

Ainsi, la longueur de notre clé est vraisemblablement un diviseur commun à 99 et à 36, ce qui ne laisse que peu de possibilités : 1, 3 ou 9. Et en l’occurrence, la longueur de la clé AUTOMATHS est de 9. Bingo, il ne reste plus qu’à décoder le tout !

Plus de complexité…

Le chiffre de Vigenère a résisté pendant près de trois siècles avant d’être enfin brisé mais est désormais facilement mis en défaut à cause de ces répétitions de la clé. Aussi, pour renforcer la sécurité, il faut utiliser une clé toujours plus longue, quitte à ce que celle-ci fasse la longueur du texte. Seulement, comment transmettre cette clé maintenant ?

C’est ici qu’intervient l’astucieux chiffrement autoclave : dans ce procédé, le message en clair fait lui-même partie de la clé !

Plus précisément, il existe bien un mot-clé, comme pour le chiffre de Vigenère, et nous choisirons toujours AUTOMATHS ici. Seulement, plutôt que de répéter cette clé à l’infini, il suffit, une fois la clé terminée, d’utiliser le message clair.

Une fois la clé placée, on répète le message lui-même : celui-ci fera office de clé pour la suite.

Pour chiffrer, on utilise alors le tableau de Vigenère. Pour décoder maintenant, on déchiffre les premières lettres grâce à la clé, puis on peut alors déchiffrer la suite grâce à ces premières lettres décodées et ainsi de suite.

Ici, plus de répétition, la méthode est robuste et tient le coup. Le seul souci, c’est qu’une seule erreur dans la transmission du message le rend impossible à déchiffrer. Attention à ne pas se tromper.

Naturellement, ce code n’est pas infaillible : le nombre de clés possibles n’est pas si élevée, mais il n’existe aucune autre astuce que de toutes les tester – hormis essayer les plus probables, mais vous ne feriez pas ça n’est-ce pas ?

Pour compléter

  • Le site Dcode vous permet de chiffrer et déchiffrer le message de votre choix avec la méthode que vous préférez
  • Un site sur le chiffre de Vigenère qui contient un mémoire assez complet sur la question
Publié dans Cryptographie | Tagué , , , | Laisser un commentaire

Le problème de Langford

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


Alors qu’il regardait son enfant s’amuser à empiler des cubes, le mathématicien Dudley Langford se prit à observer plus en détails la tour ainsi formée. Composée de trois paires de cubes de couleurs différentes – disons jaune, rouge et bleu – celle-ci présentait une propriété qu’il trouva étonnante : entre les deux cubes jaunes se trouvait un cube, entre les deux rouges s’en trouvaient deux, et entre les deux bleus s’en trouvaient trois.

Solution au problème de Langford pour 3 couleurs

L’histoire aurait pu s’arrêter là, mais les mathématiciens s’arrêtent rarement aux cas particuliers ! Non, le mathématicien est un éternel insatisfait qui cherche toujours une généralisation de son problème.

Prenons alors un ensemble composé de n paires de cubes, chacune d’une couleur différente des autres paires. Pour que tout soit plus commode, nous allons numéroter ces couleurs de 1 à n, et pourrons alors désigner chaque cube soit par sa couleur, soit par un numéro.

Est-il alors possible de disposer ces cubes en ligne de telle sorte qu’il y ait exactement 1 espace entre les cubes de la couleur 1, 2 espaces entre les cubes de la couleur 2, 3 espaces entre les cubes de la couleur 3, et ainsi de suite ?

En essayant avec 4 couleurs, nous pouvons, avec un peu de réflexion, arriver à un résultat convenable. A vrai dire, pour 3 ou 4 couleurs, le résultat obtenu est unique – si l’on considère que lire la ligne de droite à gauche ne donne pas une solution différente. Vous devriez donc parvenir à cette solution, ou à son écriture « renversée » :

Solution au problème de Langford pour 4 couleurs.

Malheureusement, pour 5 couleurs, on piétine. Même chose avec 6 couleurs, alors que lorsque l’on en prend 7, il est possible de trouver plusieurs arrangements qui respectent les règles de Langford.

Deux solutions au problème de Langford à 7 couleurs.

Au total, on comptabilise 26 solutions au problème de Langford à 7 couleurs, 150 solutions pour le problème à 8 couleurs… Et de nouveau aucune pour 9 et 10 couleurs !

Le problème ne trouve aucune solution pour 13 et 14, pour 17 et 18, 21 et 22, et ainsi de suite…

Des puzzles parfois impossibles

Attention, voilà les lettres !

Considérons que nous avons n paire de cubes, soit 2n au total, que nous souhaitons faire loger dans autant d’emplacements. Nous devons ainsi créer des espacements de 1 cube, 2 cubes, 3 cubes, et ainsi de suite jusqu’à n cubes.

Premièrement, notons que parmi les nombres entiers entre 1 et 2n, il y a autant de nombres pairs que de nombres impairs. Raisonnons alors selon les espaces à laisser entre les cubes.

Si je place le premier cube portant le numéro a à la position x, alors l’autre cube sera placé à la position x + a + 1. En effet, entre les nombres x et x + a + 1, il y a exactement a cubes. Par exemple, si je place le cube 5 en position 2, le second cube portant le numéro 5 sera à a position 5 + 2 + 1, soit 8.

Si a est pair, alors les nombres x et x + a + 1 seront de parité différentes : si l’un est pair, l’autre sera impair. Sur la première solution donnée pour 7 couleurs, on voit que les cubes portant le numéro 4 se trouvent aux positions 2 (pair) et 7 (impair).

Inversement, si a est impair, alors les nombres x et x + a + 1 seront de même parité : soit tous les deux pairs, soit tous les deux impairs. On l’a vu, il nous faut autant de positions paires que de positions impaires dans notre arrangement : par conséquent, chaque a qui produit un écart entre deux positions paires doit être en quelque sorte « compensé » par un a qui produit un écart entre deux positions impaires.

On en conclut que le nombre de a impairs doit, lui, être pair ! Ceci arrive uniquement lorsque l’entier n ou l’entier n + 1 est un multiple de 4.

Prenons alors le cas de 14 couleurs, soit 28 cubes. 14 et 15 ne sont pas des multiples de 4, il n’est donc pas possible de résoudre le problème à 14 couleurs

Nous pouvons vérifier à la main : il doit donc y avoir des écarts de 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 et 14 cubes. Les nombres impairs sont 1, 3, 5, 7, 9, 11, 13 : il y en a 7, un nombre impair.

Construire une solution

Cette démonstration permet simplement d’affirmer l’impossibilité de résoudre certains puzzles, mais elle n’affirme en aucun cas que tous les autres peuvent trouver une solution.

Rassurez-vous, il existe bel et bien un moyen de construire une telle solution dans les autres cas, donnée par Roy Davies. Pour trouver sa solution, celui-ci a remarqué certains motifs particuliers, qu’il a ensuite complété.

Par exemple, la suite 4 2 _ _ 2 4 respecte les règles de Langford. On peut par ailleurs rajouter un 6 de chaque côté sans pour autant enfreindre une règle, et le motif devient alors 6 4 2 _ _ 2 4 6… Puis on peut faire 8 6 4 2 _ _ 2 4 6 8 et ainsi de suite avec tous les nombres pairs. La même chose peut être faite en utilisant les nombres impairs, aboutissant par exemple à la suite 7 5 3 1 _ 1 3 5 7. Davies va ainsi mélanger les motifs avec les nombres pairs et impairs, en les séparant en deux tas.

Les lignes rouges relient des nombres pairs, les lignes bleues, des nombres impairs. La hauteur de la ligne dépend de la valeur du nombre. Source : Langford’s problem, remixed, John Miller.

Voyons par exemple la méthode pour n = 20 = 4 x 5.

D’abord, on met de côté les trois plus grands nombres, nous mettrons de côté 18, 19 et 20. Nous mettrons également de côté le nombre 2 x 5 – 1, soit le nombre 9

Nous allons maintenant construire 4 sous-ensembles avec les nombres restants :

  • les nombres pairs supérieurs ou égaux à n/2 : 10, 12, 14, 16
  • les nombres impairs plus grands que n/2 : 11, 13, 15, 17
  • les nombres pairs strictement inférieurs à n/2 : 2, 4, 6, 8
  • les nombres impairs strictement inférieurs à n/2 : 1, 3, 5, 7

Puis, il faudra utiliser le principe montré plus haut et réorganiser ces nombres pour obtenir des combinaisons « valables ». Nous obtenons alors 4 séquences :

  • 16 14 12 10 _ _ _ _ _ _ _ _ _ _ 10 12 14 16
  • 17 15 13 11 _ _ _ _ _ _ _ _ _ _ _ 11 13 15 17
  • 8 4 6 2 _ _ 2 4 6 8
  • 7 5 3 1 _ 1 3 5 7

Une fois arrivés ici, nous allons emboîter la petite séquence impaire dans la grande séquence paire, et inversement. Nous mettrons les deux côte à côte avec un espace au milieu. Cela nous donne alors la séquence qui suit :

16 14 12 10 _ 7 5 3 1 _  1 3 5 7 10 12 14 16 _ 17 15 13 11 _ 8 6 4 2 _ _ 2 4 6 8 11 13 15 17 _ _

Il suffit alors de compléter les trous avec les paires des trois plus grands nombres, dans l’ordre. Les trous restants correspondent alors au 9 que nous avons retiré.

16 14 12 10 18 7 5 3 1 19  1 3 5 7 10 12 14 16 20 17 15 13 11 18 8 6 4 2 9 18 2 4 6 8 11 13 15 17 20

Vous pouvez reprendre le principe pour n’importe quel nombre de la forme n = 4k. Pour ceux de la forme n = 4k – 1, reprenez le même principe en enlevant les deux nombres les plus grands, ainsi que le nombre 2k – 1.

Pour compléter

  • La note de Dave Moore qui essaye de trouver un autre procédé pour construire une suite valide.
  • Une page qui recense toutes les avancées faites sur les problèmes de Langford et leurs généralisations.
  • Une animation Geogebra de la construction d’une suite valide, utilisant la méthode de Davies
Publié dans Curiosités et récréation | Tagué , , , | 1 commentaire