Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 24-05-2011 18:35:09

EfCeBa
Administrateur
Enigmes résolues : ∞+1
Messages : 22×32×173

Taper aléatoirement sur une machine à écrrie

Soit une machine à écrire avec K caractères.

On tape aléatoirement N caractères sur la machine à écrire.

1 - Quelle est la probabilité qu'un mot de M caractères (M<=N) soit écrit ?
2 - Quelle est la probabilité que les M caractères d'un mot (M<=N) soient écrits ? (l'ordre n'est pas important ici)

NB : Il y a quelques mois le forum a vu passer un topic similaire avec un singe et récemment le concours étagère a vu une question de ce type posée, mais je voulais généraliser un peu le problème.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 24-05-2011 18:49:32

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

taper aléatoirement sut une machine à écrire

Le mot dans la première question doit-il être séparé par deux espaces quand il est au "milieu" et un espace quand il est sur les bords ou aucun si il fait K caractères ?

Et dans la deuxième quel est la taille du mot duquel on extrait les M lettres?


Un mathématicien complet est topologiquement fermé!

 #3 - 24-05-2011 19:13:37

EfCeBa
Administrateur
Enigmes résolues : ∞+1
Messages : 22×32×173

taper aléatoirement sur ube machine à écrire

@Yanyan
On entend par "mot" toute suite de caractères.
Le mot fait toujours M caractères.

 #4 - 24-05-2011 19:46:50

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Taper aléatorement sur une machine à écrire

Ouais, calculer avec des lettres ! Merci ch'Ef ! big_smile


1) On a une chance sur [latex]K^M[/latex] que le mot soit écrit sur les [latex]M[/latex] premiers caractères, puis (si [latex]N > M[/latex]) une autre chance sur [latex]K^M[/latex] que le mot soit écrit sur les caractères [latex]2[/latex] a [latex]M+1[/latex], puis etc.
Au final, ça nous donne a priori une proba de
[TeX](N-M+1) \times \frac1{K^M}[/TeX]
Sauf qu'il s'agit d'une proba a priori... Si le mot n'est pas écrit par les [latex]M[/latex] premiers caractères, je pense que cela donne une (maigre) indication sur ce que les lettres [latex]1[/latex] a [latex]M[/latex] ne sont pas, ou ne sont pas toutes en même temps.

Genre, si le mot est constitué de [latex]M[/latex] fois le même caractère, le fait qu'il ne soit pas écrit au début de la chaîne de [latex]N[/latex] caractères rend sa présence bien plus improbable sur les caractères [latex]2[/latex] a [latex]M+1[/latex], non ?

Ou alors je pense trop loin. Va pour [latex]\frac{N-M+1}{K^M}[/latex].


2) Est-ce que certains des caractères de M sont identiques ? Exemple avec M=N=3 et les dix chiffres comme caractères possibles : la chaîne de caractères 111 a une chance sur mille d'apparaître dans un ordre quelconque dans une chaîne de longueur 3, tandis que 123 a six chances sur mille (dans les chaînes 123, 132, 213, 231, 312, 321).

En gros, un caractère (que je vais noter [latex]m[/latex]) apparaissant [latex]\alpha[/latex] fois dans la chaîne que l'on veut trouver divise par [latex]\alpha ![/latex] la probabilité d'apparition dans le désordre.

Le "pire des cas" est donc celui où la chaîne a chercher est constituée de [latex]M[/latex] fois le même caractère, auquel cas la proba d'apparition dans la chaîne de longueur [latex]N[/latex] est :
[TeX]\frac{N !}{M! (N-M)!} \times \frac 1{K^M}[/TeX]
Le premier facteur est le nombre de façons de placer [latex]M[/latex] éléments parmi [latex]N[/latex] dans un ordre quelconque, soit [latex]C^N_M[/latex].

C'était le pire des cas ; dans le meilleur, tous les caractères sont différents, ce qui multiplie la proba par M! pour donner :
[TeX]\frac{N !}{(N-M)!} \times \frac 1{K^M}[/TeX]
On tombe, en lieu et place des combinaisons, sur des arrangements. Logique, non ?

