Inscription / Connexion Nouveau Sujet
mots composés des lettres M, A, T, H
Salut,
En doutant, nous venons à la recherche, et en cherchant, nous percevons la vérité.
La date de mariage de l'auteur de cette phrase a un rapport avec le nombre que l'on cherche.
Trouver le nombre (ou à défaut le nombre de chiffres de ce nombre) de mots de 2023 lettres
écrits avec les 4 lettres M, A, T, H tels qu'un M ne soit jamais à côté d'un H.
Bonjour,
je trouve comme GBZM mais je doute qu'il ait fait le calcul à la main en 30 minutes !
La formule de récurrence est très simple et mon logiciel préféré obtient le résultat instantanément :
Cliquez pour afficher
On appelle "mot acceptable" une suite finie de caractères M, A, T, H dans laquelle on n'a jamais M à côté de H.
Notons les nombres de mots acceptables de longueur
se terminant respectivement par M, A, T et H.
Calculer en fonction de
.
Au fait, c'est 1117 et pas 1177.
Bonjour
Je « débarque » seulement sur ce problème (je ne parle pas de la variante). Bien sûr, en tapant cette phrase dans un moteur de recherche on a immédiatement l'auteur d'où ensuite la réponse pour l'année. Seulement, j'aurais une montagne de questions. Comment, alb12 as-tu imaginé ce problème. Autrement dit comment s'avais-tu que le nombre de mots de 2023 lettres formés avec 4 lettres sans que 2 de ces lettres ne se touchent soit un nombre de 1117 chiffres ? Je pense que tu as fonctionné « à l'envers » c'est-à-dire que tu as d'abord résolu le problème à l'aide d'un calculateur (que certains appelle un esclave), puis tu as rattaché ce nombre à un personnage lié à cette date. Pas mal comme démarche.
La 2e question est pour jandri. La récurrence fonctionne. Comment l'as-tu trouvée ? En cherchant j'aurais peut-être trouvé mais je n'ai pas cherché.
La 3e question est pour jarod128. Ca fonctionne. Même question que pour jandri. Comment l'as-tu trouvée ?
La 4e question est pour GBZM. Je ne comprends pas la formule que tu as donnée à manger à ton esclave.
Je sais, cela fait beaucoup de cours à recevoir. Bravo à tous.
"La 4e question est pour GBZM. Je ne comprends pas la formule que tu as donnée à manger à ton esclave. "
L'explication est donnée sous forme de question dans mon message de 09:50.
Je travaille avec quatre suites et une récurrence simple, facile à établir.
alb12 avec deux suites et également une récurrence simple (en fait son est mon
, et son
est mon
.
Jandri avec une seule suite (le nombre de mots acceptables de longueur
) et une récurrence double. Cette récurrence double, on peut la voir comme ça :
Un mot acceptable de longueur peut s'obtenir de trois manières à partir d'un mot acceptable de longueur
:
- en ajoutant M, A ou T si le mot se termine par M
- en ajoutant M, H ou T si le mot se termine par A
- en ajoutant M, H ou A si le mot se termine par T
- en ajoutant H, A ou T si le mot se termine par H
ou alors de deux manières à partir d'un mot de longueur : en ajoutant AA ou TT.
Dans tous les cas, on a à calculer une puissance de matrice (même si on présente pas lers choses ainsi) : la matrice 4x4 que j'ai donnée, la matrice
pour Jandri, la matrice
pour alb12.. Ces deux dernières matrices sont semblables, bien sûr.
Pour ma part, je suis arrivé à la formule de récurrence d'ordre 2 que j'ai résolu via l'équation caractéristique. Ce n'est plus au programme du lycée.
Bonsoir à tous,
J'ai essayé de comprendre la formule ..
On suppose qu'on a un mot de 2023 lettres avec les lettres M, A, T, H, telles qu'un M ne soit jamais à côté d'un H.
On peut considérer chaque lettre comme une variable qui peut prendre les valeurs 0 ou 1, où 0 représente l'absence de la lettre et 1 représente la présence de la lettre.
On fait cette reformulation pour trouver le nombre de combinaisons possibles de 2023 lettres avec les lettres M, A, T, H, qui satisfont la condition donnée.
Est-ce que la matrice A représente les contraintes à respecter ?
Si oui, alors chaque ligne de la matrice A correspond à une lettre dans l'ordre M, A, T, H, et chaque colonne correspond à la position de la lettre dans le mot (de gauche à droite). Les éléments de la matrice A sont alors définis de la manière suivante :
A[i][j] = 1 si la lettre i peut être suivie de la lettre j dans le mot (c'est-à-dire si les lettres i et j ne sont pas adjacentes dans le mot).
A[i][j] = 0 sinon.
La matrice V est un vecteur colonne avec des 1 pour chaque lettre possible.
Maintenant, pour obtenir le nombre de mots de 2023 lettres avec les lettres M, A, T, H, respectant la contrainte donnée, comment faites-vous pour obtenir ?
La puissance représente-t-elle le nombre de chemins de longueur 2022 dans un graphe dirigé, où les arêtes sont pondérées par les éléments de la matrice A ?
Chaque chemin correspond-t-il à une séquence de lettres satisfaisant les contraintes ?
Si oui, alors en multipliant avec
et ensuite avec
, on obtient le nombre total de ces chemins, c'est-à-dire le nombre de mots recherchés.
Par conséquent, donne le nombre de mots de 2023 lettres avec les lettres M, A, T, H, où un M n'est jamais adjacent à un H.
Ou alors je raconte du n'importe quoi..
Merci d'avance.
L'équation caractéristique de la récurrence d'ordre 2 n'est autre que le polynôme caractéristique de la matrice 2x2. On élève en fait cette matrice à la puissance par diagonalisation, sans le dire.
Bonsoir
suis arrivé à la formule suivante qui marche , mais que je n'ai pas réussi à simplifier davantage , si Un est le nombre de liste de n termes ne comprenant pas de M à coté de H ou l'inverse alors
U1=4 , U2=4²-2 = 14
Un = 6 + (4.
Uk) + 2Un-1 , avec k compris entre 1 et n-2 .
cette formule me donne U3=50 , U4=178
3Bonjour,
j'ai procédé de façon élémentaire (avec les connaissances du lycée). Je note le nombre de mots de n lettres écrits avec les 4 lettres M, A, T, H et tels qu'un M ne soit jamais à côté d'un H.
Je note le nombre de ces mots qui débutent par M (c'est le même que le nombre de ceux qui débutent par H).
Je note le nombre de ces mots qui débutent par A (c'est le même que le nombre de ceux qui débutent par T).
On voit sans difficultés que , que
et que
.
On en déduit :
d'où
On a immédiatement et
Il est alors facile d'écrire un petit programme python qui calcule
Merci jandri je viens finalement juste d'arriver à retrouver ta formule sur un brouillon que je n'ai pas encor mi en ligne
à partir de mon expression initiale
Un= 6 + 4Uk + 2Un-1 k allant de 1 à n-2 .
en ecrivant que :
Un+1= 6 + 4Uk + 2Un k allant de 1 à n-1 . = 6 + 4Uk + 4Un-1 +2Un , k allant de 1 à n-1 . comme 6 + 4Uk + 2Un+1 k allant de 1 à n-2 . = Un - 2Un-1
alors Un+1= Un - 2Un-1 + 4Un-1+2Un = 2Un-1+3Un
Bonjour,
NOUS CHUTAMES CAR UN MECHANT MATHEUX QUI CHOMAIT
HUMILIAIT AVEC ACHARNEMENT UN MATCH DE CHARMANTS MAMMOUTHS ET DE MANCHOTS ASTHMATHIQUES (ATCHOUM !) UN ALGORITHME NOUS
EMPECHANT DE MATCHER SOUS AMPHETAMINE NOUS NOUS HATAMES VERS UNE CHARMANTE CURE THERMALE ET RHUMATOLOGIQUE .
Bonjour
Bonne diversion dpi.
J'ai trouvé la formule de jarod128 sur Internet. Mais on ne dit pas comment elle est trouvée.
@dpi
il me semble qu'il y a deux intrus dans ton texte 
@derny
Cet exercice est tiré soit des olympiades soit de la preparation aux olympiades (Trouver les mots de n lettres etc)
Avec n =2023 je tombe sur un resultat à 1117 chiffres.
En tapant "annee 1117" je trouve l'annee de mariage d'un celebre couple d'amoureux.
"Mais on ne dit pas comment elle est trouvée." dis-tu.
La reponse n'est-elle pas dans les posts precedents ?
La mémoire me revient. J'ai retrouvé une étude que j'avais faite en 1997 (comme le temps passe) où j'avais étudié ce genre de récurrence et j'avais trouvé une méthode générale pour résoudre d'où la formule donnée par jarod128.
On peut en terminale trouver 2 suites geometriques solutions et admettre la forme generale des solutions puis determiner la solution avec les 2 premiers termes.
Au sujet de la suite 1, 4, 14, 50, 178, ... le rapport de 2 termes consécutifs tend vers (3+V17)/2 soit 3.56155 environ. D'où, à partir de n assez grand, le nombre de chiffres augmente de 1 tous les 20/(3+V17) soit tous les 2.8077 n environ.
Bonjour,
la méthode que j'ai proposée peut se généraliser d'au moins deux façons.
Première généralisation :
soit le nombre de mots de n lettres écrits avec les
lettres
et tels que pour
de
à
la lettre
ne soit jamais à côté de la lettre
(avec
).
On obtient la relation de récurrence avec les valeurs initiales
et
.
Dans le cas particulier on obtient
pour
.
Deuxième généralisation :
soit le nombre de mots de n lettres écrits avec les
lettres
et tels que pour
la lettre
ne soit jamais à côté de la lettre
(avec
).
On obtient la relation de récurrence avec les valeurs initiales
et
.
Dans la cas particulier on obtient
.
Par exemple pour cela donne
Annuler
connectez vous