|Définitions, exemples| |Construction, programmes| |Graphes et hypergraphes| |Pavages infinis ou mixtes ou circulaires|

Page précédentePage suivante

Pavages rythmiques parfaits II



Recherche des pavages

Applet java

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 de Skolem et de Langford

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

cubes de couleur


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 9m=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.

Nombres de pavages

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.



Liens

Clique - Implementations   The Stony Brook Algorithm Repository Steven S. Skiena
Stas Busygin's NP-Completeness Page
InterTools -- Max Clique   R. Battiti and M. Protasi.
Sculpture à l'IHÉS l'Institut possède une représentation d'une des suites de Skolem sous forme de sculpture, réalisée par l'artiste américaine Jessica Stockholder, suivant un cahier des charges établi par des classes de primaire qui ont travaillé sur le jeu des cavaliers.
A Journey through Intersection Graph County   Erich Prisner

Page précédentePage suivante

|Définitions, exemples| |Construction, programmes| |Graphes et hypergraphes| |Pavages infinis ou mixtes ou circulaires|
















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