Exercice 3 — Une histoire de digicode

Sujet

Une porte est protégée par un digicode sans touche « valider ». Ainsi si le code pour ouvrir la porte est à 4 chiffres, lorsque l'on tape 315782 on teste en fait trois codes : 3157 formé des quatre premiers chiffres, 1578 formé des quatre suivants, ainsi que 5782 formé des quatre derniers. Existe-t-il une suite de chiffres qui nous permette de tester assez rapidement tous les codes? Peut-on trouver une suite qui nous permette de tester un nouveau code à chaque nouveau chiffre introduit sans jamais tester deux fois le même ? La réponse à ces questions a été donnée en 1946 par N.G De Bruijn (1918-2012) mathématicien hollandais.

Nous allons dans cet exercice essayer de comprendre son idée grâce à des cas simples.

1. Dans cette question, on dispose de deux touches numérotées \(\{0 ; 1\}\) et on veut tester tous les codes à trois chiffres.
   a) 011 est l'un des codes à trois chiffres que l'on peut faire avec ce digicode. Citer tous les codes.

Voici une suite composée de 0 et de 1 : 00010111, représentons la sous la forme d'un cercle (voir ci-dessous en partant d'en haut).

Cette suite contient tous les codes à trois chiffres que l'on peut faire avec notre digicode et chaque code n'apparaît qu'une seule fois. Pour tester tous les codes à trois chiffres de notre digicode à deux touches, il suffit donc de rentrer cette suite (en répétant à la fin les deux premiers chiffres de la suite). Une telle suite est appelée suite de De Bruijn ( 2 ;3) où « 2 » représente le nombre de touches du digicode et où « 3 » représente la longueur des codes que l'on veut tester.
On appellera suite de De Bruijn ( \(n\); \(l\) ) une suite qui, lorsqu'on la représente sous la forme d'un

cercle, contient une et une seule fois tous les codes à \(l\) chiffres d'un digicode à \(n\) touches.
b) Parmi ces suites, lesquelles ne sont pas des suites de De Bruijn (2;3) ? Justifier.
A : 0001110101
B : 0010111
C : 111010001
D : 10001011
2. Dans cette question on veut trouver une suite de De Bruijn ( 2 ; 2 ), c'est-à-dire qui permet de tester tous les codes à deux chiffres d'un digicode à deux touches.
a) Donner tous les codes à deux chiffres que l'on peut faire avec notre digicode à deux touches \(\{0 ; 1\}\).
b) Donner une suite de De Bruijn ( 2 ; 2).