Bonsoir (ou bonjour),

J'ai vu sur un site le problème suivant :

Citation

Le petit Ababa joue avec les lettres de son alphabet. Il s'est
inventé les règles suivantes:

• si dans un mot, il trouve un A suivi d'un B, il peut les remplacer par la séquence BAA
• si dans un mot, il trouve deux B qui se suivent, il peut les retirer du mot
• si dans un mot, il trouve trois A qui se suivent, il peut les retirer du mot.

En partant du mot ABABABAABAAB, quel est le mot le plus court qu'il
puisse obtenir?

Personnellement, je pense que le mot le plus court est. Oui, rien du tout ! Il peut effacer toute les lettres mais je n'ai réussi que "AB"...

Voici comment j'ai fait :


Enfin voilà, donc si vous avez une idée pour supprimer, SI C'EST POSSIBLE, toutes les lettres, j'aimerais savoir comment vous faites. Et avec des couleurs ce serais bien (pour aider à la lecture).

Tu ne peux pas supprimer tous les B (pourquoi ?), donc si tu trouves un mot plus court, ce sera le mot "B".

Tu devrais chercher la raison qui empêche de supprimer tous les B toi-même, mais voilà l'idée :


Edit: j'arrive à montrer que AB est le plus court en faisant quelque chose de similaire avec A, et aussi qu'on ne peut pas atteindre BA par exemple

Citation : gnomnain

[...]Tu devrais chercher la raison qui empêche de supprimer tous les B toi-même[...]

Et bien j'ai pensais à cela :

Pour enlever tout les B, il en faut un nombre pair. Hors, il ne peut y avoir de nombre pair même en changeant les AB contre les BAA (ce qui donne toujours un B en fait). Les changements ne font que rajouter un A, ce qui donne la possibilité, en revanche, de supprimer tout les A !

Donc en effet, le "mot" le plus court est B !

Il n'est pas dit qu'on puisse toujours enlever tous les A.
exemple bête : BA

Citation : LynxMankill

Les changements ne font que rajouter un A, ce qui donne la possibilité, en revanche, de supprimer tout les A !

Je n'ai jamais dit : Il seras TOUJOURS possible d'enlever tout les A.

oui, mais tu affirmes ensuite que le mot le plus court à partir de ton mot de départ et bien B, ce qui sous entend que l'on peut supprimer tous les A de l'exemple alors que tu ne l'avais pas montré. J'ai donc cru que tu pensais qu'on pouvait toujours trouver un moyen de supprimer tous les A. Tant mieux si ce n'est pas le cas .

Moi je suis tombé sur BA.

abababaabaab
baabaaabaaabaa
baabbbaa
baaaa
ba

Citation : Gaimon

Moi je suis tombé sur BA.

abababaabaab
baabaaabaaabaa
baabbbaa
baaaaa
ba

Normalement, à ton :

baaaaa

Tu doit atteindre après :

baa

Et non ba...

Ah ! C'est juste que j'ai tapé un a de trop dans l'avant dernière étape.

Citation : LynxMankill

Donc en effet, le "mot" le plus court est B !

Non, il n'est pas possible d'atteindre le mot "B" tout seul, voir l'edit dans mon message précédent. En fait, j'ai montré que AB est le mot le plus court qu'on puisse atteindre parce qu'il restera forcément un A et un B au moins. Pas besoin de chercher plus !

A mais oui ! Je croyais que j'avais réussi à faire B, c'est pour ça.

Par contre, je n'ai absolument rien compris à ton charabia.
Sa doit être parce que j'ai pas appris ça...

Euh, en fait, l'idée c'est que tu veux trouver une valeur qui ne change pas avec les trois opérations. Par exemple, pour les B c'est assez simple : il y a une seule opération qui change le nombre de B, et elle en transforme 2 en 0 dont la parité est conservée. Donc, un invariant pour ton ensemble d'opérations est la parité du nombre de B.

Pour un invariant qui porte sur les A c'est un peu plus compliqué. Si on ne regarde que la première opération, on voit qu'elle transforme AB en BAA : on voudrait donc que les A à gauche d'un B valent deux fois plus que les A à droite. Donc on va leur attribuer la valeur <math>\(2^n\)</math> où n est le nombre de B à droite, et on s'intéresse à leur somme <math>\(S\)</math>. Par exemple, pour AB, la somme est 2, et pour BAA aussi.
Maintenant, on doit s'occuper des deux autres opérations : celle qui enlève trois A consécutifs veut dire qu'on ne va pas pouvoir considérer que S ne varie pas. Par contre, le reste de S pour la division par 3 ne varie pas lui (c'est pour ça que je dis "modulo 3") puisqu'on enlève 3 fois quelque chose. Il reste à vérifier que ça marche avec la règle qui enlève deux B, et c'est le cas.
Donc, notre invariant est le reste de <math>\(S\)</math> pour la division par 3.

Maintenant, si on a ABABABAABAAB, la somme vaut <math>\(S = 2 \times 2 + 2 \times 4 + 8 + 16 + 32 = 68\)</math>, dont le reste pour la division par 3 est 2, alors que pour B (ou le mot vide), <math>\(S=0\)</math>.

(La version de mon premier message a un calcul un peu plus simple parce que j'ai directement simplifié les puissances de 2, mais en fait c'est la même chose)