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 - 01-04-2016 19:42:18

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Probabilité d'être interrogé avant un autre (énoncé moddifié)

Ce problème ne fait pas parti des mathématiques pour les nuls parce que je n'ai pas vraiment d'idée de comment traiter encore le problème pour n personnes et que je ne suis pas certain de mes résultats pour des cas simples.

Ce problème m'est inspiré de la manière dont mon professeur de Japonais nous interroge.

Énigme

Un professeur de Japonais interroge ses élèves (tous numéroté différemment de 1 en 1 allant de 1 à n) de la manière suivante:

- Il interroge toujours le 1 en premier
- Ensuite il continu à les interroger dans l'ordre croissant de leur numéro sauf parfois où avec une probabilité p il en interroge un autre qui n'a pas été interrogé. Puis il revient là où il aurait dû continuer.
- A chaque fois qu'un élève est interrogé sans suivre l'ordre croissant normal la probabilité qu'un autre élève soit interrogé au hasard est divisée par deux.
- Et une fois qu'un élève a été interrogé il ne peut plus l'être. (EDIT)
- Il peut faire plusieurs tirages au sort de suite. (EDIT)

En cours de Japonais nous sommes 10. Quel est la probabilité que 10 soit interrogé avant 9 si p=1/2 au départ.

Trop facile pour vous? Pourriez-vous généraliser pour n'importe quelle population d'élève (n) et de p au départ? Et si au lieu de diviser par 2 si on divisait autrement par exemple par 2 puis 3 puis 4 ... ?


Exemple

Il interroge les élèves dans l'ordre suivant : 1 2 3 4 6 5 7 8 10 9 
Il avait 1/2 de choisir 6 plutôt que 4. Et il avait 1/4 de choisir 10 plutôt que 9.
Quand je dis repartir là où il aurait dû continuer cela veut dire dans ce cas qu'il y a 7 après 5 forcément puisque 4 et 6 on déjà été choisi et que 6 l'a été avant 5.

Voilà je vous souhaite une bonne réflexion, et si vous parlez japonais répondez quand même en français lol

Shadock


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
  • |
  • Répondre

#0 Pub

 #2 - 01-04-2016 21:46:16

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Probabilité d'être interrogé avant un autre (énoncé modfiié)

Quand tu dis "il avait 1/2 de choisir 6 plutôt que 4", ce n'est pas plutôt une chance sur 10 ?

Après 1 2 3 4, il a 1 chance sur 2 de choisir 5, et 1 chance sur 10 pour chacun des élèves 6 7 8 9 10 ? Ai-je bien compris ?

 #3 - 01-04-2016 21:50:23

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

probabilité d'êtrz interrogé avant un autre (énoncé modifié)

Le problème c'est que j'ai du mal à formuler mon problème.

Quand il arrive a 4 normalement il doit aller à 5 sauf s'il décide de changer et à ce moment là il le fait avec une probabilité de 1/2.

Donc tant que personne n'a été choisi "au hasard" il y a toujours une chance sur deux que le prochain ne soit pas le suivant de l'ordre des nombres.

Et une fois qu'un élève a été interrogé il ne peut plus l'être j'ai oublié de le préciser ! smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #4 - 01-04-2016 22:03:27

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Probabilité d''être interrogé avant un autre (énoncé modifié)

Je reformule ma question : est-ce que la suite 1 2 3 4 8 5 6 7 10 9 est possible ?

C'est-à-dire, quand ton prof décide de changer après 4, prend-il toujours 6 à la place de 5, ou peut-il prendre 7 8 9 ou 10 ?

 #5 - 01-04-2016 22:56:20

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Probabilité d'être interrogé avant un autre (énnoncé modifié)

Ebichu a écrit:

Je reformule ma question : est-ce que la suite 1 2 3 4 8 5 6 7 10 9 est possible ?

C'est-à-dire, quand ton prof décide de changer après 4, prend-il toujours 6 à la place de 5, ou peut-il prendre 7 8 9 ou 10 ?

Oui oui il peut le faire. J'ai voulu dire ça en disant "élève choisi au hasard" smile
Il pourrait très bien changer après 3 aussi.


On élimine les cas triviaux de 1 et 2 élève(s).


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #6 - 02-04-2016 12:30:00

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

Probabilité d'êtr interrogé avant un autre (énoncé modifié)

Bonjour,
Problème intéressant, mais pas simple.
k = coefficient par lequel on multiple la probabilité après qu'un élève ait été tiré au hasard

