Suites de Skolem

Le mathématicien norvégien Thoralf Albert Skolem (1787 - 1963) a travaillé en algèbre, en théorie des nombres (équations diophantiennes) et en logique. Il est le fondateur de la théorie des modèles.
Théorème de Löwenheim-Skolem : toute axiomatique du premier ordre non contradictoire admet un modèle dénombrable. (D'où le paradoxe de Skolem car ce modèle dénombrable contient des ensembles non dénombrables).

Prenez les n entiers consécutifs 1, 2, 3, 4, ..., n-1, n et écrivez les à la suite les uns des autres, deux fois chacun, comme ceci : 4 5 1 1 4 3 5 2 3 2
ou encore comme cela : 3 5 6 3 8 4 5 7 6 4 1 1 8 2 7 2.
Avez-vous vu les particularités de ces listes ? Regardez comment sont placés les deux 1, puis regardez les positions des 2...

Dans ces écritures, lorsque l'entier a se trouve aux deux positions x (la plus petite) et y (la plus grande), on a toujours y = x+a.
Pour aller du premier nombre a au second nombre a, vous avancez de a pas.

On démontre qu'il ne peut exister de suite de Skolem que si n ou n-1 sont multiples de 4.
Demo 1 (afficher/cacher)
Demo 1b (afficher/cacher)

On démontre, en en construisant, qu'il existe des suites de Skolem pour tout entier naturel n congru à 0 ou 1 (mod. 4).
Demo 2 (afficher/cacher)

Pour n nul la suite est vide, pour n non nul, vous pouvez construire des suites de Skolem pour les valeurs suivantes n=1, n=4, n=5, n=8, n=9, n=12, n=13, n=16, n=17, n=20, n=21, n=24, n=25, n=28, n=29, etc.

Le nombre de solutions calculées est volontairement limité. Cliquez sur [Cherche] pour en obtenir d'autres, éventuellement. Utilisez les boutons [ |<< ]  [ <-- ]  [ --> ]  [ >>| ]  pour naviguer d'une solution à l'autre.

ordre n =

Si l'applet ne démarre pas, rechargez la page dans le navigateur. Pour arrêter le calcul en cours, appuyez d'abord sur Stop. Aucun calcul ne débute lorsque le précédent n'est pas terminé..

Les paires sont représentées par des segments. En observant ces schémas, il devrait être possible de retrouver d'autres formules semblables à celles de la Demo 2 (il en existe).

Introduits pour la première fois en 1847 par Kirkman (La promenade des demoiselles), ces systèmes furent redécouverts et publiés en 1853 par Steiner dans un contexte géométrique. Une preuve d'existence fut donnée par Kirkman (pour des ensembles de v=6p+1 et v=6p+3 éléments) mais pas par Steiner. Depuis un grand nombre de mathématiciens ont donné des démonstrations très variées.
Le problème posé par Kirkman était le suivant : Les 15 demoiselles d'un collège sortent en promenade, en rang par trois, pendant 7 jours d'affilée : comment arranger journellement ces sorties pour que deux quelconques d'entre elles ne se retrouvent jamais de toute la semaine, ensemble plus d'une fois dans une même rangée.
Un bloc design est une collection de sous-ensembles de k éléments d'un ensemble S de v éléments tels que chaque paire d'éléments de S apparaisse dans exactement lambda blocs. Un système de triplets de Steiner est un design, un ou encore un Steiner 2-design.
Kirkman demande de trouver un système résolvable de triplets : la répartition sur plusieurs journées est une contrainte supplémentaire qui ne figure pas dans la définition d'un système de triples de Steiner, cette contrainte ne peut être satisfaite que lorsque v est multiple de 3 (c.-à-d. v=6p+3), et donc pas par les systèmes obtenus ici, sur cette page pour lesquels v=6p+1).

Les systèmes de triplets sont des objets combinatoires assez simples, ils ont des liens profonds avec la géométrie, l'algèbre, la théorie des groupes, les espaces vectoriels. Ils ont de nombreuses applications en cryptographie, en théorie du codage, en statistique et en informatique. Les problèmes étudiés et résolus dans le contexte des systèmes de triplets ont souvent pu être généralisés et étendus à des d'autres domaines de la combinatoire.

En débutant à l'ordre n=1, les nombres de suites de Skolem sont 1,0,0,6,10,0,0,504,2636,0,0,455936,3040560 ...
Généralement, on ne distingue pas une suite de Skolem de sa symétrique, obtenue en la retournant et en échangeant la droite et la gauche. Dans ce cas, les nombres de suites de Skolem sont 1, 0, 0, 3, 5, 0, 0, 252, 1318, 0, 0, 227968, 1520280 ...
(Recherche exhaustive sur ordinateur, mai-juin 2007)

Les méthodes permettant de construire ou seulement de dénombrer les suites de Skolem ou de Langford seront présentés ultérieurement sur une page séparée.