0%

Problème 220

Énoncé:

Soit $D_0$ la chaîne de caractères de deux lettres "Fa". Pour $n \ge 1$, dériver $D_n$ de $D_{n-1}$ par les règles de réécriture de chaînes de caractères :

  • "a" → "aRbFR"
  • "b" → "LFaLb"

Ainsi, $D_0 = $"Fa", $D_1 = $"FaRbFR", $D_2 = $"FaRbFRRLFaLbFR", et ainsi de suite.

Ces chaînes peuvent être interprétées comme des instructions à un programme d'infographie, "F" signifiant "avancer d'une unité", "L" signifiant "tourner à gauche de $90$ degrés", "R" signifiant "tourner à droite de $90$ degrés", et "a" et "b" étant ignorés. La position initiale du curseur de l'ordinateur est $(0,0)$, pointant vers le haut en direction de $(0,1)$.

Ensuite, $D_n$ est un dessin exotique connu sous le nom de dragon de Heighway d'ordre $n$. Par exemple, $D_10$ est représenté ci-dessous; en comptant chaque "F" comme un pas, le point en surbrillance à $(18,16)$ est la position atteinte après $500$ pas.

Quelle est la position du curseur après $10^{12}$ pas dans $D_{50}$ ?
Donnez votre réponse sous la forme $x$,$y$ sans espace.

Lien du problème originel