cubes de Langford

COMBINATOIRE

Le problème des cubes de Langford est une récréation combinatoire imaginée par Dudley Langford, mathématicien écossais.
Il s’agit de placer six cubes : deux rouges (R), deux bleus (B) et deux jaunes (J), sur une rangée horizontale de sorte qu’il y ait un cube entre les bleus, deux cubes entre les jaunes et trois cubes entre les rouges. Il existe une solution unique : R B J B R J
Avec quatre paires de cubes (on ajoute des cubes verts) il y a aussi une unique solution : V B R B J V R J

Ce jeu peut être étendu, on l’appelle alors suite de Langford : trouver une suite de nombres dans laquelle il existe un nombre entre deux 1, deux nombres entre deux 2, trois nombres entre deux 3, quatre nombres entre deux 4, etc.
Il n’y a pas de solution pour 5 paires, ni pour 6 paires.
Il y a 26 suites différentes avec sept paires, 150 suites avec huit paires.

Ce jeu est une variante de la suite de Skolem .
Ce problème, dit aussi problème de Skolem-Langford a été généralisé à des triplets et à des quadruplets et à des ensembles de distances non consécutives.