Exercice 1 — Tous les HUNS veulent devenir des Z'HEROS.

--- Partie A : Quelques mouvements de Spin Out à 2, 3 ou 4 boutons --

Question 1 : Dans cette question, on considère un Spin Out à 2 boutons en position initiale, codée 11.
a) Le mouvement A permet de passer de \(\mathbf{1 1}\) à \(\mathbf{1 0}\) (il agit sur le dernier bouton).
b) Le mouvement B permet de passer de 11 à 01 (il agit sur le dernier bouton avant le dernier bouton vertical).

Question 2 : Dans cette question, on considère un Spin Out à 3 boutons, en position initiale, codée 111.
a) Si on applique A, on obtient le code 110.
b) Si on applique B, on obtient le code 101.
c) Ni le mouvement A qui donnerait 110 ; ni le mouvement B qui donnerait 101 ne fournissent le code 011.
En ajoutant une étape, à partir de 110 , on peut soit revenir par A à 111 , soit obtenir 010 par B... Et à partir de 101, on peut soit revenir à111 par B, soit obtenir 100 par A ... toujours pas l'objectif ...
On constate qu'après la séquence \(\mathrm{A}, \mathrm{B}\), si on refait le mouvement A , on tombe bien sur 011. Le nombre de coup minimal est donc 3 pour passer de 111 à 011.Donner la liste des codes successifs correspondant à la résolution complète du Spin Out à 3 boutons en cinq mouvements.
d) 111-110 - 010-011-001-000 (mouvements ABABA).

Question 3 : Dans cette question, on considère un Spin Out à 4 boutons, en position initiale, codée 1111.
1111-1101 - 1100-0100-0101-0111-0110-0010-0011-0001-0000
(M ouvements : BABABABABA) Il est bon de remarquer que le premier mouvement a été A pour le spin-out à \(\mathbf{3}\) boutons, et B pour celui à \(\mathbf{4}\) boutons, la suite étant complètement déterminée (alternance de A et de B, motivée par l'inutilité d'une répétition qui renvoie systématiquement au code précédent)
--- Partie B : Code binaire et Code de Gray ---

Question 1:

a) \(5=4+1=22+20\). Donc l'entier naturel \(\mathbf{5}\) se code \(\mathbf{1 0 1}\) (ou 00101) selon le code binaire.
b) \(9=8+1=23+20\). Donc l'entier naturel 9 se code 1001 (ou 01001) selon le code binaire
c) Compléter la boucle conditionnelle de l'algorithme joint en annexe afin qu'il détermine le code binaire d'un entier naturel donné dans son écriture décimale. (page suivante)
d) Compléter la colonne « Ecriture en code binaire» du tableau en annexe. (page suivante)

Donc \(\mathbf{G = 1 0 1 1 1 0 1

\).} d) Si G ne contient que des 1 , c'est que B est constitué alternativement de 0 et de 1 , car deux coefficients successifs égaux dans B déboucheraient sur un coefficient nul dans G.
A partir d'un certain indice j , les coefficients bi sont tous nuls, alors que \(\mathrm{b}_{\mathrm{j}-1}=1\).
Donc pour l'indice \(\mathrm{j}-1\), on a \(\mathrm{g}_{\mathrm{j}-1}=1\) et les \(\mathrm{g}_{\mathrm{i}}\) suivants sont tous nuls.

B est donc de même longueur que G et alterne les 0 et les 1 .

e) \(\mathrm{G}=111\) correspond à \(\mathrm{B}=101\), soit l'entier naturel 5 .
\(\mathrm{G}=1111\) correspond à \(\mathrm{B}=1010\), soit l'entier naturel \(\mathbf{1 0}\).
\(\mathrm{G}=11111\) correspond à \(\mathrm{B}=10101\), soit l'entier naturel 21.

--- Partie C : Résolution du Spin Out à n boutons ---

Question 1:

a) Lorsque le Spin Out est en position \(100 . . .00\) (en code de Gray) correspondant à un entier naturel n , si on pousse la règle le plus possible à droite, il n'y a aucun bouton face à l'encoche, le mouvement B est alors impossible.
Si on veut appliquer le mouvement A, on place la règle pour faire pivoter le bouton le plus à droite, le Spin Out passe alors de la position codée \(100 . . .00\) à la position \(100 . . .01\) selon le code de Gray. Si on regarde les codes binaires correspondants, on passe de \(11 \ldots 11\) à \(11 \ldots 10\). Si on regarde les entiers naturels correspondants, on passe de \(2^{p}+2^{p-1}+\cdots+2^{1}+2^{0}\) (noté n) à \(2^{p}+2^{p-1}+\cdots+2^{1}\) (soit l'entier \(\mathbf{n - 1}\) ).
b) Si le Spin Out n'est pas en position \(100 \ldots .00\), ni \(00 \ldots .00\) alors le code comporte un 1 placé ailleurs qu'à la position la plus à gauche du code et donc on peut faire pivoter le bouton placé immédiatement à gauche de ce bouton codé 1 : le mouvement B est donc possible. Le mouvement A est quant à lui toujours possible.
Ces deux mouvements sont différents et ne font changer qu'un seul chiffre dans le code initial, ils permettent donc chacun de passer à un entier voisin de celui de départ.
L'un permet donc de passer au suivant, l'autre de passer au précédent ; donc de \(n\) à n-1 pour l'un et de n à \(\mathrm{n}+1\) pour l'autre.

Question 2 :

a) Le Spin Out à 4 boutons, en position initiale, 1111, correspond à l'entier 10 d'après le tableau en annexe. Comme les mouvements A et B ne permettent de passer qu'à l'entier précédent ou suivant, il faudra au minimum 10 étapes pour revenir au code 0000, codant l'entier naturel 0.
Autre version : le code de Gray 1111 correspond au code binaire 1010 qui correspond à l'entier naturel \(2^{1}+2^{3}=2+8=10\), d'où la même conclusion.
b) Le Spin Out à 7 boutons, en position initiale, 1111111, correspond au code binaire 1010101, qui correspond à l'entier naturel \(2^{0}+2^{2}+2^{4}+2^{6}=1+4+16+64=85\). Il faut donc au minimum \(\mathbf{8 5}\) mouvements pour revenir à reculons de 1 en 1 au code 0000000, soit 0 en version entier naturel.
c) Si n est impair, le code binaire correspondant au code de Gray \(11 \ldots 11\) est du type \(10 \ldots 01\) qui correspond à l'entier
\(2^{0}+2^{2}+\cdots+2^{n-1}=1+4+4^{2}+\cdots+4^{\frac{n-1}{2}}=1 \times \frac{1-4^{\frac{n-1}{2}+1}}{1-4}=\frac{1-4^{\frac{n-1}{2}}}{-3}=\frac{4^{\frac{n-1}{2}}-1}{3}=\frac{2^{n+1}-1}{3}\) en repérant que \(2^{2}=4\) et qu'il s'agit d'une somme de termes consécutifs d'une suite géométrique de raison 4.CQFD.
Si n est pair, le code binaire correspondant au code de Gray \(11 \ldots 11\) est du type \(10 \ldots 010\) qui correspond à l'entier

\[ \begin{gathered} 2^{1}+2^{3}+\cdots+2^{n-1}=2+2 \times 4+2 \times 4^{2}+\cdots+2 \times 4^{\frac{n-2}{2}}=2 \times \frac{1-4^{\frac{n}{2}-1+1}}{1-4}=2 \times \frac{1-4^{\frac{2}{2}}}{-3} \\ =2 \times \frac{4^{\frac{n}{2}}-1}{3}=2 \times \frac{2^{n}-1}{3}=\frac{2^{n+1}-2}{3} . \mathrm{CQFD} . \end{gathered} \]

