Sésame, ouvre-toi

Voici un nouvel exercice tiré du http://www.animath.fr/IMG/pdf/ofm-2012-2013-envoi2.pdfdans la discussion Test d'entrée à l'Olympiade...

Exrcice 8 a écrit:

Un digicode s’ouvre dès qu’on fait l’unique combinaison correcte de 4 chiffres (qui peut éventuellement contenir des répétitions). Par exemple, si l’on tape la suite des chiffres 000125 le digicode
s’ouvrira si le code est soit 0001, soit 0012, soit 0125.
Petit Pierre ne connaît pas le code. Combien de chiffres au minimum doit-il taper pour ouvrir le digicode à coup sûr ?

Pour s'attaquer à ce type de questions, on a souvent intérêt à essayer de voir comment ça fonctionne sur un modèle plus petit
Ainsi, j'ai essayé de traiter le cas de codes à 3 chiffres dans un sytème de numération de base 4
Il y a alors 64 combinaisons digicode possibles, et j'ai trouvé une "clé universelle" de 66 chiffres, ce qui est optimal, parce que dans unel iste n éléments on ne peut choisir que (n-2) groupes distincts de trois éléments consécutifs.
Voici cette clé:
0010020030110120130210220230310320331121131221232132223133233300

Pour composer cette clé, j'ai appliqué l'algorithme suivant:

Sésame a écrit:

je commence par 000, puis chaque fois que j'ajoute un chiffre,
je le choisis le plus petit possible, mais de sorte que les trois deniers chiffres composent le plus petit nombre qui n'ait pas encore été listé.

J'ai été obligé de déroger à cette règle quelques fois fois (chiffres rouges), car, par exemple, 300 induisait deux zéros consécutifs et 000, 001, 002, et 003 étaient déjà listés.
Par chance(?) la suite balaye toutes les combinaisons de 3 chiffres choisis parmi 0,1,2,3.

Pour le problème original, j'imagine qu'un algorithme de ce genre sera reconductible, même règle avec des exceptions, ce qui donnerait alors un Sésame de 10 003 chiffres.

Mais comment puis-je prouver que cette clé existe effectivement sans l'écrire et l'examiner?

[ Edit: Message corrigé ce matin: plusieurs exceptions à la règle]