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

Publicité