OMB - OMB 2014 Finale MAXI Question 1

OMB 2014 Finale MAXI Question 1

3927 vues | Retourner à la liste des questions

Les Babeleirs parlent la babelangue, qui s'écrit au moyen d'un alphabet de deux lettres, $A$ et $B$ . Les mots de leur lexique sont tous ceux qui découlent des règles suivantes, et uniquement ceux-là:

R1. Le mot d'une seule lettre $B$ appartient au lexique.

R2. Si un mot du lexique contient un $B$ , le mot obtenu en remplaçant ce $B$ par $ABA$ appartient aussi au lexique.

R3. Si un mot du lexique contient deux $A$ successifs, alors le mot obtenu en les remplaçant par un $B$ appartient aussi au lexique.

R4. Si un mot du lexique contient deux $B$ successifs, alors le mot obtenu en les supprimant appartient aussi au lexique.

(a) Le mot $AA$ appartient-il au lexique de la babelangue ?

(b) Le mot $AAA$ appartient-il au lexique ?

(c) Le mot vide (formé de zéro lettre) appartient-il au lexique ?

(d) Le mot $BABA$ appartient-il au lexique ?

(e) Décrire l'ensemble des mots du lexique comportant exactement deux $B$ .

(f) Combien y a-t-il de mots de $n$ lettres dans le lexique de la babelangue ?

Solution(s) proposée(s) :

Les commentaires appartiennent à leurs auteurs. Nous ne sommes pas responsables de leur contenu.

Corentin Bodart	Posté le : 23/4/2014 21:54 Mis à jour : 23/4/2014
1/ Le nombre de A est influencé par R2 (+2) et R3 (-2) => (invariant) le nombre de a est pair. 2/ Il est possible de créer une suite de 2n A en applicant n+1 R2 sur B, R3 sur AA adjacent à B puis R4. 3/ si le nombre de A est non-nul, il est possible de créer un B n'importe où : (milieu) ..AA.. > ..B.. > ..ABA.. (coté) AA.. > B.. (-2 A) et AA>B>ABA>AABAA>AAABAAA>ABBAAA>AAAA (+2A) 4/ si le nombre de A = 0, il est possible de créer une suite B ..B..>ABA>AABAA>AAABAAA>ABBAAA>AAAA>..BB.. En bref, un mot est realisable ssi le nombre de A est pair (a)(c)(d) Oui (b) Non (e) Voir ci dessus (f) Seule restriction voir ci-dessus. Pour y remedier, choisir n-1 lettre(s) et la dernier sera A ou B en fonction des précedents => 2^(n-1) Trivial (après UN PEU de reflexion) Edit : 1 oubli : pour n = 0, le nombre de mot = 1,

Anonyme	Posté le : 23/4/2014 23:03 Mis à jour : 23/4/2014
zut, j'ai mis comme réponse à (f) que c'était égal à $\sum\limits_{i=0}^{k}{2k\choose2i}$ si $n$ est pair ( $n=2k$ ) et à $\sum\limits_{i=0}^{k}{2k+1\choose2i}$ si $n$ est impair ( $n=2k+1$ ) ce qui est exactement égal à $2^n-1$ J'espère que le correcteur le sait

Anonyme	Posté le : 23/4/2014 23:06 Mis à jour : 23/4/2014
par contre je n'ai pas prouver aussi détaillé que toi, que en faite la seule condition est que A doit apparaitre un nombre pair de fois A.B.

Corentin Bodart	Posté le : 24/4/2014 0:27 Mis à jour : 24/4/2014
L'explication est sûrement un peu moins claire sur la feuille. J'avais aussi $\sum_{i=0}^{E(n/2)}\binom{n}{2i}$ Càd ta réponse Mais j'ai préféré changé, je me demande bien pourquoi . PS: $E(x)$ est la partie entière de $x$

Anonyme	Posté le : 11/1/2015 14:14 Mis à jour : 11/1/2015
j ai un de ses gros zizi

Anonyme	Posté le : 28/2/2021 14:59 Mis à jour : 28/2/2021
Ici c'est pour les solutions pas pour les trucs pas très halal

Anonyme	Posté le : 28/2/2021 15:00 Mis à jour : 28/2/2021
Ouai