Comptes Rendus MATh.en.JEANS 94-01 

Atelier MATh.en.JEANS année scolaire 1993-1994.
Enseignants : Christophe FILLEY
Chercheur : Pierre DUCHET (CNRS, Laboratoire LSD2, 38-Grenoble)

 

---

Article en cours d'analyse et de vérification, recu le 18/12/94
[les passages entre crochets sont des éditeurs]

Définition [modélisation] du problème

n billes sont réparties dans t tas (d'où tn). Dans chacun des tas, on prélève une bille. Un nouveau tas est formé à partir des billes récoltées. Le problème consiste à comprendre l'évolution du système lorsque l'action de prélèvement est répétée.

On appelle configuration (ou état), une répartition de ces n billes. Un successeur de cette configuration est obtenu par l'action d'enlèvement, appelée aussi transition.                                                      De même un prédécesseur est une configuration qui va permettre d'atteindre la configuration donnée Figure 1

Un cycle est un ensemble fini de configurations tel que chaque état du cycle va évoluer vers lui après un certain nombre de transitions. [par exemple, les 3 configurations de la figure 1 forment un cycle : en effet, l'action de prélèvement effectuée sur la troisième configuration redonne la première configuration.]

Par convention l'ordre des tas est indifférent et les tas contenant 0 billes ne sont pas considérés. Sous ces hypothèses, une configuration est caractérisée par un nombre de tas et un nombre de billes par tas. pour simplifier la lecture, nous avons choisi de classer les tas par ordre croissant du nombre de billes qu'ils contiennent.

Premiers résultats

Rapidement différents résultats de base ont été démontrés :

Théorème 1. Une configuration présente exactement un succeseur

Théorème 2. Une configuration peut avoir 0, 1 ou plusieurs prédéceseurs.

Théorème 3. Toute configuration évolue vers un cycle.

Preuve : Le nombre d'états étant fini, et chaque état ayant un succeseur, en répétant la transformation à l'infini, on revient inéluctablement sur un état déjà visité.

Théorème 4. Le nombre de configurations à n billes vaut f(1,n) où f est la fonction définie par :
f: x

(n,p) -> f(n,p) avec :

f(n,p) = f(n-p,p)+f(n,p+1) si p<n.
        = 1 si p=n
        = 0 si p>n

Preuve : voir en annexe 1

Du théorème 3, nous avons déduit que le cycle représentait en quelque sorte, la convergence du système. La suite de l'étude va donc essentiellement porter sur la caractérisation et la détermination des cycles (leur nombre, leur longueurs, ...)

Caractérisation d'une configuration appartenant à un cycle

Par définition, on appelle cycle à p un cycle comportant p états différents.

Les cycles à 1, ou états invariants

Un état appartenant à un cycle à 1 doit être son propre successeur. C'est donc un état invariant. Appliquer l'action de prélèvement sur cet état ne modifie rien. [Théorème 5] Ils sont de la forme suivante (voir le preuve en annexe 2)

1 2 3 4 5 ...

Les cycles à 2

Il devient plus difficile de les caractériser car dans chaque configuration, un des tas représente le nombre de tas de son prédecesseur. Or il est difficile de savoir quel est ce tas.

[Théorème 6] Une condition nécessaire d'appartenance à un cycle de 2 est (voir la preuve en annexe 3) :

Condition nécessaire

Si un état appartient à un cycle à 2, alors il a la forme suivante :

(a) 1 1 3 3 5 5 ...

ou

(b) 2 2 4 4 6 ...

Une conjecture sur une condition nécesaire et suffisante est :

Un état appartient à un cycle 2 si et seulement si il est :
soit de a forme (a) et a un nombre pair de tas
soit de la forme (b) et a un nombre impair de tas.

On déduit de cette conjecture que les nombres admettant des cycles à 2 sont de la forme :

Les cycles à p

Seule une condition nécessaire a été trouvée pour caractériser un état appartenant à un cycle à  : cette condition est déduite de l'étude des cycles à p sous le même principe que l'étude des cycles à 2.

Condition nécessaire

Si un état appartient à un cycle à p, alors ses n plus petits tas doivent être de cardinalités inférieure ou égale à n.

De l'étude des cycles à partir d'exemples et de la caractérisation des états appartenant à un cycle, nous en avons déduit une conjecture générale permettant de trouver pour un nombre donné de billes, le nombre de cycles qu'il est possible d'avoir et leur longueur. Cette cconjecture est énoncée ci-dessous.

Conjecture sur le nombre de cycles et leur longueur pour un nombre n de billes

Définition

soit : la somme des j premiers entiers est la plus petite somme d'entiers supérieure à n.

Cas particulier : à partir d'un tas de n billes

a) le cycle obtenu est de longueur j.

b) on entre dans le cycle au bour de n-j itérations (le premier état du cycle contient pour la première fois un tas de j billes).

