Enigme Beghin Say 2/2 @ Prise2Tete

golgot59 · #26

Lol, je ne m'en sors pas ! Et pour cause, je pense que ton argument démontre que c'est impossible.
Pour le moment je suis parti sur un programme avec une ossature différente qui utilise des listes, mais je code très mal et je me perd un peu.

Je continue d'y réfléchir...

EDIT : Au fait, je n'ai pas compris ton bouclage, les quantités de sucres entiers sont différentes, du coup je ne vois pas comment tu peux boucler.

caduk · #27

Ce qu'il faut calculer, c'est f(a,b) = a/(a+b) f(a-1, b+1) + b/(a+b) f(a, b-1)
En initialisant f(1,0) = 1, f(0,2) = 0 si on veut la probabilité qu'il reste un sucre entier, et f(0,2) = 1, f(1,0) = 0 si on veut la probabilité qu'il reste deux demi-sucres. J'ai essayé de trouver une expression close, mais dès que a >= 2, on a des sommes harmoniques qui apparaissent, donc il n'y a probablement pas de formule close. Il faudrait essayer de trouver une majoration suffisamment fine, mais je galère...

Pour la programmation, comme l'a dit scarta, programmation dynamique sur cette relation de récurrence, et c'est en quadratique. Pour faire mieux, il faudrait par exemple expliciter une formule avec une seule somme... C'est peut être possible.

scarta · #28

Ou pas. A mon sens il faut connaitre pour chaque quantité Q de sucre (Q entre 0 et N, avec un pas de un demi sucre) la probabilité d'avoir X demis sucres (X compris entre 0 et 2Q).
Ca fait (2Q+1) configurations pour chaque Q, soit (N+1)² au total.
Faire un code efficace ne diminuera pas le ratio - même si les premiers résultats sortiront peut être un peu plus vite, ensuite ça sera de plus en plus long quand même

Code:

double sucre(long sucres) {
        long halves = sucres<<1;
        halves ++;
        double *prob = malloc(halves * sizeof(double) << 1);
        int current = 0;
        int previous = halves;
        for(int i=0; i< halves; i++) prob[i] =prob[previous+i] = 0;
        prob[0] = 1;

        for(int total = halves - 2; total >= 2; total--) {
                current = previous;
                previous = halves - previous;
                prob[current] = prob[previous+1] * 2 / (total + 2);
                for(int i=1; i<= total; i++) prob[current+i] =
                        prob[previous+i+1] * 2 * (i+1) /(total + 2 + i) +
                        prob[previous+i-1] * (total - i + 2) / (total + i);
        }
        double res = prob[current+2];
        free(prob);
        return res;
}

Désolé, c'est tout crade dans un seul tableau mais c'est pour éviter de faire des allocations à tout bout de champ, tout en restant en mémoire dans du 2N et pas du N²

golgot59 · #29

Bon, voici le fruit de ma réflexion :

Le programme que j'ai fait (et corrigé) donne l'espérance du nombre de sucres entiers et de demi-sucres. Je pense que la probabilité de tirage d'un demi-sucre se rapproche de la proportion de ces derniers à mesure que le nombre N de sucres au départ grandit (je n'ai pas de preuve de cela pour le moment).

J'ai dû modifier la dernière formule qui était fausse (ainsi que le nombre d'itérations ).

Une fois corrigé, voici les résultats qu'il me donne :

