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

shadock · #1

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

Shadock

Ebichu · #2

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 ?

shadock · #3

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 !

Ebichu · #4

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 ?

shadock · #5

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"
Il pourrait très bien changer après 3 aussi.

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

enigmatus · #6

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 %.

Ebichu · #7

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.

dhrm77 · #8

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 ?

shadock · #9

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

enigmatus · #10

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 ?

shadock · #11

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

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.

enigmatus · #12

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 %.

enigmatus · #13

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

kossi_tg · #14

- 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)?

shadock · #15

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

Jolis tableau enigmatus

enigmatus · #16

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

nodgim · #17

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.

Ebichu · #18

@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...

enigmatus · #19

@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

Ebichu · #20

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 ?

enigmatus · #21

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.

shadock · #22

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

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 01-04-2016 19:42:18

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

#0 Pub

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

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

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

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

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

probabilité s'être interrogé avant un autre (énoncé modifié)

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

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

Ebichu a écrit:

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

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

Code:

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

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

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

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

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

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

dhrm77 a écrit:

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

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

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

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

enigmatus a écrit:

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

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

Code:

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

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

Code:

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

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

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

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

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

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

Code:

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

probabilité d'être interrogé avant un autre (énoncé lodifié)

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

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

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

probabilité d'être interrogé avant un autre (énoncé modigié)

Code:

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

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

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

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

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

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

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums