omb
Menu principal
Sujets d'articles
OMB 2015 Finale MAXI Question 2 Informations | BxMO 2017 | SBPM  
OMB 2015 Finale MAXI Question 2
2199 vues  | Retourner à la liste des questions

Tous les mots non vides formés de lettres toutes différentes apparaissant dans l’ordre alphabétique sont rangés dans l’ordre déterminé par les deux règles suivantes :

— S’il y a dans le mot une lettre qui, dans l’alphabet, vient après toutes les lettres du mot , alors précède ;

— Si les mots et diffèrent tout en ayant la même dernière lettre, distinguons deux cas :
     — Si de plus et ont chacun au moins deux lettres, alors et se rangent dans le même ordre que les mots obtenus en les privant de leur dernière lettre ;
     — Si de plus un des deux mots et est formé d'une seule lettre, alors il vient avant l'autre mot.

Le début du dictionnaire est donc A, B, AB, C, AC, BC, ABC, D, AD, BD, ... Quel est le rang occupé, dans ce dictionnaire, par le mot DEFI ?



Solution(s) proposée(s) :


 
Les commentaires appartiennent à leurs auteurs. Nous ne sommes pas responsables de leur contenu.
Corentin Bodart
Posté le : 30/4/2015 20:29  Mis à jour : 30/4/2015
En retournant les mots, on obtient l'ordre alphabétique ...

Après un rapide décompte, le rang voulu s'avère être



Ce qui se résume à


Anonyme
Posté le : 17/11/2019 19:00  Mis à jour : 17/11/2019
Précision apportée par Merlin Michalski

Alors, tout d'abord, comment compte-t'on par exemple le nombre de possibilités pour la lettre n ?

2 possibilités : on prend ou pas la lettre m, ou on ne la prend pas

Pour chacune de celles-ci, on a encore deux possibilités : l ou pas l

k ou pas k

j ou pas j

...

a ou pas a

Le nombre de possibilités pour un mot se terminant par la lettre n est donc 2 exposant le nombre de lettres précédant n (13).

Pour savoir le nombre de mots précédant DEFI, il faut d'abord savoir le nombre de mots qui contiennent des lettres plus petites que I:

A, B, C, D, E et F . Et faire la somme : P(A)+P(B)+P(C)+P(D)+P(E)+P(F)=2(0)+2(1)+2(2)+2(3)+2(4)+2(5)+2(6)+2(7)

P(x) = le nombre de possibilités de mots se terminant par la lettre x
2(x) = 2 exposant x

Alors, soit on utilise la formule d'une somme géométrique, soit le fait que la somme de puissances de deux tend toujours vers la puissance supérieure: Dans les deux cas, on sait que c'est égal à

2(8)-1

Maintenant que l'on est bien certain que ce mot se termine par I, on va chercher à ce que l'avant-dernière lettre soit F. Pour cela, on ne va plus considérer le I, et faire comme si F était la dernière lettre. En effet, la façon de ranger reste identique à l'intérieur d'une lettre, comme pour un dictionnaire classique.
En appliquant un raisonnement similaire, on obtient donc:

2(5)-1

Pour E (toujours en appliquant le même raisonnement):

2(4)-1

Et pour D:

2(3)-1

Voilà, on vient de compter tous les mots venant avant DEFI. Il ne reste donc plus qu'à ajouter DEFI et le tour est joué

2(8)-1+2(5)-1+2(4)-1+2(3)-1+1 = 256 + 32 + 16 + 8 -3 = 309
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 :