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 - 08-02-2015 16:32:12

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

Piocher dse jetons, oui, mais dans l'ordre croissant !

Un sac contient 1000 jetons numérotés de 1 à 1000. Vous piochez des jetons au hasard dans le sac, un par un, et commencez à les étaler devant vous. Une seule règle : les jetons piochés doivent l'être dans l'ordre croissant. Si le dernier jeton pioché est plus petit que l'un des jetons précédemment piochés, vous êtes obligés de tous les remettre dans le sac et recommencer depuis le début ! Le but du jeu est de réussir à piocher 10 jetons dans l'ordre croissant. En moyenne, au bout de combien de jetons piochés allez-vous y parvenir ?

  • |
  • Répondre

#0 Pub

 #2 - 08-02-2015 21:33:49

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

Piocher des jetons, oui, mais dans l'ordre croisant !

Soient N le nombre de boules dans le sac, K le nombre de tirages successifs à réaliser et M le nombre moyen de tirages.

En raisonnant pour K=2, 3 ou 4, je me suis rendu compte que M ne dépend pas de N mais seulement de K. Seule condition évidente: N>=K.

On se place dans le cas N=K; chercher M revient à trouver le nombre moyen de fois pour tirer dans l'ordre de 1 à N les N jetons du sac.

* Tirage de 1: on y arrive en moyenne après K fois,
* Tirage de 1 puis 2: on y arrive en moyenne après K*(K-1) fois,
* ...
* Tirage de 1 à x dans l'ordre: on y arrive en moyenne après K!/(K-x)! fois,
* ...
* Tirage de 1 à K dans l'ordre: on y arrive en moyenne après K!/(K-K)!=K! fois.

M est la somme de toutes les tentatives soit:

M=Somme(x=1 à x=K)de(K!/(K-x)!)

Pour K=10, on a: M=Somme(x=1 à x=10)de(10!/(10-x)!) soit

M = 9 864 100.

Quelques M pour les 6 premières valeurs de K:
M=1 pour K=1
M=4 pour K=2
M=15 pour K=3
M=64 pour K=4
M=325 pour K=5
M=1 956 pour K=6.

 #3 - 09-02-2015 00:05:07

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

Piocher des jetons, oui, mais dans l'ordre croissnat !

Oui bravo kossi, c'est la bonne formule !

Est-ce que tu vois pourquoi ce dont tu t'es rendu compte est vrai ?

EDIT : En fait, je ne comprends rien à ton raisonnement, pourrais-tu expliquer un peu d'où sortent tes formules, et pourquoi tu sommes à la fin ?

 #4 - 09-02-2015 12:03:14

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

Piocher des jetons, oui, mais dans l'rodre croissant !

Sans en être vraiment certain, j'aurais dit:
1+1)2+1)3+1)4+1)5+1)6+1)7+1)8+1)9+1)10 soit près de 10 millions.

 #5 - 09-02-2015 14:31:36

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

Piocher des jetons, oui, mais dans l'ordre croissnt !

@nodgim : Oui, bravo, c'est la bonne formule !

Enfin bon, il faudrait quand même ouvrir les parenthèses que tu y fermes !

Puisque tu dis ne pas être certain de toi, il serait bon que tu essayes de justifier rigoureusement ladite formule.

 #6 - 09-02-2015 16:44:46

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

Piocher des jetons, oui, mais dans l'ordre croissant

En fait c'est facile à comprendre: Pour une combinaison de 10 nombres, il y a une chance sur 10! pour qu'elle soit dans le bon ordre. Cependant, il ne faut pas oublier qu'on remise tout à chaque fois, alors il faut corriger cette expression.
Quand on a réussi à obtenir k nombres dans l'ordre, il existe k+1 combis de k+1 nombres dont les k nombres sont dans l'ordre: le nombre supplémentaire a k+1 positions dans la combi de k nombres. C'est pourquoi quand on ajoute 1 nombre à une combi réussie de k nombres, on devra le faire k+1 fois.

