omb
Menu principal
Sujets d'articles
OMB 2014 Finale MAXI Question 1 Informations | BxMO 2017 | SBPM  
OMB 2014 Finale MAXI Question 1
2431 vues  | Retourner à la liste des questions

Les Babeleirs parlent la babelangue, qui s'écrit au moyen d'un alphabet de deux lettres, et . 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 appartient au lexique.

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

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

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


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

(b) Le mot appartient-il au lexique ?

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

(d) Le mot appartient-il au lexique ?

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

(f) Combien y a-t-il de mots de 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
à si est pair () et à si est impair ()
ce qui est exactement égal à
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



Càd ta réponse Mais j'ai préféré changé, je me demande bien pourquoi .

PS: est la partie entière de
Anonyme
Posté le : 11/1/2015 14:14  Mis à jour : 11/1/2015
j ai un de ses gros zizi
Membres
Prénom :

Nom :

Mot de passe : 

Conserver la connexion

Récupérer mot de passe
Recherche
Le site officiel de l'Olympiade Mathématique Belge
Contact webmasters :
Référencement