Les règles de Golomb

Sujet proposé par Philippe Baptiste

Philippe.Baptiste@polytechnique.fr

1  Définition des règles de Golomb

Une règle de Golomb est définie par n taquets positionnés à des valeurs entières de la règle m1 < m2 ⋯ < mn telles que ∀ i,j,k,l ∈ {1, ..., n} avec i < k,
|mj - mi| ≠ |ml - mk|.
Une règle de Golomb est donc un ensemble d'entiers naturels dans lequel les distances entre les éléments sont deux à deux distinctes.

Pour un entier n donné, une règle de Golomb est ``optimale'' si sa longueur (mn - m1) est minimum parmi toutes les règles de Golomb possibles. Dans la suite on supposera toujours que m1 = 0. Les règles de Golomb sont utiles pour les radaristes, les astronomes, les cristallographes, etc.

Voici quelques règles de Golomb optimales.
Règle      0    1    2    3    4    5    6    7    8    9    10   11 
___________|____|____|____|____|____|____|____|____|____|____|____|__ 
n = 2      ^    ^                                                    
n = 3      ^    ^         ^                                          
n = 4      ^    ^              ^         ^                           
n = 5      ^         ^                        ^    ^              ^  
Le but de ce projet est de construire des règles de Golomb optimales pour n ≤ 10. Nous nous intéresserons aussi à quelques variantes des règles de Golomb.

Notons que les règles de Golomb optimales sont connues jusqu'à n = 24. Il a fallu des dizaines d'années de CPU pour résoudre ce dernier problème.

2  Une recherche arborescente

Construire une procédure récursive qui, pour un entier n donné, énumère toutes les règles possibles et renvoie la règle optimale. Les règles seront construites en plaçant les taquets de gauche à droite. On notera qu'une telle procédure correspond à un arbre de recherche dont les noeuds sont exactement les appels récursifs.

En supposant que la recherche est limitée à 10 mn de CPU par règle, donner, pour chaque règle optimale qu'il a été possible de calculer, sa longueur, le temps CPU utilisé et le nombre de backtracks dans la procédure arborescente. Ces résultats seront présentés dans un tableau de synthèse.

3  Borne inférieure

Remarquons que la longueur de la règle optimale est au moins
LB0(n) =
n(n-1)
2
.


Supposons maintenant que les positions m1, ..., mq des q premiers taquets sont connues et qu'il reste donc à placer les n - q derniers taquets. Proposer un algorithme qui permet de calculer une borne inférieur plus efficace que mq + LB(n-q). On pourra utiliser le fait que les distances mj - mi pour ijq sont interdites pour les taquets à positionner aprés mq. On notera LB1 cette borne inférieure.

Si au cours de la recherche arborescente, la borne inférieure (LB0 ou LB1) dépasse la longueur de la meilleure règle connue, il est alors possible de bactracker immédiatement. Tester l'efficacité de ces deux bornes (on donnera à chaque fois des tableaux complets de résultats).

4  Propriété de dominance

Pour n ≥ 3, il existe une règle optimale dans laquelle m2 - m1 ≥ 2. Pourquoi ? On dit alors que les règles de Golomb qui satisfont m2 - m1 ≥ 2 sont dominantes.

Comment tenir compte de cette propriété dans la recherche arborescente ? Donner un tableau complet des résultats obtenus en combinant cette dominance avec LB1.

5  Utilisation de règles précédemment calculées

Soit lu la longueur optimale d'une règle de Golomb de u taquets. Dans une une règle de Golomb de n taquets, la postion du uème taquet (un) est au moins lu. Pourquoi ? Comment exploiter cette propriété dans la recherche ?

Donner un tableau complet des résultats obtenus en combinant cette règle avec la dominance et avec LB1.

6  Cercles de Golomb

On chercher maintenant à construire une règle de Golomb en positionnant n marques sur un cercle. Les distances entre deux marques sont définies par la longueur du plus petit arc de cercle permettant de cheminer de l'une à l'autre. Sur un cercle de Golomb, les distances entre les marques sont toutes entières et, comme pour la règle de Golomb, les distances entre les marques sont toutes distinctes.

Proposer une méthode permettant de calculer un cercle de Golomb de périmètre minimal.

En supposant que la recherche est limitée à 10 mn de CPU par cercle, donner, pour chaque cercle optimal qu'il a été possible de calculer, son périmètre, le temps CPU utilisé et le nombre de backtracks de la procédure arborescente. Ces résultats seront synthétisés dans un tableau. Les cercles optimaux seront inclus dans le rapport (de préférence sous forme graphique).


Ce document a été traduit de LATEX par HEVEA.