Graphe des représentations

Afin de visualiser certaines situations, il est commode de représenter les différentes représentations au sommet d'un graphe, de les relier par une arête si on obtient l'une de l'autre par une transformation élémentaire \(F_i = F_{i-1} - F_{i-2}\) lorsque c'est possible.

Rappel: On a construit un algorithme pour rejoindre la représentation maximale depuis tout sommet, donc ce graphe est connexe.

Exercice 1

Pour construire le graphe de toutes les représentations de Zeckendorf de \(n=9\), on peut commencer à l'écrire \(n=8+1\) sa représentation minimale. Ensuite on voit qu'on peut remplacer \(8\) par \(5+3\), ce qui conduit à \(n=5+3+1\), où la seule transition possible est pour revenir à \(n=8+1\). On a ici un graphe à deux sommets reliés par une arête.

Construire à la main les graphes pour \(n=15\), \(n=16\) et \(n=17\).

Réponse

\(n=15\)\(n=16\)\(n=17\)

graph TB
    N34["2 + 13"]
    N26["2 + 5 + 8"]
    N26 <--> N34

graph TB
    N36["3 + 13"]
    N35["1 + 2 + 13"]
    N28["3 + 5 + 8"]
    N27["1 + 2 + 5 + 8"]
    N35 <--> N36
    N28 <--> N36
    N27 <--> N35
    N27 <--> N28

graph TB
    N37["1 + 3 + 13"]
    N29["1 + 3 + 5 + 8"]
    N29 <--> N37

Exercice 2

On pourra constater que pour \(n=4\), le graphe n'a qu'un seul sommet. Trouver toutes les valeurs de \(n\) pour lesquelles le graphe n'a qu'un seul sommet. Exprimer ces nombres sous une forme simple.

Vous pourrez vérifier votre résultat avec le générateur de graphe ci-dessous.

Réponse

D'abord, on peut confirmer que pour tout \(n\) il existe au moins un sommet, car la représentation minimale existe. (Le cas \(n=0\) est un peu particulier ; il y a un sommet, composé de la somme vide, mais c'est un sommet !)

Soit \(n\in \mathbb N\) qui possède un unique sommet, alors sa représentation en tableau de bits ne peut pas comporter deux 0, ni deux 1, d'affilés. Donc son tableau de bits est d'une des formes :

Forme 0 : [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ..., 0, 1] (longueur \(2k\))
Forme 1 : [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ..., 0, 1] (longueur \(2k+1\))

Réciproquement, tout tableau de bits sous une des deux formes correspond à un entier qui n'a qu'un seul sommet à son graphe des représentations de Zeckendorf. Reste à trouver une formule simple !

Ajoutons 1 au nombre \(n\).

Si \(n\) est de la forme 0, alors une représentation de \(n+1\) est [1, 1] puis une succession finie de 0, 1. On montre sans mal qu'on peut remplacer [1, 1, 0, 1, 0, 1..., 0, 1] par [0, 0, 1, 1, 0, 1...0, 1] puis par [0, 0, 0, 0, 1, 1, ...0, 1], jusqu'à [0, 0, 0, 0, 0, 0, ..., 1, 1] qui est de longueur \(2k\). Maison peut aussi l'écrire avec \(2k\) zéros, puis un un. Dans ce cas, \(n+1\) est un nombre parmi \(F_0\), \(F_2\), \(F_4\), \(F_6\), ... en effet, on \(n+1 = F_{2k}\).
Si \(n\) est de la forme 1, alors il y a déjà un un, si on ajoute \(1\) à \(n\), on remplace \(1\) par \(2\) dans la somme de Zeckendorf, ainsi on a un tableau de bits pour \(n+1\) de la forme [0, 1, 1, 0, 1, ..., 0, 1], et comme précédemment, on arrive à \(n+1 = F_{2k+1}\).

Conclusion, \(n+1\) est un nombre de Fibonacci.

Exemple de graphe avec \(n = 100\)

