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 - 08-07-2015 07:53:07

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

gâtrau 100

Il n'a jamais été question de ligne diagonale , à postériori je comprends mieux la formule 1/50+1/50-1/(50*49)  smile

On cherche la probabilité qu'une ligne coupe toutes les autres .

Vasimolo

#0 Pub

 #27 - 08-07-2015 11:28:09

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

âteau 100

Pour ce cas n° 3, je n'ai pas trouvé autre chose que la méthode exhaustive, dont le temps de calcul augmente très vite avec N.
Voici ce que j'obtiens jusqu'à N=12 :

Code:

N=   1 ok=        1 ko=         0 tot=         1  ok/tot= 100.000 %
N=   2 ok=        1 ko=         1 tot=         2  ok/tot=  50.000 %
N=   3 ok=        3 ko=         3 tot=         6  ok/tot=  50.000 %
N=   4 ok=       10 ko=        14 tot=        24  ok/tot=  41.667 %
N=   5 ok=       43 ko=        77 tot=       120  ok/tot=  35.833 %
N=   6 ok=      223 ko=       497 tot=       720  ok/tot=  30.972 %
N=   7 ok=     1364 ko=      3676 tot=      5040  ok/tot=  27.063 %
N=   8 ok=     9643 ko=     30677 tot=     40320  ok/tot=  23.916 %
N=   9 ok=    77545 ko=    285335 tot=    362880  ok/tot=  21.369 %
N=  10 ok=   699954 ko=   2928846 tot=   3628800  ok/tot=  19.289 %
N=  11 ok=  7013079 ko=  32903721 tot=  39916800  ok/tot=  17.569 %
N=  12 ok= 77261803 ko= 401739797 tot= 479001600  ok/tot=  16.130 %

 #28 - 09-07-2015 18:52:58

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

gâyeau 100

J'ai fait une petite recherche sur l'OEIS avec les premières valeurs fournies par Enigmatus pour le problème initial http://oeis.org/A006932 et la variante de Gwen http://oeis.org/A003319 . Je crois qu'on aura du mal à trouver une expression simple de la probabilité cherchée .

Vasimolo

 #29 - 10-07-2015 18:36:06

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

Gâetau 100

Pour la variante de Gwen, à savoir : quelle est la proportion de configurations totalement imbriquées ? Totalement imbriquées pris ici dans le sens: en partant du 1er segment, on peut arriver au derrnier par une ligne brisée empruntant des portions des autres segments.
Tout d'abord, il est à remarquer que si la configuration n'est pas conforme au critère, alors c'est qu'elle est formée d'au moins 2 configurations imbriquées distinctes. Par exemple: 1/2;2/1;3/3;
1/2;2/1 est la 1ère config imbriquée, 3/3 est la seconde. Si on appelle Rn (réussite) une config imbriquée de n points, alors Rn=n!- somme des (R(n-1)+R(n-2)+..R1). 

R1=1
R2=1
R3=3!-aR2-bR1
Pour trouver a et b, on est amené à faire une partition ordonnée de 3.
3=2+1=1+1+1
2+1: 2*R2*R1 (le 2 vient des permutations 2/1)=2
1+1+1: R1*R1*R1=1
R3=3!-2-2-1=3

R4=4!-aR3-bR2-cR1
partition de 4
4=3+1=2+2=2+1+1=1+1+1+1
3+1:2R3*R1=6
2+2=R2*R2=1
2+1+1=3*R2*R1*R1=3
1+1+1+1=R1*R1*R1*R1=1
R4=24-6-1-3-1=13

etc...

Bien sûr, on calcule ici le nombre de combis réussite, et avant d'arriver à R50, on va être vite confronté à un problème de taille et de temps de calcul. On peut cependant décrire d'abord la tendance, en observant les résultats Rn/n!:
R3/3!=0,5
R4/4!=0.54..
R5/5!=0.59..
R6/6!=0.64..
R7/7!=0.68..
R8/8!=0.72..
R9/9!=0.75..

Rn semble tendre vers 1 quand n grandit.

Calcul théorique approximatif de R50
R50=50!-aR49-bR48-cR47.....
a=2
b=5 (partition 48+2 et 48+1+1)
c=16 détail:
47+3:2*R3*R47=6*R47
47+2+1=6*R47
47+1+1+1=4*R47

Remarquons que les coeff a, b, c,.. deviennent stables quel que soit n supérieur à une certaine valeur.

R50=50!-2*R49-5*R48-16*R47-....
On suppose Rn/n!=k à peu près identique pour 47 à 50.
k*50!=50!-2k*49!-5k*48!-16k*47!-....
k*50!=50!-2k*50!/50-5k*50!/(50*49) (on peut négliger R47et les suivants)
k=1-2k/50-5k/(50*49)
k=0.95 environ.

La convergence de k n'est pas différente de 1.
Calculons la convergence pour un n pour lequel k est stable.
Rn=n!-2*R(n-1)-5*R(n-2)-16*R(n-3)....
Rn=k*n!=n!-2k*n!/n-5k*n!/(n(n-1))-16k*n!(n(n-1)(n-2)).....
k=1-2k/n-5k/(n(n-1)-16k/n(n-1)(n-2)
k(1+2/n+5/n(n-1)+16/(n(n-1)(n-2)...)=1
k(1+2/n+5/n²+16/n^3)....)=1 pour n grand

On voit qu'on peut trouver des valeurs de n plus grandes pour faire augmenter k. Pour n très grand, on peut estimer la valeur de k:
k=1/(1+2/n)=1-2/n

 

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 : 

Si il y a 78 pommes et que vous en prenez 43, combien en avez-vous ?

Sujets similaires

Sujet Date Forum
23-09-2012 Enigmes Mathématiques
P2T
Gâteau 50 par Vasimolo
23-12-2011 Enigmes Mathématiques
30-09-2009 Enigmes Mathématiques
P2T
Gâteau 56 par Vasimolo
16-11-2012 Enigmes Mathématiques
P2T
01-05-2014 Enigmes Mathématiques
P2T
Gâteau 13 par Vasimolo
11-07-2010 Enigmes Mathématiques
P2T
Gâteau 61 par Vasimolo
08-08-2013 Enigmes Mathématiques
P2T
Gâteau 72 par Vasimolo
22-02-2014 Enigmes Mathématiques
P2T
Gâteau 1 par Vasimolo
05-04-2010 Enigmes Mathématiques
P2T
Gâteau 96 par Vasimolo
06-04-2015 Enigmes Mathématiques

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