b) C'est la remarque de la question 3 (partie A) qui est à l'œuvre : la constitution de la suite des codes de Gray empêche ( tout comme la résolution du spin-out) de répéter le changement d'un chiffre sous peine de retour au code de Gray précédent. On va donc alterner les actions de deux types.
L'une qui va modifier le chiffre le plus à droite (qui a la priorité pour la création d'un nouveau code), et l'autre qui va modifier un autre chiffre que le dernier, mais le plus à droite possible, «en imposant que cela ne donne pas un code déjà rencontré »)... Un code sur deux change le chiffre le plus à droite ce qui correspond bien au mouvement A ... II reste à expliquer pourquoi l'autre est B :
La procédure d'élaboration des codes de Gray, et plus précisément la priorité donnée au chiffre le plus à droite possible dans le passage au code suivant, conduit à affirmer qu'un chiffre ne peut être égal à 1 tant que toutes les combinaisons affectant les chiffres suivants ( donc plus à droite...) n'ont pas été déjà rencontrées au moins une fois... Changer n'importe quel chiffre à partir du « dernier \(\mathbf{1}\) » (compris) renvoie donc à un code déjà vu. Le chiffre immédiatement à gauche du «dernier 1» est donc celui dont le changement garantit un code de Gray inédit, et c'est bien ce que fait le mouvement B du spin-Out.
c) La résolution du spin-out de longueur n correspond à passer d'un code composé de n chiffres 1 à celui composé de n chiffres 0 . Cela va donc se traduire par le passage du nombre entier correspondant au code de Gray \(11111 \ldots .1\) (appelons N l'entier codé ainsi) au code de Gray \(0000 \ldots . .0\) (qui code l'entier 0 ). À chaque mouvement (alternativement A et B) correspondra le passage de l'entier k à l'entier k-1 , en fournissant un nombre minimal de mouvements puisque toute cassure de l'alternance conduit « à revenir en arrière » sur le chemin de la résolution, c'est-à-dire «remonter à l'entier immédiatement supérieur », correspondant au code trouvé
précédemment

-- Partie C : Résolution du Spin Out à n boutons ---

1. Le mouvement A est son propre inverse, (exécuter deux fois A d'affilée revient à la position de départ), de même pour le mouvement \(B\).
   Toute chaîne constituée de A et de B, conduisant du code composé exclusivement de 1 au code de même longueur composé exclusivement de 0 permettra en la symétrisant de fournir la chaîne appliquant la transformation en sens inverse... Il est évident que deux chaînes « symétriques » ont la même longueur et que la chaîne minimale pour la première transformation donnera la chaîne minimale pour la transformation réciproque.
2. Intéressons-nous à la fonction \(S\) : en décomposant la transformation :Déterminer \(S\) (1) et \(S\) (2).
   a) \(\mathrm{S}(1)\) est le nombre minimal de mouvements pour passer d'un code formé exclusivement de un chiffres 1 à celui de même longueur formé uniquement de 0 . Donc \(S(1)=1\).
   De même d'après le tableau de la question B)1)c), on \(S(2)=2\).
   b)
   départ : \(11111 \ldots .11\) ( \(N\) chiffres, on suppose \(N>2\) )
   étape 1 : \(110000 \ldots .00\) ( 2 chiffres « 1 » suivis par \(N-2\) chiffres « 0 »)
   La transition nécessite \(S(N-2)\) mouvements car seuls les \((N-2)\) derniers chiffres ont été affectés.
   étape 2 : \(010000 \ldots 00\) ( On change le premier chiffre qui passe de 1 à 0 par le mouvement B... soit un seul mouvement)
   étape 3 : \(01111 \ldots 11\) (un seul chiffre « 0 » et ( \(N-1\) ) chiffres « 1 »)
   Il a fallu changer les ( \(N-2\) ) chiffres « 0 » en chiffres « 1 » il faut donc \(S(N-2)\) mouvements.
   étape 4 : 0000... 00 ( \(N\) chiffres « 0 »)
   Il a fallu changer les \((N-1)\) chiffres « 1 » en « 0 », il faut donc \(S(N-1)\) mouvements.
   Le nombre de mouvements est donc la somme de ces éléments car seul le mouvement B permet de changer le premier chiffre « 1 » en « 0 », et cela suppose que le deuxième chiffre soit un « 1 ». Donc :
   \(S(N)=S(N-2)+1+S(N-2)+S(N-1)=S(N-1)+2 \times S(N-2)+1\). CQFD

a) Traitement

Tant que \(I \(I\) prend la valeur \(I+1\)
\(T\) prend la valeur \(R\)
\(R\) prend la valeur \(S\)