Le cas général, maintenant : le mot a trouver est composé de [latex]m_i[/latex] fois le [latex]i[/latex]-ième caractère de l'alphabet, avec, bien sûr, [latex]\sum_{i=1}^K m_i = M[/latex]. Alors, la probabilité "optimale" (ci-dessus) est divisée par [latex]\prod_{i=1}^K (m_i !)[/latex], d'où la probabilité générale :
[TeX]\frac{N !}{K^M (N-M)! \prod_{i=1}^K (m_i !)}[/TeX]


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #5 - 25-05-2011 08:51:19

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

taper aléatoirement sur une machibe à écrire

On entend par "mot" toute suite de caractères.

Si un mot est par définition une suite de caractères, alors quand on tape N caractères on obtient un mot de N caractères.

Il y a un truc qui m'échappe je pense o_O

 #6 - 25-05-2011 10:16:35

EfCeBa
Administrateur
Enigmes résolues : ∞+1
Messages : 22×32×173

taoer aléatoirement sur une machine à écrire

@Nicouj, oui quand on tape N caractères on obtient un mot de N caractères.

Exemple K=26, N=6 et M=4 :
J'ai une machine a écrire de 26 caractères, les lettres de l'alphabet, je tapes 6 caractères ABCDEF, j'ai bien obtenu le mot ABCDEF, mais lui meme contient le mot de 4 lettres ABCD par exemple. La question 1 demande la probabilité d'avoir écrit ABCD (ou BCDE, ou CDEF).

 #7 - 25-05-2011 10:19:06

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

taper aléatoirement sur une machinr à écrire

Donc le mot de M lettres n'est pas fixé?


Un mathématicien complet est topologiquement fermé!

 #8 - 25-05-2011 10:45:35

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

Taper alééatoirement sur une machine à écrire

Ok j'ai mieux compris

Donc en tapant N lettres, j'écris N-M+1 mots de M lettres (donc forcément au moins un mot de M lettres ce que je croyais être la question ^^)

Si l'alphabet de la machine compte K caractères, il y a K^M mots de M lettres.

1)Donc j'ai (N-M+1)/K^M chances de taper un mot particulier   ?

2)Chacune des N lettres tapées au hasard a 1 chance sur K d'être la première lettre de mon mot. Si une lettre est bonne, chacune des N-1 restantes a une chance sur K d'être la 2eme lettres ...

Soit N/K * (N-1)/K * (N-1)/K * ... * (N-M+1)/K = [latex]\frac{N!}{K^M * (N-M)!}[/latex]

 #9 - 25-05-2011 12:18:19

Milou_le_viking
Professionnel de Prise2Tete
Enigmes résolues : 30
Messages : 434

Taper aléatoirement sur une machine à écrrire

Rappel: l'alphabet compte 26 caractère.

1. La probabilité qu'une chaine de N caractères commence par un mot donnée de M<=N caractères vaut: (1/26)^M. On s'en fout des autres caractères vu qu'il n'est pas dit que le mot ne doit pas être écrit plus d'une fois.
Il en découle la probabilité de trouver un mot de M caractères, quelques soit sa position qui vaut: (1+N-M).(1/26)^M.

2. Même raisonnement mais en multipliant par le nombre de permutations: N!.(1/26)^M

J'ai un sale préssentiment...

 #10 - 27-05-2011 21:12:41

EfCeBa
Administrateur
Enigmes résolues : ∞+1
Messages : 22×32×173

Taper aléatoirement sur une machine àà écrire

Je vous donne mes propositions de réponses :

1- La première question tout le monde est d'accord, le nombre de mots qui fonctionnent :[latex]{N-M+1}[/latex] divisé par le nombre de mots possibles [latex]{K^M}[/latex] soit : [latex]\frac{N-M+1}{K^M}[/latex]

2- MthS nous gratifie d'une explication avec des caractères distincts et non distincts, je n'avais pas forcément réfléchi à ce cas, mais il s'agit simplement de calculer les arrangements possibles des lettres. [latex]\frac{A^M_N}{K^M} = \frac{N!}{(N-M)!K^M}[/latex]

Bonnes réponses de MthS-MlndN, Nicouj et une partie pour Milou_le_viking.

 #11 - 27-05-2011 23:54:53

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1105
Lieu: Jacou

Taper aléatooirement sur une machine à écrire

Je ne suis pas du tout sûr de suivre les raisonnements.
Pour fixer les idées, revenons à l'exercice original, la question est: En tapant 10 caractères (K=26) aléatoires (N=10), quelle est la probabilité de voir apparaitre CIJM (M=4)?

