Exercice 1 — L'automate à dépiler

Sujet

Dans un atelier de construction aéronautique, les pièces produites sont placées sur deux piles comme le montre le dessin ci-contre. Pour tout le problème, on notera a le nombre de pièces dans la pile \(A\), et \(b\) le nombre de pièces dans la pile \(B\).
Pour la gestion du stock des pièces de l'atelier, on utilise un automate. Il est chargé de « dépiler » les pièces produites, c'est-àdire de vider complètement les deux piles de pièces.
Cependant, cet automate ne sait exécuter que deux opérations :
O1 - Enlever un même nombre de pièces de chaque pile.
O2-Ajouter des pièces sur une des piles afin de doubler le

nombre de pièces qu'elle contient.
Avec l'exemple ci-dessus, l'automate est capable de « dépiler » : en effet, il double une première fois, le nombre de pièces dans la pile \(B\) (opération O 2 ), puis une seconde fois \((\mathrm{O} 2)\); on a ainsi 4 pièces dans chaque pile. En appliquant l'opération O1, l'automate peut vider les deux piles de pièces.

Partie A : premier fonctionnement

1. Pour \(a=2018\) et \(b=2017\), l'automate est capable de « dépiler ».
   a. Expliquer comment.
   b. Est-il capable de dépiler en au plus trois opérations ?
2. Pour \(a=37\) et \(b=29\), l'automate est capable de « dépiler ».
   a. Expliquer comment.
   b. Est-il capable de « dépiler » en au plus trois opérations ?
3. Pour \(a=1515\) et \(b=1492\), l'automate est-il capable de « dépiler » ?
4. Pour un nombre quelconque de pièces \(a\) et \(b\) dans chaque pile, l'automate est-il capable de « dépiler » ? Si oui, proposer une méthode ou un algorithme (rédigé en langage naturel). Si non, proposer un contreexemple.
5. Dans le cas où \(b \leq a<2 b\), est-ce que l'automate est capable de « dépiler » en au plus trois opérations ? Justifier la réponse.

Partie B : un deuxième fonctionnement

On modifie le fonctionnement de l'automate : l'opération O2 est transformée en « Ajouter des pièces sur une des piles afin de tripler le nombre de pièces qu'elle contient »
6. On note \(d\) la différence entre les effectifs des piles A et B . Ainsi, \(d=a-b\).
a. Comment évolue \(d\) quand on applique l'opération O 1 ?
b. On applique la nouvelle opération O 2 , et on note \(d^{\prime}\) la nouvelle différence. Démontrer que \(d^{\prime}-d\) est un multiple de 2 .
7. En déduire que pour \(a=2018\) et \(b=2017\), l'automate ne peut pas « dépiler. »