RÈGLES PARFAITES ET OPTIMALES
Introduction. 

Les règles, que nous pouvons acheter en papeterie, sont graduées avec un ordre régulier de graduations qui ressemblent à :

'-'-'-'-'-'-'

Plutôt ennuyeux, n'est-ce pas? Récemment, les fabricants de règles ont découvert qu'ils pouvaient réduire les coûts de production en supprimant certaines des graduations, mais tout en gardant leur fonctionnalité. Par exemple, avec la règle

'-'---'--'

nous pouvons mesurer toutes les distances qui peuvent être mesurées avec la règle standard de même longueur.

Combien de graduations pouvons-nous supprimer, si nous voulons pouvoir mesurer toutes les distances jusqu'à une certaine longueur ? C'est cette question que nous allons principalement étudier ici et qui transforme une règle monotone en un objet d'analyse combinatoire intéressant.

Tout d'abord, nous voulons nous assurer que nous pouvons mesurer toutes les longueurs qui sont plus courtes ou égales à celles de la règle. Ceci est une condition sine qua non pour une règle raisonnable.

Nous appellerons une règle qui a cette qualité règle complète, car elle a assez de graduations pour remplir sa fonction principale. Les règles qui ne remplissent pas cette fonction (les règles incomplètes) ne seront pas prises en considération ici. 

En 2ème lieu nous allons nous concentrer sur les règles complètes qui ont le minimum possible de graduations. Nous les appellerons les règles parfaites. Ce sont donc des règles complètes; la suppression d'une seule graduation les rendrait incomplètes. Nous pouvons donc considérer que de telles règles parfaites présentent une qualité esthétique non contestable : et qu'elles remplissent leur fonction avec un minimum de complexité.

Curieusement, les règles parfaites avec le même nombre de graduations se différencient cependant dans leur utilité. Considérons les trois règles parfaites suivantes. Elles ont toutes 4 graduations. (Les nombres correspondent aux positions des graduations sur la règle.)

[0, 1, 3, 4], [0, 1, 3, 5], [0, 1, 4, 6]

Nous constatons que, avec la 3ème règle, nous pouvons mesurer 33% de longueurs en plus qu'avec la première règle. Parions que, si vous deviez choisir une ces règles vous choisiriez certainement la troisième règle.

Cependant pour ce qui est de la troisième règle, le point décisif est qu'il n'existe aucune autre règle qui ait 4 graduations, qui soit complète et qui puisse mesurer plus de longueurs.

Ce qui veut dire que les graduations couvrent une étendue de mesurage maximale. Nous nommerons les règles avec cette caractéristique les règles optimales. Les règles optimales combinent ainsi l'esthétique d'un minimum de complexité avec un maximum d'efficacité.

Les règles ayant cette qualité sont des exemplaires plutôt rares. Par exemple, il y a 52012 règles parfaites avec 14 graduations, mais seulement 4 d'entre elles sont des règles optimales. L'énumération des règles parfaites et optimales seront un de nos objectifs.

Les règles optimales, qui existent pour chaque nombre de graduations, ont une longueur très particulière. En fait leurs longueurs dépendent du nombre de graduations :

0, 1, 3, 6, 9, 13, 17, 23, ...

Mais ces nombres comptent également le nombre maximal de bords dans un graphe gracieux sur n nœuds, encadrant l'étude des règles parfaites à la théorie des graphes, l'analyse combinatoire et la théorie additive des nombres.

Bien sûr, vous voudriez bien savoir comment on construit de telles règles optimales. À première vue ceci a l'air difficile, mais il y a une conjecture (une hypothèse encore non-prouvée), qui dit qu'il existe un plan de construction très simple pour ces règles optimales.

La conjecture indique qu'une règle avec plus de 14 graduations n'est optimale que si c'est une règle Wichmann, qui tient son nom de B. Wichmann, qui a présenté le plan de construction en 1962 dans l'article A note on restricted difference bases.

Les règles en un mot

Une règle est un ordre croissant strict et fini de graduations, que nous comprenons comme nombres entiers non négatifs. Par convention la première graduation est le 0.

Les règles sont comptées d'après leur longueur L et le nombre de segments S (un segment est l'espace entre deux graduations adjacentes). Une règle avec des graduations de M à S=M-1 segments.

Une règle est donc :

  • COMPLÈTE, si toutes les distances d avec 1 <= d <= L peuvent être mesurées avec la règle.
     
  • PARFAITE, s'il n'y a aucune règle complète avec la même longueur qui possède moins de graduations.
     
  • OPTIMALE, s'il n'y a aucune règle parfaite avec le même nombre de graduations qui a une plus grande longueur.
home