Enigme 100 coffres (logique et probas) 2/2 @ Prise2Tete

nodgim · #26

La convergence est obligatoire: le ratio est compris entre 1 et 1/2 (ou alors j'ai loupé quelque chose). En effet, on ne peut que couper en 2 la plus longue chaine, les autres plus petites étant inchangées. Trouver la limite de ce ratio,c'est un peu trouver la proportion des grandes boucles (>= n/2) dans toutes les configs possibles.

nodgim · #27

Sinon, je ne comprends ce 3,4: est ce l'inverse du ratio ?

Ebichu · #28

Je prends le train en marche ; avec la fonction f(n)=3488580*(1-1/n), on trouve une bonne approximation de cette suite.

Sinon une question que je me posais : quelqu'un a-t-il une démonstration du fait que la stratégie exposée est la meilleure possible ?

nodgim · #29

@ Ebichu: aucune. Tu as trouvé mieux ?
Sinon, ton commentaire ne m'a pas éclairé sur le ratio, compris entre 1 et 1/2, je dois être bouché là....

Ce qui ne laisse pas de me surprendre, après coup, et au delà d'une 1ère réaction un peu rapide, comme une apparente évidence trop tôt admise, est ce (n+1)/2 qui est le nombre moyen de coffres ouverts avec la méthode du chaînage décrite ici. Suivre la méthode du chaînage ne fait rien gagner par rapport au pur hasard. J'admets le résultat, sans plus.

scarta · #30

oui, c'est n/moyenne pour n.
En gros, je dois ouvrir un coffre tous les combien pour finir en moyenne.

Par contre,
Trouver la limite de ce ratio,c'est un peu trouver la proportion des grandes boucles (>= n/2) dans toutes les configs possibles.>
Pas tout à fait d'accord. Toutes les configurations sont améliorables à l'exception d'une et une seule.

Pour le (n+1)/2, on va faire simple.
Probabilité d'ouvrir le bon coffre du 1er coup: 1/n
Probabilité d'ouvrir le bon coffre du 2ème coup: 1/n
etc...
Probabilité d'ouvrir le bon coffre du n-ième coup: 1/n
Espérance: n*(n+1)/2 / n = (n+1)/2

Avoir une "stratégie" particulière, tout seul, ne t'avancera à rien...

C'est comme le problème classique suivant
"Dans un pays, les gens arrêtent d'avoir des enfants dès qu'ils ont un garçon, et continuent d'en avoir tant qu'ils n'ont que des filles. Quelle est la proportion fille/garçon de ce pays ?"
On peux faire les calculs qu'on veut. On trouvera 50-50.
Ou alors, sans calcul, on peut dire: "s'il était possible d'avoir autre chose que 50-50, alors je vais au casino jouer à la roulette, en jouant noir jusqu'à ce que rouge sort", qui est un énoncé complètement identique; et en déduire de là que le résultat est 50-50.

enigmatus · #31

@scarta :
Après avoir amélioré mon algorithme, j'ai pu aller jusqu'à 100 coffres, mais à une allure d'escargot par rapport à ton programme. Voici les valeurs correspondant à ce que tu présentes en #24 et #25.
Mon script est en python3, et j'utilise le module fractions.Fraction pour traiter les nombres rationnels sans limitation sur la longueur des entiers.

Code:

  1 1.0                  (    0.00 secondes )
  2 2.0                  (    0.00 secondes )
  3 2.4545454545454546   (    0.00 secondes )
  4 2.704225352112676    (    0.00 secondes )
  5 2.824858757062147    (    0.00 secondes )
  6 2.931463469803212    (    0.00 secondes )
  7 3.005769090333731    (    0.00 secondes )
  8 3.0662398494257217   (    0.00 secondes )
  9 3.1095280159531984   (    0.00 secondes )
 10 3.1479778068258617   (    0.00 secondes )
 11 3.1773880249494506   (    0.00 secondes )
 12 3.2034652294489665   (    0.00 secondes )
 13 3.224174448356042    (    0.00 secondes )
 14 3.243164647262605    (    0.00 secondes )
 15 3.2589702492613126   (    0.00 secondes )
 16 3.2734717592130185   (    0.00 secondes )
 17 3.285568625989652    (    0.01 secondes )
 18 3.2969336371529874   (    0.01 secondes )
 19 3.306747282732798    (    0.01 secondes )
 20 3.315902216041585    (    0.01 secondes )
 21 3.3238580637081188   (    0.02 secondes )
 22 3.331410638091849    (    0.02 secondes )
 23 3.3380723658995826   (    0.03 secondes )
 24 3.344387313163916    (    0.04 secondes )
 25 3.350002022643927    (    0.04 secondes )
 26 3.355365485823435    (    0.05 secondes )
 27 3.360198938753125    (    0.07 secondes )
 28 3.3648179451399463   (    0.08 secondes )
 29 3.368983365157019    (    0.11 secondes )
 30 3.3729943941700222   (    0.13 secondes )
 31 3.3766567180648543   (    0.17 secondes )
 32 3.3801738938276054   (    0.19 secondes )
 33 3.3833931165407285   (    0.25 secondes )
 34 3.386506356260294    (    0.30 secondes )
 35 3.389373671131792    (    0.42 secondes )
 36 3.3921443858440226   (    0.49 secondes )
 37 3.394704919278514    (    0.58 secondes )
 38 3.3971875008926133   (    0.73 secondes )
 39 3.399496416311834    (    0.88 secondes )
 40 3.40173562599647     (    1.02 secondes )
 41 3.4038188837772734   (    1.27 secondes )
 42 3.4058466906219707   (    1.69 secondes )
 43 3.4077451469578306   (    1.93 secondes )
 44 3.409590382968944    (    2.27 secondes )
 45 3.4113200846110203   (    2.65 secondes )
 46 3.41300760437351     (    3.09 secondes )
 47 3.4145949375935443   (    3.52 secondes )
 48 3.4161428497002384   (    4.45 secondes )
 49 3.4176015828443114   (    5.11 secondes )
 50 3.419026714894549    (    6.05 secondes )
 51 3.4203746817403076   (    7.07 secondes )
 52 3.4216918101158837   (    8.96 secondes )
 53 3.4229378643474804   (   10.53 secondes )
 54 3.424158053304416    (   13.22 secondes )
 55 3.425316787302461    (   13.95 secondes )
 56 3.426450446160323    (   16.63 secondes )
 57 3.4275278341727584   (   19.93 secondes )
 58 3.4285843617857568   (   23.02 secondes )
 59 3.4295906339365563   (   26.89 secondes )
 60 3.4305771160710914   (   31.60 secondes )
 61 3.431517780623103    (   37.26 secondes )
 62 3.4324410268170262   (   43.26 secondes )
 63 3.433323504517306    (   52.55 secondes )
 64 3.434189739952301    (   66.16 secondes )
 65 3.4350178302230168   (   72.80 secondes )
 66 3.4358318370247765   (   84.64 secondes )
 67 3.436611972061118    (   96.69 secondes )
 68 3.4373783647586187   (  114.67 secondes )
 69 3.4381132447377847   (  127.96 secondes )
 70 3.4388363251086083   (  156.25 secondes )
 71 3.439530715677878    (  181.81 secondes )
 72 3.4402138085311966   (  197.33 secondes )
 73 3.440870329908339    (  238.21 secondes )
 74 3.441516690656764    (  263.80 secondes )
 75 3.4421389534400326   (  319.16 secondes )
 76 3.4427516351938454   (  348.00 secondes )
 77 3.4433415279239257   (  403.34 secondes )
 78 3.4439229237778433   (  476.34 secondes )
 79 3.444483710241104    (  542.93 secondes )
 80 3.445036171191873    (  667.98 secondes )
 81 3.445569245177033    (  696.81 secondes )
 82 3.446095008779233    (  798.92 secondes )
 83 3.4466028785249714   (  918.64 secondes )
 84 3.4471037018899486   ( 1096.27 secondes )
 85 3.447587766064386    ( 1314.56 secondes )
 86 3.4480653956790848   ( 1547.40 secondes )
 87 3.4485276178528244   ( 1653.00 secondes )
 88 3.448983724215911    ( 1943.11 secondes )
 89 3.4494251471424144   ( 1985.91 secondes )
 90 3.4498610561259775   ( 2315.84 secondes )
 91 3.4502835059965187   ( 2836.65 secondes )
 92 3.450700536549524    ( 3311.69 secondes )
 93 3.4511048030843923   ( 3471.86 secondes )
 94 3.4515042313878253   ( 4116.79 secondes )
 95 3.4518917583332613   ( 4651.83 secondes )
 96 3.4522745994098116   ( 5434.97 secondes )
 97 3.45264620064046     ( 5960.35 secondes )
 98 3.453013473514602    ( 6570.08 secondes )
 99 3.4533703056819425   ( 7693.38 secondes )
100 3.453722998420917    ( 9052.00 secondes )

nodgim · #32

@Scarta : Je me suis fait mal comprendre.

Prenons l'exemple d'une config 2 boucles de 50 coffres. On ne peut, avec un seul changement, n'en couper qu'une seule et obtenir 3 boucles: 25,25,50.
Avant changement L = 50
Après changement L = (25² + 25² + 50²) / 100 = 37,5
Ratio : 37,5 / 50 = 0,75.
C'est le plus mauvais ratio, le plus proche de 1, celui qui améliore le moins.

Pour en revenir au fait que la méthode de recherche par chaînage est (n+1)/2 :
J'ai bien compris qu'elle est égale à celle qu'on aurait si on démarrait la recherche soit au hasard ou soit par exemple en explorons les coffres dans l'ordre de 1 à 100. Cependant, ce sont les résultats que tu as obtenus par calcul qui te le disent, ce n'est pas une preuve (même si je suis convaincu que c'est vrai). On aurait pu imaginer que suivre la boucle à partir du coffre numéroté comme la somme recherchée avait un petit avantage sur le hasard. Or non. C'est cet aspect là qui m'échappe encore....

