Hmm, je cherche... Il me semble que les nombres du type 323132303231323 sont les plus efficaces. Cependant, je n'arrive pas encore à démontrer qu'on ne peut fabriquer un nombre de taille 2^b, je n'ai pas trouvé l'astuce.

Il me semble que le résultat ne change pas si l'on restreint l'énoncé aux extraits commençant à l'endroit d'un chiffre de rang pair, ça va peut être m'aider à trouver la démo.

Bonjour,
En premier lieu, il est facile de remarquer que l'on peut trouver un nombre de longueur 2^b-1 en base b.
Supposons que l'on dispose d'un alphabet de b symboles 0,...,b-1 (permet d'inclure b = 1)
Procédons par récurrence:
Initialisation:
b = 1:
0 est une solution.

Hérédité:
supposons qu'il existe une solution m de longueur 2^b-1
pour b+1, le mot mbm est une solution, et est de longueur 2^(b+1)-1

En revanche, je n'ai pas réussi à montrer que l'on ne pouvait pas aller au delà, ni beaucoup pris de temps pour y trouver un contre exemple

Ha ben si, cette piste m'a aidé à trouver une solution, finalement

Considérons un nombre de taille [latex]2^b[/latex], noté [latex]x_{1}x_{2}...x_{2^b}[/latex]. On regarde les extraits de taille 2, 4, 6... : [latex]x_{1}x_{2}[/latex], [latex]x_{1}...x_{4}[/latex], [latex]x_{1}...x_{6}[/latex], ... , [latex]x_{1}...x_{2^b}[/latex]. Il y a [latex]2^{b-1}[/latex] tels extraits.

Maintenant, étant donné un extrait de longueur paire, on appelle "reste" de cet extrait ce qu'il reste quand on l'a épuré de ses doublons. Par exemple, si l'extrait est 023121312321, alors le reste est 03 (l'ordre n'est pas important). Il y a [latex]2^{b-1}[/latex] restes possibles pour les extraits en base b. Par exemple, les 8 restes des extraits en base 4 sont {},01,02,03,12,13,23,0123.

Reprenons notre nombre de taille [latex]2^b[/latex]. Nous allons démontrer qu'il est possible d'en trouver un extrait dont le reste est {}, ce qui suffira à démontrer le résultat.

Parmi les extraits de taille 2, 4, 6... commençant par [latex]x_{1}[/latex] dont nous parlions, ou bien un extrait a pour reste {}, et c'est gagné. Sinon, il y a [latex]2^{b-1}-1[/latex] restes possibles, et [latex]2^{b-1}[/latex] extraits : par le lemme des tiroirs, il existe deux extraits [latex]x_{1}...x_{i}[/latex] et [latex]x_{1}...x_{j}[/latex] avec le même reste. L'extrait [latex]x_{i+1}...x_{j}[/latex] a donc pour reste {}, cqfd.

Alors, la variante de la preuve qu'on ne peut pas aller au dela de 2^b -1 chiffres.

On définit un nombre binaire de b chiffres, dont le rang de chaque bit est indexé à un chiffre de b. Un code spécifique k est associé aux k-ièmes premiers chiffres de notre plus grand nombre: il représente, pour chaque chiffre de b, la parité du nombre d'apparitions de ce chiffre depuis 1 jusqu'à k. Comme le nombre de codes possibles est 2^b-1 (le code 000...est exclu, car tout pair), au bout de 2 ^ b chiffres de ce plus grand nombre, il y a forcément 2 codes identiques. Si ces 2 codes sont aux rangs i et j, leur différence étant nulle, dans l'intervalle j-i chaque chiffre apparait un nombre pair de fois. Donc notre plus grand nombre ne peut pas comporter plus de 2^b - 1 chiffres.

CQFD

Peu de réponses, mais c'était tout de même assez particulier.....