Avec 1 sucre au départ, il restera pour l'avant dernier tirage :
0 demi-sucre et 1 sucre entier (c'est mieux, non ?)
Avec 2 : 1 demi et 0.5 entier (ce qui fait bien 1 + 2*0.5 = 2 pioches restantes)
3 : 1.1026 demis et 0.4487 entier (1.1026 + 2*0.4487 = 2 pioches restantes à nouveau)
10 : 1.3177 et 0.3411
100 : 1.5261 et 0.2369
1000 : 1.6352 et 0.1824
10 000 : 1.7026 et 0.1487
100 000 : 1.7485 et 0.1257
1 000 000 : 1.78195 et 0.1090

Ce qui donne les proportions de demi-sucres suivantes :

Code:
probabiltés mes proportions
1 0.0 0.0
2 0.5 0.666667
10 0.761443 0.794355
100 0.857820 0.870992
1000 0.896716 0.899634
10000 0.918266 0.919675
50000 0.928498 0.929429
100000 0.932128 0.932920
1000000 0.942345

Et le programme en question :

"nombre de sucres entiers :"
v=1000000
v1=v
"nombre de demi-sucres"
u=0
for i in range(1,2*v1-1):
u1=u
u=(u*(u-1)+v*(u+1))/(v+u)
v=(u1*v+v*(v-1))/(u1+v)
print("demi-sucres :",u)
print("sucres entiers :",v)
print("% de demi-sucres :",u/(u+v)*100)

Si le calcul de la proportion se rapproche bien de la probabilité de tirage comme je le pense, alors ce programme permet de gagner du temps de calcul, même si le résultat n'est pas exact...

scarta · #30

Quand je donnais des formations SQL, à la question "qu'est-ce qu'une bonne requête SQL ?" les gens répondaient : une requete qui renvoie le bon résultat.
Ce à quoi je rétorquais : une requête qui ne donne pas le bon résultat n'est pas une requête. Une bonne requête est celle qui le fait en temps optimal.

Ceci étant dit, j'ai fini par comprendre ce que fait ton programme.
Tu calcules l'espérance du nombre de sucres et l'espérance du nombre de moitiés, et sort le résultat à la fin - sauf que
1) tes deux variables aléatoires ne sont pas indépendantes : tu pourrais très bien ne calculer que u et en déduire v (comme tu le fais sur la fin pour trouver 2, mais c'est un invariant du problème => tu auras toujours une quantité donnée de sucre répartie en moitiés et en carreaux entiers)
2) accessoirement la moyenne d'une fraction n'est pas le rapport des moyennes du haut et du bas

Au final, ce programme sort une suite croissante et bornée par 1 - comme ce qu'on étudie, donc c'est dur d'affirmer que c'est une bonne approximation

Pour finir, un algo linéaire bon en fait non en N.ln(N) pour etre exact - pseudolinéaire quoi

Code:

double fastPow(double a, long b) {
        double res = 1;
        double c = a;
        for(long i = b; i; i>>=1) {
                if(i&1) res *= c;
                c *= c;
        }
        return res;
}

double sucre(long sucres) {
        double res = 0;
        double limit = 10000;
        double step = 0.001;
        for(double i=0; i<limit; i += step) {
                res += exp(-i) * fastPow(1 - (1+i)*exp(-i), sucres-1);
        }
        return 1 - res * sucres * step;
}

10^1: 0.761443
10^2: 0.857820
10^3: 0.896716
10^4: 0.918266
10^5: 0.932128
10^6: 0.941853
10^7: 0.949079
10^8: 0.954672
10^9: 0.959135
10^10: 0.962783
10^11: 0.965823
10^12: 0.968396
10^13: 0.970605
10^14: 0.972527
10^15: 0.974173

golgot59 · #31

Lol, OK, on ne joue pas dans la même cour !

Je ne sais pas programmer mais j'essaie de faire ce que je peux (j'ai découvert python récemment). En tous cas, merci pour le tien (je ne connais pas le langage que tu utilises), il a l'air super optimisé en effet, et les résultats qu'il donne sont très intéressants et semble en faveur de la limite vers 1.

Je vais malgré tout continuer de réfléchir à ce problème tout à fait énervant...

scarta · #32

C'est du C - après ça change pas des masses C ou Python, ça reste possible de faire pareil

Et l'implémentation utilise une formule qui n'a pas encore été détaillée ici mais que j'essaye de mettre au propre - mais le programme en lui même n'a rien de magique, il calcule juste de manière très laide une intégrale

scarta · #33

Pour info mon programme n'est au final pas vraiment linéaire (ou pas vraiment précis, au choix, après 10^15) : le calcul de l'intégrale nécessite beaucoup plus de pas pour être précis.
Donc on retombe sur le même problème (plus loin et à une echelle différente)

scarta · #34

Voilà voilà j'ai eu le temps de mettre au propre la formule "directe" telle qu'exposée par un des membres du site voisin
Plutôt que de passer par une probabilité 1/N de piocher parmi N sucres, l'idée est de passer par un processus de Poisson.

