suite de Skolem

Écrivons deux fois chacun des nombres 1, 2, 3 et 4 dans huit cases. Le défi est de régler l'écart entre les deux copies de chaque nombre. Dans la suite 4, 1, 1, 3, 4, 2, 3, 2, les deux 1 occupent des cases voisines. Les deux 4 sont placés aux cases 1 et 5 : leurs numéros de case diffèrent de 4. Une suite de Skolem est précisément un arrangement où cette règle vaut simultanément pour tous les nombres utilisés.

Une suite de Skolem d'ordre n est un arrangement de longueur 2n. Chacun des entiers k allant de 1 à n y apparaît exactement deux fois. Si i est l'indice de sa première occurrence et j celui de la seconde, avec i inférieur à j, le critère est $j-i=kj-i=k$. Autrement dit, l'écart entre les numéros des deux cases vaut k ; il y a donc k − 1 cases strictement entre elles.

Pour l'ordre 4, la suite (4, 1, 1, 3, 4, 2, 3, 2) satisfait ces contraintes pour les quatre valeurs. Une suite de Langford suit une convention voisine, mais l'écart des indices y vaut k + 1. Les suites de Skolem ont été décrites par le mathématicien norvégien Thoralf Skolem (1887–1963). La source ne donne pas de formule générale pour compter les suites de Skolem ou de Langford d'un ordre donné : leur dénombrement repose sur des algorithmes d'énumération.

La structure réunit quatre données nécessaires. L'ordre n fixe à la fois les valeurs autorisées, de 1 à n, et la longueur totale 2n. Chaque valeur k fournit une paire d'occurrences. Les indices i et j localisent cette paire dans la suite. Enfin, la contrainte j − i = k lie la valeur inscrite à l'écart de ses positions.

Ces dépendances empêchent de choisir séparément le contenu et les places : déplacer une occurrence peut satisfaire une paire tout en en bloquant une autre. L'ordre de lecture de gauche à droite sert à numéroter les cases ; la couleur ou la manière de tracer les liaisons ne définit pas la suite. Les 2n cases, les deux copies de chaque entier et tous leurs écarts suffisent à construire puis à vérifier l'objet.

Vérifions l'exemple d'ordre 4. Les données sont huit cases numérotées de 1 à 8 et l'arrangement (4, 1, 1, 3, 4, 2, 3, 2). Chaque valeur de 1 à 4 doit apparaître deux fois, puis l'écart de ses indices doit être égal à cette valeur.

1. Les 1 sont aux indices 2 et 3 : 3 − 2 = 1.
2. Les 2 sont aux indices 6 et 8 : 8 − 6 = 2.
3. Les 3 sont aux indices 4 et 7 : 7 − 4 = 3.
4. Les 4 sont aux indices 1 et 5 : 5 − 1 = 4.

Les quatre contrôles réussissent et chaque nombre figure exactement deux fois : l'arrangement est bien une suite de Skolem d'ordre 4. Le contrôle est refaisable en entourant une paire, en lisant ses deux numéros de case, puis en soustrayant le plus petit du plus grand.

Pour contrôler un arrangement proposé, on relève les deux indices de chaque valeur et on calcule leur différence. Ce test direct convient lorsqu'une suite précise est déjà donnée ; une simple vérification visuelle risque de confondre l'écart des indices avec le nombre de cases intermédiaires.

Pour rechercher toutes les suites d'un ordre fixé, on emploie une énumération qui essaie des placements et rejette ceux qui violent une contrainte. Cette démarche est préférable au contrôle manuel quand il faut dénombrer les solutions, puisque la source ne fournit pas de formule générale pour ce nombre.

Suite de Langford. Le test décisif porte sur l'écart des indices d'une paire k. Il vaut k dans une suite de Skolem, mais k + 1 dans une suite de Langford. Ainsi, dans l'exemple d'ordre 4, les deux 4 placés aux indices 1 et 5 satisfont la règle de Skolem, car 5 − 1 = 4 ; cette paire ne satisfait pas la règle de Langford, qui demanderait un écart de 5.

Compter les cases au lieu des écarts. Entre les indices 1 et 5, il n'y a que trois cases strictement intermédiaires, mais l'écart des indices vaut 4. Il faut soustraire les numéros des deux positions, conformément au critère j − i = k.

Valider les distances sans contrôler les multiplicités. Quelques paires bien espacées ne suffisent pas. Le symptôme est une valeur absente ou présente plus de deux fois ; il faut aussi vérifier que chacun des entiers de 1 à n apparaît exactement deux fois dans les 2n cases.

Chercher une formule de dénombrement fournie par la définition. La règle caractérise chaque solution, mais la source précise qu'aucune formule générale n'est disponible pour leur nombre. Pour un ordre fixé, il faut donc recourir à un algorithme d'énumération plutôt que déduire le compte de la seule longueur 2n.

Une piste naturelle consiste à transformer la définition en problème de recherche : pour chaque valeur k, choisir deux indices distants de k, sans réutiliser une case. Cette formulation montre pourquoi les contraintes interagissent et pourquoi une procédure d'énumération doit éliminer progressivement les placements incompatibles. Elle invite aussi à comparer différentes stratégies pour parcourir les placements possibles sans compter deux fois le même arrangement.