cubes de Langford

Alignez deux cubes bleus, deux jaunes et deux rouges. Les bleus doivent laisser un cube entre eux, les jaunes deux cubes et les rouges trois cubes. Chaque emplacement choisi pour une couleur réduit donc les places disponibles pour les autres.

L'arrangement R B J B R J satisfait les trois écarts à la fois. La suite de Langford remplace simplement les couleurs par des nombres : deux exemplaires du nombre 2, par exemple, encadrent exactement deux autres termes.

Les cubes de Langford forment un problème de placement sous contraintes. Dans la version originale, six cubes sont répartis en trois paires de couleurs. Les deux cubes bleus encadrent exactement un cube, les deux jaunes exactement deux cubes et les deux rouges exactement trois cubes. La rangée R B J B R J respecte simultanément ces trois conditions.

La généralisation numérique emploie deux occurrences de chaque entier, de 1 jusqu'au nombre de paires choisi. Pour chaque entier k, les deux occurrences de k ont exactement k termes entre elles. Leur écart de positions vaut donc k + 1. Les lettres B, J, R et V jouent respectivement le rôle des nombres 1, 2, 3 et 4 dans les exemples colorés. Avec quatre paires, V B R B J V R J satisfait toutes les contraintes.

Toutes les tailles n'admettent pas de solution : la source indique qu'il n'en existe aucune avec cinq ou six paires, contre 26 avec sept paires et 150 avec huit lorsque deux rangées inversées sont identifiées. Le problème est présenté comme une variante de la suite de Skolem et s'étend aussi à des multiensembles de triplets, de quadruplets ou à des distances non consécutives.

On veut contrôler la rangée à quatre paires V B R B J V R J. Les données sont les huit positions numérotées de 1 à 8 et la correspondance B = 1, J = 2, R = 3, V = 4.

1. Repérez B aux positions 2 et 4. La position 3 est entre elles : la paire bleue encadre bien un cube.

2. Repérez J aux positions 5 et 8. Les positions 6 et 7 donnent exactement deux cubes intermédiaires.

3. Repérez R aux positions 3 et 7. Les positions 4, 5 et 6 donnent exactement trois cubes intermédiaires.

4. Repérez V aux positions 1 et 6. Les positions 2, 3, 4 et 5 donnent exactement quatre cubes intermédiaires.

Les quatre contraintes sont vérifiées, donc la rangée est une solution. Le contrôle est refaisable en soustrayant les positions de chaque paire : on obtient 2, 3, 4 et 5, soit toujours une unité de plus que le nombre associé.

Avec des cubes, on peut chercher une rangée en plaçant d'abord la paire qui exige le plus grand intervalle. Dès qu'une couleur ne dispose plus de deux emplacements compatibles, il faut revenir sur un choix antérieur plutôt que poursuivre cette branche.

Pour contrôler une proposition, il suffit de numéroter les positions. Si les deux occurrences de k sont aux positions p et q, avec p avant q, la différence q − p doit valoir k + 1. Ce test évite de recompter visuellement les termes intermédiaires.

Pour comparer plusieurs réponses, il faut annoncer si une rangée lue en sens inverse compte comme une seconde solution. Sans cette convention, le mot « unique » peut prêter à confusion, car le renversement conserve tous les écarts.

Une suite de Skolem est une notion voisine, mais le texte source présente le problème de Langford comme une variante, non comme un synonyme. Pour trancher, il faut donc vérifier la règle d'écartement employée au lieu de se fier au seul fait que les nombres apparaissent par paires.

L'existence n'est pas automatique. Avec cinq ou six paires, aucune suite de Langford n'existe ; multiplier les essais ne peut donc pas produire une solution. Il faut d'abord distinguer une recherche difficile d'un cas déclaré impossible.

Le nombre placé entre deux occurrences et leur écart de positions ne sont pas identiques. S'il y a k termes entre les deux k, leurs positions diffèrent de k + 1. Pour k = 4, un écart de quatre positions ne suffit pas : il en faut cinq.

Le renversement d'une solution conserve toutes les contraintes. Une annonce d'unicité doit donc préciser si deux rangées inversées sont identifiées ; à défaut, il faut contrôler la convention de comptage avant de comparer des totaux.

Les nombres 26 pour sept paires et 150 pour huit paires concernent la version à deux occurrences et aux distances consécutives décrite ici, en identifiant deux rangées inversées. Les généralisations à des triplets, quadruplets ou distances non consécutives changent les données du problème ; ces totaux ne s'y transfèrent pas.

La question peut être prolongée en changeant une seule règle à la fois : remplacer les paires par des triplets ou des quadruplets, ou imposer un ensemble de distances non consécutives. Chaque modification définit un nouveau problème de placement et oblige à réexaminer l'existence ainsi que le comptage des solutions.