Sachant qu'un évenement se produit en moyenne [latex]\lambda[/latex] fois sur une période donnée, la probabilité qu'il se produise exactement k fois est
[TeX]p(k) = \frac{\lambda^k}{k!}e^{-\lambda}[/TeX]
Par ailleurs, au lieu de parler de sucres et de demis sucres, on ne parle que de sucres mais pris 0 fois (entier), 1 fois (demi) ou 2+ fois (y'a plus de sucre dans ce carreau)

Finir avec un sucre entier signifie pour ce sucre : n'avoir jamais été pris pour ce sucre alors que tous les autres ont été pris très 2 fois ou plus

Probabilité d'être pris 0 fois : [latex]e^{-\lambda}[/latex]

Probabilité d'être pris au moins 2 fois : [latex]1 - e^{-\lambda} - {\lambda}e^{-\lambda} = 1 - (1 + \lambda)e^{-\lambda}[/latex]
(1 - p(0) - p(1) quoi)

Probabilité que tous les sucres sauf 1 soit pris au moins deux fois et le dernier sucre 0 :
[TeX]e^{-\lambda}(1 - (1 + \lambda)e^{-\lambda})^{N-1}[/TeX]
Et pour finir, on somme pour tout lambda, et on considère chacun des N sucres comme pouvant être le dernier :
[TeX]N \int_{0}^\infty{e^{-\lambda}(1 - (1 + \lambda)e^{-\lambda})^{N-1}d\lambda}[/TeX]

Sydre · #35

Effectivement c'est plus simple comme expression

Marrant de se dire que
[TeX]n\int_0^{+\infty}e^{-\lambda}(1-(1+\lambda)e^{-\lambda})^{n-1}\mathrm{d}\lambda=\\\small\frac{1}{n!}\sum_{a=1}^{n-1}\sum_{b=a-1}^{n-2}\ldots\sum_{y=x-1}^2\left(\left(\frac{n-1}{n}\right)^{a-1}\left(\frac{n-2}{n-1}\right)^{b-1}\ldots\left(\frac{2}{3}\right)^{y-1}ab\ldots y\right)[/TeX]

scarta · #36

J'ai amélioré mon code qui sort des fractions (en trouvant un dénominateur commun pour un nombre de sucre initial donné, ce qui réduit le temps passé en PGCD)

Pour ceux que ça intéresse, p(100) =

Code:

75729070212884959962179462170111532945438181515983
56400623675554364260487008314254187178529217176107
62866726439769744990259525916382356751993590319655
76155880211056561927127524949190200177605828829960
83262296685860706423358223810981691821199589390661
39581256425225073595339295014991334054749986409388
88774745053198894405530874848257273532166399170966
12439829773800121502960144309732186526838487724183
16937712119207405363226070152938111078676408315155
69321532152177103557599369071309938705721856388957
01514471453879933579866926298137070671049315217540
53358140839685343571018235284463329082730815803854
22081027324781768636522033824586906759851971271465
93428140029264979316002387404572372370173457430015
97644667086055826769243243384497756642369948373578
15313865357019363155428830314168184606249451225949
84869142819624884417758631825045227866439579020648
14488872042604228586287134879539228594047079750192
95013190463409086581676623307415010409474721517471
40058329223569817032685030812805112114303652979558
03985811894986756112661936809822011902186863394098
96347166501186782727455802228332949602015264853402
48166207374375217111402536130703143606017370100839
98826839707892664613132570595134284703780327608947
56179780951707552772735798028192793688193587928073
91397455896524145937476374226202803425610162203926
43772423890718396662100085035457149523770636979659
85050534998166585161348747999581081620432302300035
47802577483138515653326994535145118360189237682181
00447634665747209002319005883078458867156457373122
10304036757716910563240300884124825088949464451033
89864764604127669028787605537638776530791690826855
46802971498358838562222190111634167551502675365903
14284353584033580617678254163127010889647112044666
19915940867323075146397337871705926943816104822505
85839302511291200768429208783827919527468102816912
45655437771397623229376855190788725046387710543101
64357088497241349753562666643849858476419286153680
95566260387722529372942865382381378423407931386877
07342772135384767372503029243984151914923885610410
28667046506119968348426524523913332302858687148339
87420901162968292767158877405212362160039716998708
56648732189805250717726590617182598168646179217389
51286150525481869567973285816388578409805770929561
86860215560402629072715357558667592965617216685298
67575548965576261485081811237438472968202778715518
20414494025497291786522656062964095800593374132919
49669429501461997905508459516371375131532325353042
50243840186152189346732011777604428149566868548832
30377096722672526555872513031317689714802493746024
82609883302204579755278121075697322959096090992410
90955436524151195187215356825628884408534015732017
81809869079785585031768466569831396227204654414299
24744685968626295122489072437291043258939619574515
73644379410917595057871451206943885762721350661296
25982236432897870270448643818054259794987116932359
20193604915700856047178925681814842191791494990559
11270455819270130397841631308090800112067009539623
62800202144703795504266177036933465597203845573793
57794645955940890031275168734113270379683098208273
43388180251085482577091484152665330925121026143644
64851389102077849291663919379099722866768597843436
60493492732799103015090568713177172389528466555025
426856478722974426105119443572851211511

/

88280843877444733117663241707652036866445127746206
90314467784357313584344535592841198669525676630616
13796154061887683764466343426961721415207145416647
29955252367774385234521415503292087791795080376663
08547527967688629259839227074743489662805350482854
70411758135388243201070668072833103480371923281254
82852704351906719538114065337878814246234482367899
70551853776210195918388588237221650549061269765604
99345478716690639731609540005601026806185691793301
42236433049485311276673227388396547049960291356278
53424659279932248489899963710129989881436738107722
92576419651348294210100501807208853583902908613392
26062477462249924216666150637342188464686891282445
34786109276107470846288789283973243133562713890987
66941765562192101881340932211398740446698239896090
31909899876150763872410527357140622268761624655129
90628594846202106731203085345658194098510576502813
23567588497440869684075904086523387944061736729872
74319513354926867183750938589905552833980391153620
69450192836968559754766755272069893776725972036382
55090944996689497652004331813452211029150922758602
97723027695187404851192201650244353877902804964465
87677786768166528510644497265169325820482485396128
74836768615040117316425094867702197065721743407339
13489687760159228601542582647989687226858149918120
59779994615157460278898485733820400135407287992706
11727188456776624382072523497594141532429960573821
12126250783611276060824092539049707301115035600194
88708225589965795512498993060337348722401336080842
59118299420162206351178397042443110648845135645556
39807535356937755154055079670621341403869768764656
88419226943583313576358078052237409036283795764391
21321308283763287510312992537093046418982076661684
24796069575492907585160040273224341696095646948600
18414286441677252244074339208452939154209609251674
93421848528514884199445119185982723406465947848923
15184352929940725419966939645845198770948697634783
91724482811568876679707560582404095301060027448236
39452098640503170853131346727101982249790617144600
38426575079001414798064023810705400545488281560029
93315721262517580726092223520619531861511904718244
38591052514933143222073785871792166650536713556047
61417809596445016499130170025433612401683703513701
26894164122067306628180276545210523665153571113458
96514303823772070017837607937057756743020391411152
81362087166022455496595626769503002545202060793011
05531279184688882087306758840102729838847935680231
07877640131161848227916214098593360827452154549853
02929247157970466833534762998917887786939025516206
02830805954747057983599746862762016358309863646251
03397933433210265971999526501128446806874501316955
23420495432601760244543465205166306963206593817369
33786460294927933310505216337403862698744021147308
31449982227011101796697945138476220397449315821451
96255420328168907237760919967207992681213419138974
27385573100060112388072006123104864646759868568433
70524463470750711671092737422312615772049189518210
19634778841999663796952274570913352393504527168790
86865985685253427652871457039777392799591485265128
85638946472336285130529136829688158155673310250158
98619762442240000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000

enigmatus · #37

@scarta #36 : J'avais le même résultat que toi

scarta · #38

c'est rassurant

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 - 17-06-2020 09:56:26

begjin say

#0 Pub

#27 - 17-06-2020 10:16:52

Beghiin Say

#28 - 17-06-2020 10:52:35

eghin Say

Code:

#29 - 17-06-2020 18:48:00

Beghin Sa

#30 - 17-06-2020 19:42:21

Behin Say

Code:

#31 - 17-06-2020 20:19:48

beghib say

#32 - 17-06-2020 20:28:27

Beghin aSy

#33 - 18-06-2020 08:02:44

Beghni Say

#34 - 18-06-2020 14:10:12

Beghi nSay

#35 - 18-06-2020 15:28:17

beghib say

#36 - 22-06-2020 10:03:05

brghin say

Code:

#37 - 22-06-2020 15:54:00

Behgin Say

#38 - 22-06-2020 20:32:53

Beghhin Say

Réponse rapide

Sujets similaires

Pied de page des forums