CIJM peut apparaitre dans n'importe laquelle des 7 positions possibles (CIJM......, .CIJM....., ..CIJM...., ...) et les caractères autour sont choisis au hasard. Il y a donc à priori: 7*26^6 combinaisons qui répondent au problème sur 26^10 combinaisons au total. Ce qui semble être le raisonnement suivi dans les réponses.

Mais voila avec ce raisonnement, on compte 2 fois certaines combinaisons comme CIJM..CIJM comptée une fois pour CIJM en première position et une 2ème fois pour CIJM en 7ème position.
Il faut donc retrancher ces doublons. Dans notre cas ce sont:
CIJMCIJM.., CIJM.CIJM., CIJM..CIJM, .CIJMCIJM.,.CIJM.CIJM,..CIJMCIJM.
Il y en a 6 et pour chacun 26^2 possibilités pour les 2 cases vides.
Je trouve donc comme proba:
(7*26^6-6*26^2)/26^10.

Le cas générique avec K et M est plus compliqué, puisqu'il faut enlever les doublons mais remettre les "triplons" et enlever les "quadruplons", ... raison pour laquelle je ne suis pas allé jusqu'au bout mais une petite somme bien sentie doit donner la réponse.
Ce problème commence à se produire lorsque N>=2M.

 #12 - 28-05-2011 13:03:10

EfCeBa
Administrateur
Enigmes résolues : ∞+1
Messages : 22×32×173

Taper aléatoirement sur une macihne à écrire

Très bonne remarque big_smile Dans la réponse que j'ai proposée certains cas doivent être comptabilisés plusieurs fois et donc ne fonctionne que lorsque N < 2M.

Quelqu'un est motivé pour distinguer les cas ?

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Sujets similaires

Sujet Date Forum
P2T
La machine par PRINCELEROI
27-10-2014 Enigmes Mathématiques
01-04-2012 Enigmes Mathématiques
17-06-2013 Enigmes Mathématiques
P2T
La Machine v2.0 par SabanSuresh
28-10-2014 Enigmes Mathématiques
21-05-2011 Enigmes Mathématiques
P2T
Au moins la moitié ! par Vasimolo
08-01-2013 Enigmes Mathématiques
P2T
Les 1000 lampes par Yannek
16-11-2010 Enigmes Mathématiques
P2T
Bientôt 2012 ! par fix33
13-02-2011 Enigmes Mathématiques
P2T
Couloir par looozer
27-07-2010 Enigmes Mathématiques

Mots clés des moteurs de recherche

Mot clé (occurences)
Taper a la machine a ecrire (7) — Machine a enigme (3) — Taper des devinette (2) — Cijm (2) — Tape devinette (2) — Taper a la machine (1) — Enigme ecrire en quatre lettres (1) — On tape la reponse en tapant la question (1) — Taper sur une machine quand elle ne fonctionne pas (1) — Enigme a ecrire et donne la reponse (1) — Enigme logique tapez reponse (1) — tapi tap devinette combinaison (1) — Une machine a ecrire (1) — Statistiques proba chimpanze machine a ecrire a b c d e (1) — Tape devinette jeux (1) — Machine a ecrire enigmes (1) — Machine a devinette (1) — Machine a ecrire singe (1) — Enigme a taper (1) — Le chifre a b c d e f j ch (1) — J?ai 25 lettres (1) — Alphabet caractere machine a ecrire (1) — Taper une devinete (1) — 123 132 213 231 32 (1) — Ecrire au lieu de taper (1) — Caracteres de lettres de machine a ecrire (1) — Site:fr ecrire une reponse (1) — Les premiers mot a taper a (1) — Machine enigme (1) — Enigme a taper qui donne les reponses (1) — Enigme devinette (1) — Ecrit en tapant (1) — Caracteres d une machine a ecrire (1) — Forum cijm etagere 2012 (1) — Enigme si vous repondez aleatoirement a la question quels (1) — Taper une devinette (1) — Exercice probabilite sur le chimpanze iago (1) — Besoin une machine a taper (1) — Devinette combinaison (1) — Le mot de trois lettres enigme (1) — Devinette machine a ecrire (1) — Ecrire les e en tapant a la machine (1) — Enigme lettres sur machine a calculer (1) — Enigme singe machine a ecrire (1) —

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete