Accueil / Combinatoire / Combinatoire et permutations / Suites de Skolem, de Langford. Designs / Suites de Skolem

Suites de Skolem

Introduction

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).

Définition

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.

Existence

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)Démo
Demo 1b (afficher/cacher)Démo 1 b c

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)Démo 2

Constructions

Application

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é..

Schémas

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).
Cliquez pour afficher ou pour cacher le schéma

Systèmes de triplets de Skolem

Cliquez pour afficher ou pour cacher le système de Skolem

Système de différences

Cliquez pour afficher ou pour cacher le système de différences

Système de Steiner

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 (v, k, lambda) design, un (v, k, lambda)BIBD 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.

Cliquez pour afficher ou pour cacher le système de Steiner

Nombre de suites de Skolem

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)

Algorithmes

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.
En attendant, et c'est bien mieux, entraînez-vous à construire des algorithmes, en particulier sur la recherche des suites de Skolem ou de Langford, et construisez un programme pour une valeur particulière de n ou pour n'importe quel n demandé par l'utilisateur.

Janvier 2012 : Benjamin Coulonval, élève de TS a écrit un programme qui calcule les suites pour la valeur n=8 et a expliqué très en détail sa méthode, vous pouvez télécharger l'archive Skolem_By_Coulonval.rar qui contient le programme, l'exécutable windows, le document et son pdf. (Pour compiler le programme sous linux, il peut être nécessaire de mettre en commentaire // la ligne qui contient le mot 'system').

Documents - livres - références - compléments - liens utiles


Accueil / Combinatoire / Combinatoire et permutations / Suites de Skolem, de Langford. Designs / Suites de Skolem

















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014