Pavages rythmiques parfaits II

L'applet ci-dessous permet d'obtenir des pavages par des progressions de longueur 2, 3 ou 4 et peut-être plus, (mais java est bien lent).
Pour que l'applet fonctionne, il est impératif que vous ayez installé java (la version actuelle est compilée par le javac de j2sdk1.4.2_05).
Le nombre de solutions est volontairement limité à 5 mais en réessayant, vous en aurez sûrement d'autres en cliquant sur [Cherche] pour relancer l'application .
Pensez à utiliser les boutons [ |<< ]  [ <-- ]  [ --> ]  [ >>| ]  pour naviguer d'une solution à l'autre.

Les solutions sont présentées dans un ordre aléatoire (mais leurs apparitions ne sont pas équiprobables), pour deux raisons 1) généralement on obtient plus rapidement une solution dans les cas difficiles, 2) les solutions obtenues sont mélangées et se ressemblent moins entre elles, en particulier lorsque vous recliquez sur [Cherche]

La notation utilisée ici est celle que l'on emploie pour écrire les suites de Skolem, dans 6 9 11 8 1 1 6 2 4 2 9 8 4 11 les nombres indiquent les écarts, le 6 en première position indique que le prochain est à la sixième position qui suit, pour le 9 avancez de 9 ... (Dans la notation habituelle des mots de Langford, qui diffère de celle-ci, les nombres indiquent les intermédiaires et sont plus petits d'une unité).

dimension n =      ordre k =

/Suites et systèmes de Skolem/
C'est en observant son fils jouer avec des cubes de couleurs que le mathématicien écossais Dudley Langford imagina de les placer comme sur l'image ci-contre, en intercalant entre deux cubes de même couleur des nombres différents de cubes d'autres couleurs.
Le mathématicien et logicien norvégien Thoralf Skolem (1887-1963) utilisait des objets mathématiques équivalents pour construire des systèmes triples de Steiner.



Certaines des suites obtenues par l'applet seront parfois des suites de Skolem ou des suites de Langford, mais le plus souvent les distances ne forment pas un ensemble de nombres consécutifs, les suites de Skolem ou de Langford sont plus rares et n'existent d'ailleurs pas pour toutes les valeurs de n.

Lorsque l'ensemble des distances est l'ensemble de tous les nombres de 1 à n comme dans 4 1 1 3 4 2 3 2, on a une suite de Skolem. Il s'agira d'une suite de Langford lorsque les distances iront de 2 à n+1 (ex : 2 8 2 3 6 7 3 4 5 8 6 4 7 5) ou plus généralement de m à m+n-1 (ex. : 7 4 11 12 14 4 13 7 8 5 10 6 9 11 5 12 8 6 14 13 10 9 où m=4 et n=11. Il existe des programmes de construction (formules) pour construire de telles suites (Skolem 1957) à tous les ordres n pour lesquels il existe de telles suites (n congru à 0 ou à 1 modulo 4 lorsqu'il s'agit de couples).
On généralise ces définitions aux triplets 4 10 8 6 4 9 7 5 4 6 8 10 5 7 9 6 3 5 8 3 7 10 3 9 (Langford) ou à des quadruplets 7 19 1 1 1 1 3 7 16 3 9 6 3 20 7 3 22 6 13 9 19 7 24 6 16 18 23 21 9 6 12 13 15 20 17 10 14 9 22 19 16 11 12 18 13 10 24 15 21 23 14 17 11 20 12 10 16 13 19 8 22 18 15 11 14 10 12 8 17 21 24 5 23 20 11 8 5 15 14 18 4 5 22 8 4 17 5 2 4 2 21 2 4 2 24 23 (Skolem).
Une suite de Langford d'ordre n permet d'obtenir une suite de Skolem d'ordre n+1 comme dans l'exemple suivant 7 4 2 3 2 4 3 7 (Langford) qui permet d'écrire 1 1 7 4 2 3 2 4 3 7 et 7 4 2 3 2 4 3 7 1 1 (Skolem).
En utilisant la notation habituelle des suites de Langford, on écrirait 6 3 1 2 1 3 2 6 et non 7 4 2 3 2 4 3 7 en comptant les éléments intercalés et non les différences de positions.
Pour l'instant personne n'a semble-t'il trouvé de suites de quintuplets ou plus, ni prouvé qu'il n'en existe pas.

Le tableau ci-dessous donne quelques uns des résultats obtenus. Le nombre n de progressions se lit dans la colonne de gauche, les longueurs k des progressions sont notées sur la ligne du haut.
Les cases du tableau contiennent
soit le nombre de pavage (par exemple 0 ou encore 444 etc.),
soit '=>1' lorsqu'une solution ou plus ont été trouvées mais que le nombre total de solutions est inconnu (car la recherche prendrait trop de temps),
soit encore le signe '-' lorsque la recherche n'a pas été entreprise ou que la durée accordée à celle-ci n'a pas permis de trouver une solution.