Cas général : à partir d'un tas de n billes

c) la longueur d'un cycle ne peut pas dépasser j.

d) Un état appartenant à un cycle a j ou j-1 billes.

e) Un tas d'un état appartenant à un cycle ne peut avoir plus de j billes.

f) Un état appartenant à un cycle a au plus 2 tas qui ont le même nombre de billes.

g) Soitle nombre d'états qui appartient à un cycle pour un nombre de bille donné (s'il y a plusieurs cycles, vaut la somme des nombres d'états de chaque cycle).

Pour n1, les correspondant suivent le triangle de Pascal.

Si on note le nombre de billes rajoutées par rapport au plus grand invariant <n, [on a] :

=

Remarques

i) Quand on ajoute des billes à un invariant, le nombre d'tétats qui cyclent augmentent. Quand n s'approche du prochain invariant, le nombre d'état qui cycle diminue. Ceci introduit l'idée de symétrie entre 2 invariants.

ii) La distance entre 2 invariants croît avec n. Cela implique que la valeur maximale atteinte par entre deux invariants croît avec n.

iii) Pour un nombre n de billes donné, on obtient le nombre de cycles et leur longueur à partir de , écrit comme un entier et une somme de fractions à numérateur égal à 1.

Exemple. pour n= 32, j=8, =70 on a = = 8+1/4+1/2 [Donc il y a ] 8 cycles à 8, 1 cycle à 4, 1 cycle de 2.

Vérifications de la validité de la conjecture

Il ne nous a pas été possible, vu la difficulté du problème de montrer cette conjecture. Pourtant nous avons vérifié sa compatibilité avec les théorèmes trouvés.

Cas des invariants

Par exemple nous retrouvons bien avec la conjecture que dans le cas d'un nombre de bille pouvant s'écrire sous la forme i, le cycle ne contient qu'un état qui est en fait un état invariant.

Cas des cycles à 2

De même la cojecture nous indique qu'il y a un cycle à 2 pour un nombre de bille s'écrivant sous la forme

Les résultats donnés par la conjecture ont été vérifié jusqu'à n=45. [voir annexe 4]

Conclusion

Cette théorie de caractérisation des cycles à partir du nombre de billes, n'est qu'à l'état de conjecture car il nous manque des éléments de démonstration. Certaines conjectures se déduisent d'autres. Par exemple, une fois d) et f) démontrés, la démonstration de g) (triangle de Pascal) devient immédite (cela revient à ajouter k fois une bille sur j tas de la configuration invariante).

Il reste donc à démontrer les conjectures a) à g) pour valider la théorie.

A partir d'une configuration donnée, le nombre total de billes nous permettrai alors de dire combien de cycles nous pouvons avoir, leur longueur, mais nous ne pouvons toujours pas savoir vers quel cycle cette configuration va converger. Ceci pourrait être la suite de l'étude déjà réalisée.

[Preuve du théorème 4]

Pour déterminer le nombre de configurations différentes pour un nombre de billes donné, définissons la fonction f: x
(n,p) -> f(n,p)

f(n,p) représente le nombre de configurations composées de n biles répartyies en tas d'au moins p billes chacun.

• Il n'existe pas de configuration composée de n billes réparties en tas ayant plus de n billes. Formellement cela donne :
  (1) f(n,p) = 0 = 0 si p>n.
• Il existe une seule confuguration composée de n billes réparties en tas ayant au moins n billes. Cette configuration est celle où il y a un unique tas de n billes. Donc,
  (1) f(n,p) = 1 si p=n.
