Olympiades · 18 mars 2015 · Tous candidats
« Transformation du boulanger » : \(f\) définie sur \([0,1]\) par \(f(x)=2x\) si \(x\le\frac12\), \(f(x)=2(1-x)\) sinon.
Partie A. 1. Montrer que \(f(x)\in[0,1]\). 2. Justifier que \(f\) modélise le déplacement d'une fève dans une pâte repliée.
Partie B. On note \(x_1=f(x)\), \(x_2=f(x_1)\), etc. 1. Calculer les 9 images de \(\frac13\) et de \(0{,}33\), commenter. 2. Une fève peut-elle revenir à sa position initiale en 1, 2, ou 3 coups (mais pas avant) ? Donner tous les \(x\) correspondants. 3. On dit que \(x\) « atteint sa cible » s'il finit par atteindre 0. Donner un exemple qui atteint sa cible, un autre qui ne l'atteint pas. 4. Le nombre \(2015/2^{2015}\) atteint-il sa cible ? 5. Déterminer tous les nombres de \([0,1]\) atteignant leur cible.
Partie C. 1. Modifier l'algorithme fourni pour qu'il affiche le nombre d'étapes vers 0. 2. Le nombre \(\frac19\) n'atteint pas sa cible (question B5) : que devrait faire l'algorithme ? Que se passe-t-il en pratique sur machine, et pourquoi ?
B2. Résoudre successivement \(f(x)=x\), \(f(f(x))=x\), \(f(f(f(x)))=x\) en découpant \([0,1]\) selon les morceaux affines de \(f\), \(f\circ f\), \(f\circ f\circ f\).
B4-5. Un nombre atteint sa cible si et seulement s'il finit par atteindre 1 (l'autre antécédent de 0), c'est-à-dire si ses doublements successifs (avant de dépasser \(\frac12\)) finissent par tomber exactement sur une puissance de 2 au dénominateur.
C2. Penser aux erreurs d'arrondi inhérentes au calcul en virgule flottante sur une machine.
A1. Si \(x\le\frac12\), \(2x\in[0,1]\). Si \(x>\frac12\), \(1-x\in[0,\frac12[\), donc \(2(1-x)\in[0,1[\).
A2. \([0,\frac12]\) est « étiré » sur \([0,1]\), \([\frac12,1]\) est « replié » puis étiré : cela modélise l'étirement de la pâte après repliement.
B1. Les images de \(\frac13\) restent constamment \(\frac23\) (point fixe de \(f\circ f\)) : elles se stabilisent immédiatement. Celles de \(0{,}33\) s'en écartent puis oscillent sans se stabiliser (chaos sensible aux conditions initiales).
B2. 1 coup : \(x=0\) ou \(x=\frac23\). 2 coups (nouveaux) : \(x=\frac25\) ou \(x=\frac34\). 3 coups (nouveaux) : les six solutions se répartissent en deux cycles \(\left\{\frac29,\frac49,\frac89\right\}\) et \(\left\{\frac27,\frac47,\frac67\right\}\).
B3. Exemple qui atteint sa cible : \(x=\frac14\) (car \(f(\frac14)=\frac12\), \(f(\frac12)=1\), \(f(1)=0\)). Exemple qui ne l'atteint pas : \(x=\frac23\) (point fixe, n'atteint jamais 0).
B4. Les images successives de \(\dfrac{2015}{2^{2015}}\) restent inférieures à \(\frac12\) (doublements successifs) jusqu'à devenir \(\dfrac{2015}{2048}>\frac12\), puis \(\dfrac{33}{1024}\), \(\dfrac{33}{512}\), ..., jusqu'à \(\frac12\) puis \(1\) puis \(0\) : oui, il atteint sa cible.
B5. En raisonnant sur les antécédents : les nombres qui atteignent leur cible sont exactement les rationnels de la forme \(\dfrac k{2^n}\) (\(n\in\mathbb N\), \(k\) entier avec \(0\le k\le2^n\)), c'est-à-dire les nombres dyadiques de \([0,1]\).
C1. Ajouter une variable \(N\) initialisée à 0, incrémentée à chaque tour de boucle « Tant que », puis afficher \(N\) après la boucle.
C2. L'algorithme devrait tourner indéfiniment (le cycle \(\frac29,\frac49,\frac89\) ne contient jamais 0). En pratique, les erreurs d'arrondi en virgule flottante font dériver les valeurs successives de \(\frac19\) vers des rationnels dont le dénominateur est une puissance de 2 (ensemble dense dans \([0,1]\)), jusqu'à atteindre accidentellement 0 après une cinquantaine d'itérations.