nodgim · #33

Bon, le ratio est donc environ 0,578...
Je me demandais si ça pouvait correspondre à un nombre connu, en relation avec e ou Pi, mais là je vois pas....

scarta · #34

@enigmatus: j'utilise uniquement des entiers, pas des fractions (y'a que le numérateur qui m'intéresse, avec comme dénominateur n.n!)
Du coup, je sais pas ce que fait ta librairie Python mais un petit PGCD qui traîne et te ralentit ne me surprendrait pas outre mesure.

@nodgim
Justement. Sans indice supplémentaire tu ne peux pas faire mieux que le hasard.
Partir sur une chaîne, après permutation, t'assure une fin en 50 coups max.
Partir sur une chaîne sans aucune permutation c'est du hasard pur. La longueur de ta chaîne peut être 100, 99,...

De manière plus mathématique : quelle est la probabilité d'être dans une chaîne de longueur k quand on a n éléments ?
k parmi n ==> Cn,k
qu'on réordonne en cycle ==> (k-1)!
et les autres comme ça vient ==> (n-k)!
encore faut-il tomber sur ces k là ==> k/n
Total: n!/(k!.(n-k)!) (k-1)! (n-k)! k/n = (n-1)! cas sur un total de n!
Conclusion : chaîne ou pas, la probabilité de trouver en k essais est de 1/n
J'espère que ça passe mieux comme ça