• Pour une configuration composée de n billes réparties en tas d'au moins p billes, 2 cas peuvent se produire :
  - soit il n'existe pas de tas d'exactement p billes,
  - soit il existe au moins un tas de p billes [et, si n>p], les autres tas regroupent les (n-p) billes restantes réparties en tas d'au moins p billes.

[D'où, pour n>p, la formule f(n,p) = f(n,p+1) + f(n-p,p) , qui permet de calculer f(n,p) de proche en proche à partir des valeurs données par (1) et (2) ]

[Table des premières valeurs (n de 1 à 10 : 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, ... et documents :

Actesw 95 pp. 141-144 Les parttions d'entiers, Module lycée Louise Michel : table et autre calcul.

99-10 (à paraître) Partitions d'entier, Lycées Camille Sée et Charles Poncet Fonction génératrice et formule de Mac Mahon]

retour au texte

[Preuve du théorème 5]

Les états invariant sont ceux qui sont leur propre successeur. Donnons la forme générale d'un état. Il eut s'écrire avec a, b, c, d, [...] le nombre de billes par tas classés par ordre croissant :

Il faut en particulier que la nombre de tas soit égal dans les deux états.

D'où a-1 = 0 , i.e. a=1

Puis
b-1 = a , i.e. b=2
c-1 = b , i.e. c=3
d-1 = c , i.e. d=4
[etc.]

La forme générale d'un état invariant est [donc] :

1    2    3    4    5    ...     

retour au texte

[Preuve du théorème 6]

Cette caractérisation est faite dans le cas général. Le raisonnement est basé sur le nombre de tas appartenant à une configuration.

Un état appartenant à un cycle à 2 s'écrit sous la forme

Son sucesseur est :

Le successeur du sucesseur est :

Le successeur suivant est :

Si l'état 1 appartient à un cycle à 2, alors il doit être égal à l'état 3. En particulier le nombre de tas est égal. [Les nombres] a, b, c, d [...] étant rangé par ordre croissant, nous obtenons (car e et f sont2) :

a-2 0 , i.e. a2
b-2 0 , i.e. b2
c-2  >  0 , i.e. c > 2
d-2  >  0 , i.e. d > 2

Plusieurs cas peuvent se produire en fonction des valeurs de a et b :

• a=1, b=1

  Donc a-1=0 et b-1=0. Or il faut aussi que que l'état 2 soit égal à l'état 4. On obtient dans ce cas :
  c-3<0 [?] i.e. c3
  d-3<0 [?] i.e. d3
  D'où [...] c=3 et d=3.

  la configuration est de la forme

• a=1, b=2

  On obtient de la même façon c=3,b=4, c'est à dire une configuration de la forme :

Or c'est le cas invariant. Cette configuration est donc déjà comptée dans les cycles à 1.

• a=2, b=2

  L'état 2 possède donc 5 tas. Il doit en être de même pour l'état 4. On obtient alors
  c-3>0     i.e.   c > 3
  d-3>0 [?] i.e. d > 3
  En appliquant le raisonnement fait sur l'état 1 à l'état 3, on obtient :
  c-22 [?] i.e. c4
  d-22 [?] i.e. d4
  D'où [...] c=4 et d=4. La configuration est de la forme :

Ces deux formes de configurations suffisent-elles à caractériser un état appartenant à un cycle à 2 ?

Exemple :            1 1 3 3 5 5 2 2 4 4 61 1 3 3 5 5. Le cycle à deux est vérifié.
Contre-exemple :  1 1 3 3 5 2 2 4 51 1 3 4 4. Le cycle à 2 n'est pas vérifié.

Cette condition sur la forme des états n'est donc que condition nécessaire. Il faut en plus une condition sur le nombre de tas de la configuration.

Si a=b=1 alors le nombre de tas doit être pair,
Si a=b=2 alors le nombre de tas doit être impair.

retour au texte

n    nb de billes

nombre total de configurations [...] cycliques

j   (1+2+3+...+j > n)

nombre et longueur des cycles

retour au texte

1.

retour au texte

2.

retour au texte

3.

retour au texte

4.

retour au texte

5.

retour au texte

Quelques références.

Mots clefs

roulette hollandaise

Comptes Rendus MATh.en.JEANS 94-01

© MATh.en.JEANS 2002. Tous droits réservés.