On a un stock (illimité) de jetons rouges et de jetons bleus.
On a une bande constituée de cases, elle aussi illimitée à droite et à gauche.

Initialement, une seule case est non-vide et contient un jeton rouge, la bande ressemble donc à ceci : [latex]\ldots\fbox{R}\ldots[/latex], les pointillés représentent des cases vides.

Le but est qu'il ne reste plus qu'un jeton bleu sur la bande.
[TeX]\ldots\fbox{B}\ldots[/TeX]
Pour cela, il y a des règles à suivre :

1) On peut ajouter un bleu à la suite d'un rouge s'il est en bout de bande

(ainsi on peut passer de ... RBBR... à ...RBBRB... ou à ...BRBBR...

2) On peut dupliquer la séquence, à droite (ou à gauche ce qui revient au même)

(ainsi de ...BRBBRRB..., on peut passer à ...BRBBRRBBRBBRRB...)

3) On peut transformer 3 rouges consécutifs en un bleu :

(ainsi de ...BRBRRRB..., on peut passer à ...BRBBB...)

4) On peut supprimer deux bleus consécutifs

(ainsi de ...BRBRBBR..., on peut passer à ...BRBRR...)

Est-il possible de passer de "...R..." à "...B..." preuve à l'appui ?

PS : librement adapté d'une énigme de Spoiler : [Afficher le message] D.H.