enigmatus · #35

scarta a écrit:
Du coup, je sais pas ce que fait ta librairie Python mais un petit PGCD qui traîne et te ralentit ne me surprendrait pas outre mesure.

Je fais tous les calculs sur des entiers, et ne fais la division qu'à la fin, pour obtenir la fraction exacte simplifiée. Ça marche, mais très doucement…

nodgim · #36

D'accord, Scarta. C'est ce que j'attendais !

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	[+]

#26 - 31-10-2017 09:32:21

100 coffres (logique et porbas)

#0 Pub

#27 - 31-10-2017 09:37:15

100 cofgres (logique et probas)

#28 - 31-10-2017 10:03:02

100 coffres (logique et rpobas)

#29 - 31-10-2017 11:04:55

1000 coffres (logique et probas)

#30 - 31-10-2017 12:50:42

100 coffres (logoque et probas)

#31 - 31-10-2017 17:21:01

100 coffres (logiquue et probas)

Code:

#32 - 31-10-2017 17:55:57

100 coffres (logiique et probas)

#33 - 31-10-2017 18:19:40

100 coffres (logique er probas)

#34 - 31-10-2017 22:42:58

010 coffres (logique et probas)

#35 - 01-11-2017 08:07:22

1000 coffres (logique et probas)

scarta a écrit:

#36 - 01-11-2017 08:18:02

100 cffres (logique et probas)

Réponse rapide

Sujets similaires

Pied de page des forums