Sujet
Préliminaire : en informatique, un mot est une suite de 0 et de 1 .
Par exemple : 010011 est un mot.
- Combien peut-on former de mots de \(n\) chiffres ( \(n\) non nul) ?
- Expliquer pourquoi un mot d'au moins 4 chiffres comporte forcément, dans son écriture, deux blocs de chiffres consécutifs identiques.
A) Une transformation
On considère la transformation \(P\) qui opère sur les mots en remplaçant chaque 0 par 01 et chaque 1 par 10.
Ainsi :
\[
P(0)=01 \text { et } P(1)=10 .
\]
Si on considère par exemple le mot 010 alors : \(P(010)=(01)(10)(01)=011001\).
A vous de jouer : déterminez \(P(11)\) et \(P(100)\).
B) La suite de Protéus
La suite de Protéus \(\left(t_{n}\right)_{n \in \mathbb{N}}\) est définie ainsi : \(t_{0}=0 ; t_{1}=P\left(t_{0}\right) ; t_{2}=P\left(t_{1}\right) ; t_{3}=P\left(t_{2}\right)\) etc., c'est-à-dire pour tout entier \(n\) positif, \(t_{n+1}=P\left(t_{n}\right)\).
- Déterminer \(t_{1}, t_{2}\) et \(t_{3}\).
- Déterminer en fonction de \(n\) le nombre de chiffres qui composent \(t_{n}\). Expliquer.
- Y a-t-il toujours autant de 1 que de 0 dans chaque mot \(t_{n}\) de la suite de Protéus, pour tout entier \(n\) strictement positif? Expliquer.
C) Le miroir
Pour tout mot \(m\), on note \(\bar{m}\) le mot obtenu en remplaçant dans \(m\) le chiffre 0 par 1 et le chiffre 1 par 0.
Par exemple : si \(m=010\) alors \(\bar{m}=101\).
- Déterminer \(P(\overline{0})\) et \(P(\overline{1})\); pour tout mot \(m\), comparer : \(P(\bar{m})\) et \(\overline{P(m)}\)
- a) En observant les mots \(t_{1}, t_{2}\) et \(t_{3}\) vérifier qu'on peut construire simplement \(t_{2}\) à partir de \(t_{1}\) ainsi que \(t_{3}\) à partir de \(t_{2}\).
b) Expliquer pourquoi cette relation se poursuit de proche en proche et comment on peut construire \(t_{n+1}\) à partir de \(t_{n}\) pour tout entier \(n \in \mathbb{N}\).
c) Comment peut-on retrouver à partir de cette relation le nombre de 0 et de 1 dans un mot quelconque \(t_{n}\) ?
d) Quels sont les deux derniers chiffres du mot \(t_{2015}\) ?
Aucun corrigé disponible pour cet exercice dans la source APMEP.