论坛 › 趣题妙解 › 合并石子问题(2)

KeyTo9_Fans 发表于 2022-7-25 18:54:14

合并石子问题(2)

《合并石子问题(1)》已经是10年前的坟贴了：https://bbs.emath.ac.cn/thread-3978-1-1.html

本贴是《合并石子问题(2)》，对合并规则作了一些改动：

有N颗体积为1的石子。

我们每次随机抽取2颗石子，合并成1颗石子。

每颗石子被抽到的概率均等。

假设要合并的$2$颗石子的体积分别为$a$和$b$。

如果$a=b$，那么可以无损合并，合并后的体积为$(a+b)$；

否则大石子会把小石子吸收掉，合并后的体积为$\max\{a,b\}$。

一共合并$(N-1)$次，最后剩下$1$颗石子。

记这颗石子的体积的期望值为$E(N)$。

(1)对于较小的$N$，$E(N)$的精确值是多少？

(2)对于较大的$N$，$E(N)$大约等于$N$的多少次方？

mathe 发表于 2022-7-25 21:37:01

这个结果只能取2的幂。每种合并过程可以看成一棵二叉树，只是不同的树的权重应该是不一样的

mathe 发表于 2022-7-27 17:26:49

根据链接内容，假设最后一步两个石子的合并过程，这两个石子分别是从h和N-h棵石子合并过来的概率为1/(N-1)
所以得出$p_k(N)=\frac1{N-1}\sum_{h=1}^{N-1}(2p_k(h)s_{k-1}(N-h)+p_{k-1}(h)p_{k-1}(N-h))$
好像总是倒数第三和第四大的两个非零数出现的概率最高，两者概率加起来通常超过90%

mathe 发表于 2022-7-28 14:00:46

2:2
3:2
4:2.666667
5:3.333333
10:4.519929
100:19.381907
1000:82.584912
10000:352.778718
100000:1506.949790
可以看出石子数目每增加10倍，E(N)大概增加4.27倍。所以大概$N^0.63$

KeyTo9_Fans 发表于 2022-7-28 21:45:24

我没有精确计算，直接抽样模拟，结果如下：
         3 2.000000
         9 4.231674
      27 8.502773
      81 16.931536
       243 33.662674
       729 66.887726
      2187 132.846680
      6561 264.103027
   19683 525.009766
   59049 1043.968750
    177147 2078.093750
    531441 4132.750000
   1594323 8197.000000
   4782969 16348.000000
14348907 32600.000000
43046721 64384.000000
$3^n$颗石子合并后，好像是$n$较小的时候，合并后的体积比$2^n$大，$n$较大的时候，合并后的体积比$2^n$小

mathe 发表于 2022-7-28 22:21:36

h=3 w=2.000000
      m=1
h=9 w=4.231746
      m=0.0031746
      m=0.937302
      m=0.0595238
h=27 w=8.502055
      m=8.32014e-20
      m=0.00991275
      m=0.922374
      m=0.0677133
h=81 w=16.932300
      m=8.44582e-96
      m=3.45346e-15
      m=0.0142225
      m=0.920398
      m=0.06538
      m=1.95842e-13
h=243 w=33.658228
      m=1.24972e-68
      m=5.17132e-14
      m=0.0173106
      m=0.922215
      m=0.0604749
      m=9.90855e-13
h=729 w=66.881955
      m=1.38857e-269
      m=1.03378e-62
      m=1.78279e-13
      m=0.0200685
      m=0.924867
      m=0.0550648
      m=9.18693e-13
      m=1.65113e-88
h=2187 w=132.907027
      m=2.537e-244
      m=3.02525e-60
      m=4.05497e-13
      m=0.0228738
      m=0.927353
      m=0.049773
      m=5.47905e-13
      m=8.77733e-86
h=6561 w=264.153414
      m=1.96039e-234
      m=1.00005e-58
      m=8.05039e-13
      m=0.0258793
      m=0.929332
      m=0.0447889
      m=2.80495e-13
      m=1.92705e-86
h=19683 w=525.100205
      m=1.17788e-228
      m=1.6475e-57
      m=1.51856e-12
      m=0.0291525
      m=0.930685
      m=0.0401626
      m=1.34692e-13
      m=4.46662e-88
h=59049 w=1044.002650
      m=3.59913e-224
      m=2.11411e-56
      m=2.79574e-12
      m=0.0327297
      m=0.931372
      m=0.0358987
      m=6.24828e-14
      m=4.59493e-90

mathe 发表于 2022-7-29 08:14:08

