合并石子问题(1)

mathe

4# 056254628

为什么$E(6)$和$E(8)$都小于$2$？

我觉得对于所有的$N$，都有$E(2N)>=2$。
KeyTo9_Fans 发表于 2012-1-20 18:44

是的，很容易归纳证明

056254628

9# wayne

N＝6
1,1,1,1,1,1
－－>1,1,1,1,2
－－>1，1，1，1 （2/5 的概率）    2/5*E(4)
           1，1，2，2 （3/5的概率）
         －－> 2,2,2（1/6的概率）      －－>2
         －－> 1，1，3（1/6的概率）   －－>2  
         －－> 1，1，2（4/6的概率）
               －－> 1，1（2/3的概率）  －－>2  
               －－> 2，2（1/3的概率）  －－>3
所以E(6 )  =2/5*E(4)+3/5*(1/6*2+1/6*2+4/6*(2/3*2+1/3*3))=34/15

mathe

4  2.33333333
6  2.26666667
8  2.30476190
10  2.30617284
12  2.31181017
14  2.31424707
16  2.31633276
18  2.31781010
20  2.31897922
22  2.31990620
24  2.32066314
26  2.32129084
28  2.32181957
30  2.32227054
32  2.32265944
34  2.32299801
36  2.32329525
38  2.32355813
40  2.32379218
42  2.32400180
44  2.32419054
46  2.32436132
48  2.32451652
50  2.32465814
52  2.32478785
54  2.32490706
56  2.32501697
58  2.32511860
60  2.32521284
62  2.32530044
64  2.32538207
66  2.32545830
68  2.32552964
70  2.32559654
72  2.32565939
74  2.32571853
76  2.32577428
78  2.32582692
80  2.32587669
82  2.32592382
84  2.32596851
86  2.32601093
88  2.32605125
90  2.32608963
92  2.32612618
94  2.32616105
96  2.32619433
98  2.32622614
100  2.32625657

056254628

我有一种思路：



合并石子的一个过程如上图。
最后一步，实际上是1+5 类型。
  5个石子融合后最后和1个石子融合。
4+2类型是指4个石子先后融合，2个石子也先后融合，最后两者融合。
计算每种类型的值F()
    如
    F(1+5)=2          奇数个石子融合必等于1， 奇数＋奇数类型必等于2
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
2个石子的类型      
   F(1+1) ＝2
4个石子的类型
    F(1+3)=2    概率2/3
        F(2+2)=3    概率1/3
    所以E(3)=2*2/3+3*1/3=7/3
6个石子的类型：
    F(1+5)   =2
        F(3+3)    =2
       F(2+4)   =?
                  F(2)=2    F(4)=2或3
                所以F(2+4)   =3或2
            实际上F(2+4)分为 F(1+3+2)和F(2+2+2)两者情况
      前者F(1+3+2)＝3，后者F(2+2+2)＝2
所以计算E(6)的值，只要知道F(1+3+2)＝3类型的概率p即可 ，其他类型的值都等于2   
      E(6)＝2*(1-p)+3*p=2+p
      而p=4/15,  所以E(6）＝2+4/15=34/15
----------------------------------------------------------------
对于其他的N值，只要求出F值等于3的类型的概率p，E值就等于2＋p。
这也说明了所有大于2的偶数的E值大于2。
因此关键是如何正确的求出F值等于3的类型的概率p

056254628

其他N值，可能F值大于3，所以
需要求出F值不等于2的类型的概率p
   如等于3的概率p1，等于4的概率p2，等于5的......
      E(N)=2+(3-2)*p1+(4-2)*p2+(5-2)*p3+......
               =2+p1+2*p2+3*p3+......

wayne

12# 056254628
嗯，是我算错了。
刚才编了一个小程序，很笨的思想，效率比较低。
不过，算出了
E(6) =34/15
E(8) = 242/105

1. 
   
2. f[x_] := If[Min[x] == Max[x], Min@x + 1, Min[x]];
   
3. g[long_, pair_] := Module[{tmp}, tmp = Flatten@Table[If[MemberQ[ii, pair[[1]]], Rest[ii], ii], {ii, Gather[long]}]; Flatten@Table[If[MemberQ[ii, pair[[2]]], Rest[ii], ii], {ii, Gather[tmp]}]];
   
4. s[sub_] := If[Length[sub] > 2, Subsets[sub, {2}], List@sub]
   
5. 
   
6. n = 6; x = List@PadLeft[{2}, n - 1, 1];
   
7. Do[x = Flatten[Table[Table[Join[{f[jj]}, g[kk, jj]], {jj, s[kk]}], {kk, x}], 1], {n - 2}];
   
8. Mean@Flatten@x
   

复制代码

wayne

晕死，改代码花了这么长时间
现在效率明显提高：
E(10) =934/405
E(12) =360469/155925
E(14) = 2814622/1216215
E(16) = 44818433/19348875

wayne

1. {4, 7/3, 2.3333333333333333333}
   
2. {6, 34/15, 2.2666666666666666667}
   
3. {8, 242/105, 2.3047619047619047619}
   
4. {10, 934/405, 2.3061728395061728395}
   
5. {12, 360469/155925, 2.3118101651434984768}
   
6. {14, 2814622/1216215, 2.3142470698026253582}
   
7. {16, 44818433/19348875, 2.3163327583645043963}
   
8. {18, 3594168154/1550674125, 2.3178101033961600410}
   
9. {20, 36171339103/15597957375, 2.3189792248678971659}
   
10. {22, 90428309425574/38979295480125, 2.3199062043510287612}
    
11. {24, 12714348335602766/5478756531373125, 2.3206631400384943599}
    
12. {26, 1914048263079434/824562019771875, 2.3212908394798228431}
    
13. {28, 18719553371462258173/8062449634755140625, 2.3218195733920733463}
    
14. {30, 280059494536250948278/120597272957758471875, 2.3222705428367953621}
    
15. {32, 67359786835571062751804/29001146569682023996875, 2.3226594394715895785}
    
16. {34, 303000235021575126052361594/130434995499287619218203125, 2.3229980103248440346}
    
17. {36, 81008035454588784573959051881/34867731767889277340286328125, 2.3232952459841816804}
    
18. {38, 1684644565205504554896296858518/725027939213386357871275078125, 2.3235581335434425893}
    
19. {40, 1379534338939722609189264834285266774/593656501767616816756789390344140625, 2.3237921842549495637}
    
20. {42, 573691784542114615646064677029349374/246855137651848777758908367181640625, 2.3240018012151672664}
    
21. {44, 113266641551414870937145109286716564213/48733801917832544139216438134614453125, 2.3241905431960283913}
    
22. {46, 11494576970942130720478802489311164391605854/4945262549612057416526988059710001630859375, 2.3243613166390628652}
    
23. {48, 489932405826365101696295594250364472794052477/210767444363573386164596469598607990654296875, 2.3245165177466058759}
    
24. {50, 2655586357106340156196568421088439752575239714/1142355648960385263217734241793010376728515625, 2.3246581391032547662}

复制代码

发现mathe数值计算的精度相当高啊

mathe

C的精度还是不够呀，改用Pari/Gp计算结果:
P[4]=7/3~=2.333333333333333333333333333
P[6]=34/15~=2.266666666666666666666666667
P[8]=242/105~=2.304761904761904761904761905
P[10]=934/405~=2.306172839506172839506172840
P[12]=360469/155925~=2.311810165143498476831810165
P[14]=2814622/1216215~=2.314247069802625358180913736
P[16]=44818433/19348875~=2.316332758364504396250427996
P[18]=3594168154/1550674125~=2.317810103396160041040215332
P[20]=36171339103/15597957375~=2.318979224867897165926189101
P[22]=90428309425574/38979295480125~=2.319906204351028761191353410
P[24]=12714348335602766/5478756531373125~=2.320663140038494359929997187
P[26]=1914048263079434/824562019771875~=2.321290839479822843109284352
P[28]=18719553371462258173/8062449634755140625~=2.321819573392073346279396598
P[30]=280059494536250948278/120597272957758471875~=2.322270542836795362089982819

P[32]=67359786835571062751804/29001146569682023996875~=2.32265943947158957850085
1972
P[34]=303000235021575126052361594/130434995499287619218203125~=2.322998010324844
034598593531
P[36]=81008035454588784573959051881/34867731767889277340286328125~=2.32329524598
4181680392194705
P[38]=1684644565205504554896296858518/725027939213386357871275078125~=2.32355813
3543442589289354060
P[40]=1379534338939722609189264834285266774/593656501767616816756789390344140625
~=2.323792184254949563682406044
P[42]=573691784542114615646064677029349374/246855137651848777758908367181640625~
=2.324001801215167266356933736
P[44]=113266641551414870937145109286716564213/4873380191783254413921643813461445
3125~=2.324190543196028391284869228
P[46]=11494576970942130720478802489311164391605854/49452625496120574165269880597
10001630859375~=2.324361316639062865242714378
P[48]=489932405826365101696295594250364472794052477/2107674443635733861645964695
98607990654296875~=2.324516517746605875922781478
P[50]=2655586357106340156196568421088439752575239714/114235564896038526321773424
1793010376728515625~=2.324658139103254766227269383
P[52]=3386061530744337632684741324620617140285928199363/145650345242449121060261
1158286088230328857421875~=2.324787850731084723535321004
P[54]=1484710199197607933588392772966133681478194987167858/638610559185756464430
581237855800321352370849609375~=2.324907062436688300264175509
P[56]=37189294398026769612681880747230556842942343720439640914/15995278675925642
164592768264574230648912832670166015625~=2.325016972289458149733483302
P[58]=74195885473088900547775883882082524166839366070249075828922/31910580958471
656118362572687825590144581101176981201171875~=2.325118604692507025460906212
P[60]=2365608171964378337910842653525204661143495722820419454612427/101737274571
3260936991025376438563690758601194667357177734375~=2.325212840556186561251130563

P[62]=26807899766737700716008774623701993996823176066965941553905831282/11528789
694980694994833300256157462315700256537878594049072265625~=2.3253004414165949145
66567708
P[64]=31990534015064675055594124736786079231913712098481612611204171404532103/13
757108753595648665519665029568345104465749222289382342659100341796875~=2.3253820
68867007983988576791
P[66]=13196758823353444667011018178011214318737466760825300667240978682654/56749
06671724960261331435124811626559056905050032745789398193359375~=2.32545830032868
5671505623826
P[68]=45978113631211207947245097184833110309768074988071127207824824322786088779
49/1977102884522998647965158659724414716688295149481318583375252605621337890625~
=2.325529641938892612625195762
P[70]=66659101137736032470533304798113426052821244655000161710253318777375856848
2/286632268390245632686087147182886968566971970132441811679541627288818359375~=2
.325596539151015725528049332
P[72]=13402931052297542333664587957606619516685996526725319107042539440610448643
969229218/5763067083610511373946880803023995079748294972698842945273440696388665
924072265625~=2.325659385505664228772099192
P[74]=21569992999304933808532140839032991720196316831189492994114989240166573803
5381166/927455008923969619763159996959403494769045878031387584824164246791758361
81640625~=2.325718529929594293676002665
P[76]=14554553934936459932677335881140896437057773983569964839794832937492329624
122506250513/6257939148398805285405362958935838135509289867093634893834964408361
170932769775390625~=2.325774282842056305661612078
P[78]=24366033314088020470993916835183934883985071074565062450041508269264824694
06521845857826/10476288278829422838239057622150846637898114166061379131475259570
99229058292388916015625~=2.325826921289204953728499833
P[80]=30179488771674916333592773316573858314562335946920193287004875836413090801
9895425830650664211/129755325632035276093750436866063969135283640777453138598382
604447673534089673780059814453125~=2.325876693281859880028107687
P[82]=24553513069043895796634061058891996037207925186788081349244415105043214525
497064089387722255674/1055645625291998606965253622989868257425608376330600452025
6416346988079348820047626495361328125~=2.325923821476760313277377375
P[84]=15182345096083384421908902432408588532371283004048507307515956878957746653
7330605414835210027099610263/652732186823237567851651142960572589259515041855456
15755880006633930388621670908306575069427490234375~=2.32596850631403334254056158
9
P[86]=59710886974653514904927016114243900959026124669979894869441054892057053946
99288226607771443379078918/25670939993378700037790497062696853103933601024786596
18927133581015835893310475936440753936767578125~=2.326010928702054968740561254
P[88]=20277304959262546188862033517348874040329480510160780653139318533370560489
2440245230146089806494972407530186/871747986593346231655890612516134234141884940
45451035029760716419859489428620499867038348497982025146484375~=2.32605125232385
7819249813722
P[90]=99259045243580235735781924752590407604108180131613337074371782851032541992
7763879888165954247339358121846424286/426720639437442980395558454826647707612452
678352482816470678706875212200753097346849152715897622013092041015625~=2.3260896
25625703046570763417
P[92]=91342062579511697213188315003589418266263098508273961840806611373767148962
23649875681609306308072935113344131479/39267888056097281004939592640789266576921
20714277341872915571471132570701312210416510742408091600322723388671875~=2.32612
6183537610758244275181
P[94]=74122508229730261257333369748776196359765017034422167913880785915488144068
91345835560834044370507902506748336622402/31864736219638940674302451792922819554
62517956085643008051194614369047813211878982103864207036683908939361572265625~=2
.326161048966943037733305160
P[96]=38821811506442176249585296972323380664181650546398449088238609318224416540
906180523729266006859885872849977171323392808808/1668898033898668716399220046305
84656662273873565109705443026889770540976240674895154249730718232449554549145698
54736328125~=2.326194334099104033540765428
P[98]=80390675449847493979619025180274882977895674160167149372006891870847572653
4977107250433705646131475988481708532586340102/345584094402983417399966579004483
98981514051951502828067971838698660374358525862442102520201384503536877393722534
1796875~=2.326226141533714163464351417
P[100]=5226539659894128497233070710771117530692738619480669765678835924990181922
81866029110716455344070749740617794214017877146521/22467597675603446651024837496
65956066980639853832600872629389756550122874403831405346712609752485511903194928
16925048828125~=2.326256565279959920707809898

mathe

dumpall(N)={
    local(c,v,m,s,p);
    v=vector(N);
    v[1]=vector(2);
    v[1][2]=1;
    for(u=2,N,
       m=2;
       for(h=1,u-1,
         s=1+min(length(v[h]),length(v[u-h]));
         if(s>m,m=s)
       );
       v[u]=vector(m);
       v[u][2]=u/(2*u-1);
       for(h=1,u-1,
          for(i1=2,length(v[h]),
             for(i2=2,length(v[u-h]),
                p=v[h][i1]*v[u-h][i2]/(2*u-1);
                if(i1==i2, v[u][i1+1]+=p,
                           if(i1<i2, v[u][i1]+=p,v[u][i2]+=p)
                )
             )
          )
       );
       p=0;
       for(h=2,m,
          p+=v[u][h]*h
       );
       print("P["2*u"]="p"~="p*1.0)
    );
}