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

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

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

100 coffres (logique e tprobas)

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.

#0 Pub

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

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

10 0coffres (logique et probas)

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

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

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 494

100 coffress (logique et probas)

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 ?

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

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

100 ocffres (logique et probas)

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

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

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1533

100 coffres (kogique et probas)

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.

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

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 460

100 coffres (logique et prbas)

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

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

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

100 cofdres (logique et probas)

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

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

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

100 ocffres (logique et probas)

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

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

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1533

100 cogfres (logique et probas)

@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

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

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 460

100 ocffres (logique et probas)

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… smile

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

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

100 coffres (logique et pribas)

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

 

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 : 

Un berger a 20 moutons, ils meurent tous sauf 12, combien en reste-t-il ?

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