根据前面Fans的观察，由于$\log_3 2\approx 0.63$, 所以结果可能会近似$N^{\log_3 2}$,
我们可以猜测$p_k(N)$会以$k-1-\log_3 N$为中心，而且对于充分大的N,这个图像会基本不发生变化。
我们猜测$ p_k(N) \to f(k-\log_3 N)$, 由此，可以对$33334\le N \le100000$范围内描出$ k-\log_3 N \to p_k(N)$的图像

如果我们再对p_k(N)取自然对数，可以描出图像$ k-\log_3 N \to \ln(p_k(N))$

KeyTo9_Fans 发表于 2022-7-30 01:18:51

我前面的计算结果太粗糙了

我后来精确计算了一下，发现“石头数3倍、合并后2倍”是错觉

精确的结果应该是“石头数3.04383倍、合并后2倍”

或者是“石头数3倍、合并后1.98202倍”

总之N个石头合并后的体积应该是N的0.62271次方，不是N的0.63次方

因为当石头数增加至原来的3.04383倍时，合并后的体积分布与原来的分布是一样的，只是多了一个系数2

mathe你可以翻出你的原始数据看看，是不是这个结果

mathe 发表于 2022-7-30 12:22:13

#include <math.h>
#include <time.h>
#include <stdio.h>
#define MAX(a,b) ((a)>(b))?(a):(b)

#define N 1000000
#define MD 3
#define LN (2*MD+1)
int base;
double matrix;
double sum;

int main()
{
        int h,s,a,b;
        time_t start;
        start=time(NULL);
        matrix=1.0;
        for(h=MD;h<LN;h++)sum=1.0;
        base=1;base=2;
        matrix=1.0;
        for(h=MD;h<LN;h++)sum=1.0;
        for(h=3;h<=N;h++){
                base=round(log(h)/log(3))+1;
                for(a=0;a<LN;a++){
                        int hind = a+base-MD;
                        double r=0.0;
                        for(s=1;s<=h-1;s++){
                                int ua = hind+MD-base;
                                if(ua<0||ua>=LN)continue;
                                int ind2=h-hind;
                                int b=hind-base+MD-1;
                                if(b<0)continue;
                                double s2=0;
                                if(b>=LN)s2=1.0;else s2=sum;
                                r+=2.0*matrix*s2/(h-1);
                                if(ua>0&&b<LN){
                                  r+=matrix*matrix/(h-1);
                                }
                        }
                        matrix=r;
                        if(a==0)sum=r;
                        else sum=sum+r;
                }
                if(h%128==0){
                        fprintf(stderr,"h=%d time %ds\n",h,(int)(time(NULL)-start));
                }
        }
        for(h=2;h<=N;h++){
                printf("h=%d\n",h);
                double p=0;
                double m=1.0;
                for(s=0;s<LN;s++){
                        int a=base+s-MD;
                        if(matrix==0)continue;
                        printf("\tm[%d]=%g\n",a,matrix);
                }
        }
        return 0;
}

这个比较乱的代码应该能够在一天以内运行到1000000，不知道误差有多大，你们有空可以试验一下

KeyTo9_Fans 发表于 2022-8-3 00:16:38

8# mathe 点评：
我不知道你是怎么判断出来的，我觉得我的数据量不够评估，结果就是用3#的公式推算的就是运行一下上面的代码，看一下前后两个峰值对应的N，差了多少倍啊

例如：

当n=1时，合并后的体积等于1的概率达到最大值，为1.00000000000000000
当n=2,3时，合并后的体积等于2的概率达到最大值，为1.00000000000000000
当n=8时，合并后的体积等于4的概率达到最大值，为0.97142857142857142
当n=24时，合并后的体积等于8的概率达到最大值，为0.94474148406846015
当n=74时，合并后的体积等于16的概率达到最大值，为0.93570797290841390
当n=224时，合并后的体积等于32的概率达到最大值，为0.93287352346257579
当n=683时，合并后的体积等于64的概率达到最大值，为0.93192170797609386
当n=2078时，合并后的体积等于128的概率达到最大值，为0.93160994038313749
当n=6326时，合并后的体积等于256的概率达到最大值，为0.93150737895583391
当n=19255时，合并后的体积等于512的概率达到最大值，为0.93147368686003040
当n=58610时，合并后的体积等于1024的概率达到最大值，为0.93146261826311938
当n=178399时，合并后的体积等于2048的概率达到最大值，为0.93145898182323894
当n=543016时，合并后的体积等于4096的概率达到最大值，为0.93145778712761851
……

由此可知当n=0.858558*3.043829^k时，合并后的体积等于2^k的概率达到最大值，为0.93145720258744+0.31741467/n

因此n个体积为1的石子合并后的体积大约是n的0.622709次方

查看完整版本: 合并石子问题(2)