La probabilité que l'élève n soit interrogé avant l'élève n-1 est, sauf erreur (le calcul est un peu laborieux) :

Code:

n=3 => P=p
n=4 => P=p*(3-2*p)/2
n=5 => P=p*(11+(2*k-15)*p+6*p*p)/6

J'ai vérifié quelques valeurs par simulation.

Pour n=10, p=k=1/2, j'obtiens par simulation P=37.75 %.

 #7 - 02-04-2016 13:42:06

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Porbabilité d'être interrogé avant un autre (énoncé modifié)

Notons p(n;k) la probabilité qu'avec n élèves, l'élève n soit interrogé avant l'élève n-1, si initialement, la probabilité que le prof ne suive pas l'ordre établi est 1/2^k.

Alors on a la relation : p(n;k) = (1-1/2^k).p(n-1;k) + (1+(n-4).p(n-1;k+1))/((n-2).2^k). Cette relation est valable pour n>=3 et k>=1, en prenant comme conditions initiales : p(2;k)=0 pour tout k>=1.

On rentre ça dans le tableur pour calculer p(10;1) et on obtient environ 0,3785.

 #8 - 02-04-2016 15:32:01

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 3004
Lieu: Fanning Island-?-Lac Tele,Mali

Probabillité d'être interrogé avant un autre (énoncé modifié)

Apres avoir interrogé un eleve au hasasrd, doit il OBLIGATOIREMENT revenir la ou il en été, ou peut il interrogé un autre eleve au hasard avec un probabilité diminué?

Par exemple peut-il faire: 1 2 3 8 7 6 4 10 5 9 ?


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #9 - 02-04-2016 16:43:33

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Probabilité d'être interrogé avaant un autre (énoncé modifié)

dhrm77 a écrit:

Apres avoir interrogé un eleve au hasasrd, doit il OBLIGATOIREMENT revenir la ou il en été, ou peut il interrogé un autre eleve au hasard avec un probabilité diminué?

Par exemple peut-il faire: 1 2 3 8 7 6 4 10 5 9 ?

Non il n'est pas obligé. C'est sur ce point là que j'ai eu du mal à rédiger mon énoncé.

Ebichu et Enigmatus vos valeurs sont différentes de 0.1 smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #10 - 02-04-2016 17:36:49

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

probabilité d'être interrogé avant un auyre (énoncé modifié)

Du coup, je ne suis pas sûr d'avoir bien compris l'énoncé.
1) Je pensais que le prof ne pouvait pas faire 2 tirages au sort de suite. Peux-tu préciser ?
2) Si le prof interroge 1, et fait un tirage au lieu d'interroger 2, choisit-il parmi 3-10 ou 2-10 ?

 #11 - 02-04-2016 18:00:38

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Probabilité d'êter interrogé avant un autre (énoncé modifié)

C'est bon j'ai modifié. A la fin de l'énigme vous aurez l'énoncé complet lol

enigmatus a écrit:

2) Si le prof interroge 1, et fait un tirage au lieu d'interroger 2, choisit-il parmi 3-10 ou 2-10 ?

Il choisit avec une chance sur deux soit 2 soit un élève au hasard (de manière équiprobable) parmi 3-10.


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #12 - 02-04-2016 19:50:55

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

Proabbilité d'être interrogé avant un autre (énoncé modifié)

Bon. J'ai corrigé ma copie en fonction des nouvelles directives.

Code:

n=3 => P=p
n=4 => P=p*(3-2*p)/2
n=5 => P=p*(11+(3*k-15)*p+2*p*p*(3-k*k))/6

Pour n=10, p=k=1/2, j'obtiens par simulation P=37.84 %.

 #13 - 03-04-2016 06:30:19

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

Probabiliité d'être interrogé avant un autre (énoncé modifié)

Je pense avoir la solution exacte. J'ai programmé en python le calcul que j'avais fait à la main pour n=3, 4, 5.

Pour [latex]n=10, p=k=1/2[/latex], j'obtiens [latex]P=5462294224309/14431090114560=0.378509[/latex]

Ajouté :
Voici un tableau en faisant varier p et k (toujours pour n=10)

Code:

     K 0.0    0.1    0.2    0.3    0.4    0.5    0.6    0.7    0.8    0.9    1.0    
P
0.0    0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 
0.1    0.1639 0.1703 0.1763 0.1821 0.1877 0.1931 0.1984 0.2037 0.2089 0.2142 0.2194 
0.2    0.2002 0.2208 0.2393 0.2560 0.2716 0.2864 0.3007 0.3147 0.3286 0.3423 0.3560 
0.3    0.1897 0.2277 0.2593 0.2866 0.3111 0.3338 0.3554 0.3764 0.3970 0.4170 0.4362 
0.4    0.1694 0.2248 0.2677 0.3027 0.3331 0.3608 0.3870 0.4122 0.4365 0.4593 0.4796 
0.5    0.1524 0.2241 0.2753 0.3148 0.3482 0.3785 0.4071 0.4343 0.4598 0.4825 0.5000 
0.6    0.1411 0.2275 0.2841 0.3255 0.3598 0.3912 0.4209 0.4488 0.4740 0.4947 0.5072 
0.7    0.1342 0.2336 0.2931 0.3345 0.3689 0.4007 0.4309 0.4587 0.4829 0.5008 0.5076 
0.8    0.1299 0.2408 0.3013 0.3416 0.3757 0.4079 0.4383 0.4659 0.4887 0.5035 0.5052 
0.9    0.1271 0.2481 0.3080 0.3469 0.3810 0.4137 0.4442 0.4712 0.4925 0.5046 0.5023 
1.0    0.1250 0.2549 0.3133 0.3509 0.3852 0.4184 0.4489 0.4753 0.4952 0.5047 0.5000

 #14 - 03-04-2016 08:56:02

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 307
Lieu: Montargis

Probabilité d'être interrogé avannt un autre (énoncé modifié)

- A chaque fois qu'un élève est interrogé sans suivre l'ordre croissant normal la probabilité qu'un autre élève soit interrogé au hasard est divisée par deux.

Une fois que la proba d'interroger un élève au hasard est divisé par 2,4,.. (après avoir interrogé 1,2,... élèves au hasard à la suite); reste-t-elle à cette valeur (moitié) même s'il recommence à interroger dans l'ordre? Ou la proba se réinitialise à sa valeur de départ dès qu'il recommence à interroger dans l'ordre  (après avoir interrogé un ou des élèves au hasard)?

 #15 - 03-04-2016 21:00:55

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Probabilité d'être interrogé avant un autre (énoncé modifiéé)

La proba n'est pas réinitialisée non smile

Jolis tableau enigmatus big_smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #16 - 03-04-2016 22:43:09

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

probabilité d'être interrogé avant un autre (énpncé modifié)

Voici les résultats pour [latex]n=11,12,13[/latex], avec les temps de calcul approximatifs. Mon programme, un peu bourrin, passe en revue toutes les permutations (du moins celles qui se terminent sur le dernier élève, et ne contiennent pas l'avant-dernier), et ne permet pas d'aller beaucoup plus loin.

Code:

n=11 p=1/2 k=1/2 P=2710463851646939/7388718138654720=0.366838                  30 secondes
n=12 p=1/2 k=1/2 P=2020209797683492381/5674535530486824960=0.356013             5 minutes
n=13 p=1/2 k=1/2 P=221100823549069532257561/639179682154035963494400=0.345913  55 minutes

Édité : Petite précision

 #17 - 04-04-2016 11:00:50

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

Probabilité d'être interrogé avant un aautre (énoncé modifié)

Pour le problème japonais initial, j'ai trouvé que c'était environ une proba de 1/2 pour que le 8 ème choix ce soit l'ordre plutôt que le hasard qui soit choisi.
ça suppose évidemment qu'il ait été nécessaire d'aller jusqu'au 8ème choix, c'est à dire que les 7 choix précédents, hasard ou ordre, ont évité le 9 ou le 10. C'est ce qu'il faut traduire dans le calcul.
Lorsque le hasard est choisi, c'est évidemment 50/50 pour le 9 ou le 10.
Donc, P(10 avant 9), c'est 1/2 sur le hasard, c'est à dire 1/4.
et P(9 avant 10) c'est 1/2 + 1/4 soit 3/4.

La généralisation ne pose pas de problème particulier avec un raisonnement identique, en revanche, il me semble qu'il est nécessaire de faire appel à un tableur ou une routine poour faire le calcul.

 #18 - 04-04-2016 20:14:04

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Probabillité d'être interrogé avant un autre (énoncé modifié)

@enigmatus : je trouve comme toi avec ma relation pour n=11, 12, 13, mais avec un temps de calcul négligeable.

Pour n=40, ça fait 0,2042 environ. Au-delà, ça commence à faire beaucoup d'élèves, pour un cours de japonais...

 #19 - 04-04-2016 21:10:06

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

rPobabilité d'être interrogé avant un autre (énoncé modifié)

@Ebichu
Je n'ai pas compris ta relation de récurrence en #7, mais je l'ai transcrite en python et nous obtenons rigoureusement les mêmes résultats (pour une proba de 1/2 au départ et divisée par 2 à chaque fois). Ton calcul est beaucoup plus rapide (pour n=13, moins de 0.07 seconde pour toi, 55 minutes pour moi).
Avec ta formule, j'obtiens le résultat pour n=20 en moins de 0.1 seconde.

Code:

n=20 P=1572079911772530447407100255227952524832014115521949343174283/5414976651461685427888851233531444842940158969162525310976000=0.290321

Édité : Correction des temps de calcul après amélioration du codage de ta récurrence

 #20 - 04-04-2016 22:14:39

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Probabilité d'être inteerrogé avant un autre (énoncé modifié)

Voui, mon message était peut-être un peu sibyllin, je vais rajouter quelques explications.

On note p(n;k) la probabilité qu'avec n élèves, l'élève n soit interrogé avant l'élève (n-1), si initialement, la probabilité que le prof ne suive pas l'ordre établi est 1/2^k : par exemple, p(10;1) est la proba recherchée par shadock, car il y a 10 élèves, et initialement, une proba 1/2^1 = 1/2 de choisir un autre élève. Autre exemple, p(5;3), c'est avec 5 élèves, et initialement, une proba 1/2^3 = 1/8 de choisir un autre élève.

Maintenant, on explique comment calculer p(n;k). On a n élèves, et on commence avec le numéro 1. Ensuite, le prof va choisir le numéro 2 avec une probabilité (1-1/2^k) : dans ce cas, on retombe sur exactement le même problème, sauf qu'il n'y a plus que (n-1) élèves (les numéros 2, 3, ..., n). Ce qui explique le premier terme : (1-1/2^k).p(n-1;k).

L'autre possibilité est que le prof décide de choisir un autre élève, ce qui se produit avec la proba 1/2^k. Il y a (n-2) autres élèves (les numéros 3, ..., n), donc chacun est choisi avec la proba 1/((n-2).2^k). Il faut distinguer 3 cas :
* si l'élève choisi est le numéro n, alors on est sûr que l'élève n sera interrogé avant l'élève (n-1) : proba 1.
* si l'élève choisi est le numéro (n-1), alors on est sûr que l'élève n ne sera pas interrogé avant l'élève (n-1) : proba 0.
* sinon, pour chacun des élèves numéros 3 à (n-2) (soit (n-4) élèves au total), on retombe sur exactement le même problème, sauf qu'il n'y a plus que (n-1) élèves, et que l'on incrémente k (par exemple, on passe de 1/8 à 1/16) : proba p(n-1;k+1) pour ces (n-4) élèves.
Finalement, le deuxième terme est (1+(n-4).p(n-1;k+1))/((n-2).2^k).

En tenant compte de ces deux cas, on obtient : p(n;k) = (1-1/2^k).p(n-1;k) + (1+(n-4).p(n-1;k+1))/((n-2).2^k). Cette relation fonctionne dès n=3. Pour n=2, c'est trop court pour qu'il y ait une inversion, donc p(2;k)=0 pour tout k.

Est-ce plus clair ?

 #21 - 05-04-2016 07:00:20

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

probabilité d'être intzrrogé avant un autre (énoncé modifié)

Merci Ebichu. Tes explications en #20 sont lumineuses, et bravo pour cette formule qui permet un calcul rapide.

Ajouté :
19 secondes pour n=100 (P=0.1145)
Ta formule peut facilement s'adapter si la probabilité initiale et le coefficient de réduction sont différents.

 #22 - 05-04-2016 18:53:33

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Probabilité d'être interrogé avant un autre (noncé modifié)

Merci à tous les participants et bravo à Ebichu pour son explication très claire.

Du coup maintenant on va pouvoir calculer des probabilités conditionnelles du genre, la proba que 9 soit interrogé avant 10 sachant que 7 n'a pas été interrogé avant 5 roll


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
 

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 : Pim, Pam et ?

Mots clés des moteurs de recherche

Mot clé (occurences)

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