Cependant, en passant par les intégrales, je ne retrouve pas ce résultat, je ne sais pas pourquoi. D'où mon scepticisme.

 #7 - 09-02-2015 17:33:47

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

piocher dzs jetons, oui, mais dans l'ordre croissant !

@nodgim : ta façon de t'exprimer est un peu confuse pour moi, je ne sais pas trop si tu as vraiment compris ce qui se passe. Pourquoi parles-tu d'intégrales à la fin ? Ce n'est pas vraiment l'outil adapté à la situation...

 #8 - 09-02-2015 18:10:14

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

Piocher des jetons, oui, mai sdans l'ordre croissant !

Mon raisonnement s'est basé sur 2 concepts:
1-) le nombre moyen pour réussir un événement de probabilité p est 1/p
2-) pour tirer par ordre de 1 à K dans l'ordre croisant, il faut avoir tiré :
* 1 (p=1/K donc K tentatives en moyenne),
* 1 puis 2 (K jeton, pour tirer 1, p_1=1/K. Il reste K-1 jetons, pour tirer 2, p_2=1/(K-1) ==> p=p_1*p_2==1/(K*(K-1)) donc K*(K-1) tentatives en moyenne),
...
ainsi de suite jusqu'à avoir le tirage complet.

La somme se justifie par le fait qu'on ne peut pas atteindre une étape supérieure sans avoir réussi les étapes antérieures. Le nombre moyen de tirage pour atteindre la dernière étape (1 à K) est la somme de toutes les tentatives y compris celles pour la réussite des étapes antérieures.