graph TB
    N532["3 + 8 + 89"]
    N531["1 + 2 + 8 + 89"]
    N404["3 + 8 + 34 + 55"]
    N527["1 + 2 + 3 + 5 + 89"]
    N403["1 + 2 + 8 + 34 + 55"]
    N372["3 + 8 + 13 + 21 + 55"]
    N399["1 + 2 + 3 + 5 + 34 + 55"]
    N371["1 + 2 + 8 + 13 + 21 + 55"]
    N367["1 + 2 + 3 + 5 + 13 + 21 + 55"]
    N531 <--> N532
    N404 <--> N532
    N527 <--> N531
    N403 <--> N531
    N403 <--> N404
    N372 <--> N404
    N399 <--> N527
    N399 <--> N403
    N371 <--> N403
    N371 <--> N372
    N367 <--> N399
    N367 <--> N371

Un IDE pour expérimenter

Voici un IDE avec de nombreuses fonctions disponibles, celles déjà rencontrées, mais deux nouveautés :

zeckendorf_mermaid : prend un entier positif en paramètre et renvoie le code Mermaid permettant le dessin du graphe.
dessine_graphe : prend un entier positif en paramètre et effectue le dessin ci-dessous.

Le graphe sera dessiné ici

Exercice 3 🌋

On dira que le graphe est filiforme lorsqu'il n'y a qu'un seul chemin pour relier deux sommets distincts.

On pourra constater que pour \(n=14\), le graphe est filiforme. Trouver toutes les valeurs de \(n\) pour lesquelles le graphe est filiforme. Exprimer ces nombres sous une forme simple.

Vous pourrez vérifier votre résultat avec le générateur de graphe ci-dessus.

Indice

Il sera malin de réfléchir :

à la forme de la représentation minimale. Rappelons qu'il n'y a pas deux 1 consécutifs dans le tableau associé.
à la forme de la représentation maximale. Rappelons qu'il n'y a pas deux 0 consécutifs dans le tableau associé.
aux possibilités de la partie commune à ces deux représentations.

Réponse

C'est assez délicat, mais il y a un rapport entre \(n+1\) et deux nombres de Fibonacci.

On montre que le tableau de bit de la représentation minimale a l'une des formes :

0, 1 répété, suivi de zéros, suivi de 1 et une répétition de 0, 1
1 suivi de la forme précédente.

De manière condensée, on note ce motif : \(1?(01)^*0^*(01)^*\) qui se traduit par :

Présence éventuelle d'un 1
Répétition (éventuellement vide) de 01
Présence (éventuellement vide) de 0
Répétition (éventuellement vide) de 01

Le graphe est filiforme, donc les transitions n'opèrent que dans l'unique bande de zéros (au moins 2).

Si on ajoute 1 à ce nombre, on obtient un nouveau motif plus simple, au choix :

\(0^*1(0)^*1\) ; dans ce cas \(n+1\) est la somme de deux nombres de Fibonacci
\(0^*1(01)^*\) ; dans ce cas, si on ajoute \(F_{k}\) avec le bon indice, on obtient un nouveau motif encore plus simple \(0^*1\) ; on a obtenu un nombre de Fibonacci. Ce qui veut dire \(n+1\) est la différence entre deux nombres de Fibonacci.

Conclusion: Le graphe de \(n\) est filiforme, si et seulement si, \(n+1\) est la somme ou la différence de nombres de Fibonacci.

Exercice 4

Démontrer qu'un graphe de la forme suivante ne peut pas exister (ni son symétrique).

Schéma de graphe

    .
   / \
  .   .
 / \ / \
.   .   .
 \     /
  \   /
   \ /
    .

Concrètement, cela signifie qu'on peut rejoindre tout sommet à une extrémité avec un seul type de transition (soit des fusions, soit des fissions) \(F_{n} = F{n-1} + F_{n-2}\), et réciproquement.

Réponse

Le sommet central ne possède aucune transition vers le bas (res. le haut), donc d'après le théorème de Zeckendorf, c'est l'unique représentation minimale (resp. maximale).

Un tel sommet se doit d'être à une extrémité du graphe, et non au cœur.