Justification du fait que M est indépendant de N (nombre de jetons dans le sac.

Pour tirer 2 nombre x et y tels que y>x dans un sac à N jetons, on a N-1 possibilités. La probabilité p de ce tirage est la somme des probabilités de toutes possibilités:
* possibilité 1: x=1. p_x=1/N et p_y=(N-1)/(N-1) car y peut prendre toutes les valeurs sauf 1.
p_1=p_x*p_y=(1/N)*((N-1)/(N-1))

* possibilité 2: x=2. p_x=1/N et p_y=(N-2)/(N-1); y prend toutes les valeurs sauf 1 et 2.
p_2=p_x*p_y=(1/N)*((N-2)/(N-1))

* ...

* possibilité m: x=m. p_x=1/N et p_y=(N-m)/(N-1); y prend toutes les valeurs > à m or il reste N-1 jetons dans le sac.
p_2=p_x*p_y=(1/N)*((N-m)/(N-1))=(1/(N*(N-1))*(N-m)

* ...

* possibilité N-1: n=N-1. p_x=1/N et p_y=1/(N-1); y peut prendre seulement la valeur N.
p_N-1=p_x*p_y=(1/N)*(1/(N-1))

p=somme des p_m; m allant de 1 à N-1=(1/(N*(N-1))*[somme des N - somme des m] (il y a N sommé N-1 fois et somme de 1 à N-1)

p=(1/(N*(N-1))*[N*(N-1)-N*(N-1)/2] =(1/(N*(N-1))*N*(N-1)*[1-1/2]=1/2 d'où l'indépendance de p. CQFD

Il y a sûrement un moyen plus rapidement smile

 #9 - 09-02-2015 20:42:28

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

Piocher des jetons, oui, mais dans l'ordre crroissant !

@kossi :

pour les 2 concepts exposés :
1-) Ok
2-) ça ne tient pas debout selon moi, même si le résultat est bon

pour l'indépendance :
il y a beaucoup plus simple, sans aucun calcul

 #10 - 09-02-2015 21:56:14

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

Piocher des jetons, oui, mais dans 'ordre croissant !

Bonsoir,
Le résultat ne dépend pas du nombre N de jetons dans le sac (≥10).
Si on appelle m le nombre moyens de jetons tirés dans les séries de 10 qui échouent, le nombre moyen de jetons tirés sera :

Code:

N + m * (N! - 1)

m calculé par ordinateur, en passant en revue les permutations de N éléments

Code:

m = 9864090/3628799

On obtient le nombre moyen de jetons tirés : 9864100

 #11 - 09-02-2015 22:50:59

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

Piocher des jjetons, oui, mais dans l'ordre croissant !

Oui, bravo enigmatus. Saurais-tu justifier ta première phrase sur l'indépendance. Saurais-tu calculer simplement la réponse sans avoir à faire un programme qui passe en revue toutes les possibilités ?

 #12 - 09-02-2015 23:10:24

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

piocher des jetons, oui, mais dans l'ordre ceoissant !

titoufred #11 a écrit:

Saurais-tu justifier ta première phrase sur l'indépendance.

Quand on compare les jetons tirés, seul compte l'ordre de leurs numéros. Qu'ils soient numérotés de 1 à 10, ou de 10 nombres différents choisis parmi 1000 ou 1000000, cela ne change rien.

Saurais-tu calculer simplement la réponse sans avoir à faire un programme qui passe en revue toutes les possibilités ?

Non, je n'ai pas trouvé…

Voici un programme en python qui fait le calcul :

Code:

#!/usr/bin/env python

import sys
from itertools import permutations

N=int(sys.argv[1])
n=0
for jetons in permutations(range(N)) :
   j0=-1
   for j in jetons :
      n+=1
      if j<j0 : break
      j0=j

print("N=%d Resul=%d"%(N,n))

à lancer ainsi (du moins sous Linux)

Code:

./le_script.py 10

Correction : Orthographe

 #13 - 10-02-2015 11:10:55

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

Piocher des jetons, oui, mais das l'ordre croissant !

Bon, j'ai réconcilié le calcul avec l'intuition.

La proba d'obtenir une suite de k réels ordonnés dans un intervalle [0,1] est définie par l'intégrale I():
P(k+1)=I pour x=0 à 1 ((1-x)x^(k-1)/(k-1)!)
x est la position du plus grand réel de la suite de k réels ordonnés. le x^(k-1)/(k-1)! est le nombre de suites de k réels ordonnés pour cet x. (1-x) est bien sûr la proba de piocher un réel>x.

P(k+1)=I(x^(k-1)/(k-1)!-x^k/(k-1)!
=1/(k-1)!*I(x^(k-1)-x^k)
=1/(k-1)!*[x^k/k-x^(k+1)/(k+1)] de 0 à 1
=1/(k-1)!*(1/k-1/(k+1))
=1/(k+1)!

Donc pour passer d'une suite ordonnée de k réels à une suite ordonnée de (k+1) réels, il faudra bien en moyenne tenter k+1 fois une suite de k réels.
Ensuite, la formule vraie prend en compte bien sûr le fait qu'on doit tout recommencer depuis le début.

 #14 - 10-02-2015 11:14:06

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

piocher des jetons, oui, mais dans l'ordre ctoissant !

Ah ! au fait j'allais oublier: et pour optimiser tout ça ? J'ai déja une solution avec moins de 9000 jetons: on prend les n°1 à 9 + 1 jeton. On peut sans doute faire beaucoup mieux, mais pour l'instant je n'ai pas la solution....

 #15 - 11-02-2015 17:30:50

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

piocher des jetons, oui, mais dans l'ordre croissany !

Voilà, vous pouvez à présent découvrir les bonnes réponses données par kossi, nodgim et enigmatus. Faites donc savoir si leurs explications vous convainquent.

 #16 - 11-02-2015 18:38:00

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

Piocher des jeton,s oui, mais dans l'ordre croissant !

J'ai laissé entendre qu'avec une stratégie simple, il était possible d'obtenir la suite ordonnée avec 4500 tirages environ en moyenne. Pouvez vous dire mieux ?

 #17 - 12-02-2015 22:00:49

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

Piocher des jetons, ui, mais dans l'ordre croissant !

Avant de s'attaquer à un prolongement de l'énigme, il faudrait déjà répondre à l'énigme initiale ! Personne ne donne de raisonnement correct et complet selon moi.

 

Réponse rapide

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

Répondez (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 20ème, en quelle position êtes-vous ?

Sujets similaires

Mots clés des moteurs de recherche

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