堆叠杯子的趣味难题

iseemu2009

一道国外有趣的堆叠杯子的趣味难题，需用到编程思维，靠人力计算不能实现。求计算方案数的思考过程。

mathe

这个相当于直线排列n颗石子，一只青蛙从任何一颗石子出发，每次可以向左或向右跳到相邻或间隔一颗石子的石子上。要求不重复跳遍所有石子的方案数目。
我们假设n颗石子，从第i颗石子出发，第一步向右跳的方案数目为S(n,i), 那么总数目必然是\(2\sum_{k=1}^n S(n,k)\) (显然S(n,n)=0)
我们先查看从第k颗石子出发（左边和右边都至少有两颗以上石子）的情况，如果从k跳到k-1,那么如果接下去向左，将永远无法到达k+1位置；而如果接下去向右到k+1，那么将永远无法达到k-2位置；由此得出，只要左右都同时还有两颗以上石子的，第一步必须间隔跳跃；比如第一次跳到k-2,那么容易分析，只要左边还有两颗以上，必须继续间隔向左跳跃，直到跳到最左边或离左边只有一个空格，这时显然就只能先使用最左边空格（如果存在）后掉头向右，直到跳到k+1位置。所以方案数目有S(n-k-1,1)+S(n-k-1,2). 也就是\(\begin{matrix}S(n,k)=S(k-2,1)+S(k-2,2) &,&(2\le k \le n-2)\end{matrix}\)
而第一步从第一格出发，必须向右，显然也满足上面公式，也就是k=1也成立；而第一步从第二格出发，必须向右，类似前面分析，必须间隔一格跳远直到最右边，再掉头，只有唯一方案；所以S(n,2)=1。而对于k=n-1,第一个向右只能跳到最右边然后掉头向左到n-2位置，所以为S(n,n-1)=S(n-3,1)+S(n-3,2).

四来

这样算一种还是两种？

mathe

我们记L(n,k)是从第k个石子出发，第一步向左的数目；R(n,k)是从第k个石子出发，第一步向右的数目，于是显然
L(n,k)=R(n,n+1-k)
R(n,n)=0
而对于R(n,1),由于第二步跳到位置2相当于n-1个石子从第一个开始，等于R(n-1,1); 而第二步跳到位置3,相当于n-1个石子第一步从第二个石子开始，
等于R(n-1,2)+L(n-1,2),于是
R(n,1)=R(n-1,1)+R(n-1,2)+L(n-1,2)=R(n-1,1)+R(n-1,2)+R(n-1,n-2)
而对于R(n,k),从前面分析知道，只要左边还有石子(k>=2),那么必须先把右边走完，然后余下k-1个石子从第k-1个开始，相当于L(k-1,k-1)，所以
R(n,k)=L(k-1,k-1)=R(k-1,1)， 当2<=k<=n-1。
而我们还有初始数据:
R(1,1)=1
R(2,1)=1
R(3,1)=R(2,1)+R(2,2)+R(2,1)=2, R(3,2)=R(1,1)=1

我们可以给一段gp程序

1. 
   
2. dumpr(n)=
   
3. {
   
4.     local(R,s);
   
5.     R=matrix(n,n);
   
6.     R[1,1]=1;
   
7.     R[2,1]=1;
   
8.     R[3,1]=2;R[3,2]=1;
   
9.     for(u=4,n,
   
10.        R[u,1]=R[u-1,1]+R[u-1,2]+R[u-1,u-2];
    
11.        R[u,2]=1;
    
12.        for(v=3,u-1,
    
13.           R[u,v]=R[v-1,1];
    
14.        );
    
15.        s=0;
    
16.        for(v=1,u-1,s+=R[u,v]);
    
17.        print("S[",u,"]=",2*s);
    
18.     );
    
19. }
    

复制代码

得到结果如下
S[4]=12
S[5]=20
S[6]=34
S[7]=56
S[8]=88
S[9]=136
S[10]=208
S[11]=314
S[12]=470
S[13]=700
S[14]=1038
S[15]=1534
S[16]=2262
S[17]=3330
S[18]=4896
S[19]=7192
S[20]=10558
当然如果继续计算到S[1000]也很容易，只是数值会超级大

然后在OEIS可以搜索到A003274,是所有前n个数的置换数目，要求相邻两个数差值为1或2，正好和这个题目的匹配。

iseemu2009

mathe 发表于 2025-2-22 16:36
我们记L(n,k)是从第k个石子出发，第一步向左的数目；R(n,k)是从第k个石子出发，第一步向右的数目，于是显然 ...

你的计算数据跟题目给出的正确数据有出入吧？比如 S(8),S(20)

iseemu2009

为方便大家思考这个问题，我用CAD精确画出了4个杯子的所有堆叠方法，图中给出了六种不同的情况，把六种情况上下颠倒放置又可以得到六种堆叠方法，所以 S(4)=12。

mathe

明白了，两个模型还是略有不同，所以本题模型处理起来要复杂一些，但是计算量应该类似。
我们用u(k)代表开口朝上的k号杯子，d(k)代表开口朝下的k号杯子，
那么u(k)上面可以叠放{u(k-1), d(k+2),d(k-2)}之一，但是不能放k+1号杯子，这个是同青蛙跳题目的区别。
同样d(k)上面可以叠放{d(k+1), u(k+2),u(k-2)}之一, 但是不能放k-1号杯子。

于是我们可以使用U(n,k)代表n个杯子，最底下一个是k号杯子开口朝上时的数目; D(n,k)代表n个杯子，最底下一个是k号杯子开口朝下时的数目。
我们可以用UP(n,k)代表n个杯子，最底下一个是k号杯子开口朝上时的数目，上面一个编号大于k; UM(n,k)代表n个杯子，最底下一个是k号杯子开口朝上时的数目，上面一个编号小于k；
可以用DP(n,k) 代表n个杯子，最底下一个是k号杯子开口朝下时的数目,上面一个标号大于k; DM(n,k)代表n个杯子，最底下一个是k号杯子开口朝下时的数目,上面一个标号小于k;
只要能够递推计算完它们，就可以解决这个问题了。我们可以以楼上分析为基础，再结合u/d之间特殊关系，来得到对应的递推式。
比如对于
UP(n,1)类似4#分析，我们需要判断上面一个是2号杯子和3号杯子两种情况，由于u(1)上面不能叠放2号杯子，所以上面只能叠放d(3), 所以去掉下面一号杯子，每个杯子编号在减一，相当于D(n-1,2), 于是我们得出第一个递推式UP(n,1)=D(n-1,2)=DP(n-1,2)+DM(n-1,2). 而UM(n,1)=0.
而对于DP(n,1), 由于d(1)上面只能对方d(2),u(3), 我们得出DP(n,1)=D(n-1,1)+U(n-1,2)=DP(n-1,1)+UP(n-1,2)+UM(n-1,2). 而DM(n,1)=0.
类似对于U(n,2),u(2)上面可以放u(1),d(4)之一.
   如果放了u(1),接下去只能放d(3),得到UD(n,2)=U(n-2,1)=UP(n-2,1)
  如果放了d(4), 那么我们根据4#知道只能一路继续+2下去，每次+2需要杯子翻转一次；如果n是偶数，那么如果n是4的倍数，最后到达d(n), 由于d(n)无法到达n-1状态，需要淘汰；如果n除以4余数为2，最后到达u(n)，而u(n)需要继续到达u(n-1),然后再继续间隔跳跃，每次翻转，最后到达d(3),最终达到u(1),所以只有一种方案； 如果n是奇数，n-1是4的倍数，那么会先到达d(n-1), 然后可以到达d(n),然后每次两格回跳，每次翻转，达到u(3),最终达到d(1),所以也只有1中方案；如果n+1是4的倍数，那么会先到达u(n-1),无法使用杯子n,淘汰。所以得到UP(n,2)在n除以4的余数为1,2的时候是1；余数为0，3时结果为0.

后面我们需要对于更加一般的U(n,k)和D(n,k)做类似分析，应该都可以得到递推式，就是分析有点麻烦;
需要注意对于3<=k<=n-2时，由于两边都有两个以上数字，按照4#分析，都必须走+-2改变杯子方向的方案，直到到达一边顶点，也就是同样需要按照n-k除以4的余数来分析，应该一半无解，一半形成递推关系。最后对于k=n-1和n再做单独处理即可形成完整递推关系，然后计算机就可以轻松求解了。

mathe

S[3]=6
S[4]=12
S[5]=16
S[6]=22
S[7]=36
S[8]=58
S[9]=82
S[10]=114
S[11]=174
S[12]=266
S[13]=382
S[14]=548
S[15]=816
S[16]=1212
S[17]=1762
S[18]=2566
S[19]=3780
S[20]=5560
S[21]=8128
S[22]=11892
S[23]=17454
S[24]=25604
S[25]=37498
S[26]=54932
S[27]=80538
S[28]=118062
S[29]=172996
S[30]=253510
S[31]=371574
S[32]=544600
S[33]=798112
S[34]=1169658
S[35]=1714260
S[36]=2512406
S[37]=3682066
S[38]=5396294
S[39]=7908702
S[40]=11590806
S[41]=16987102
S[42]=24895768
S[43]=36486576
S[44]=53473720
S[45]=78369490
S[46]=114856026
S[47]=168329748
S[48]=246699284
S[49]=361555312
S[50]=529885016
S[51]=776584302
S[52]=1138139664
S[53]=1668024682
S[54]=2444608936
S[55]=3582748602
S[56]=5250773338
S[57]=7695382276
S[58]=11278130826
S[59]=16528904166
S[60]=24224286500
S[61]=35502417328
S[62]=52031321438
S[63]=76255607940
S[64]=111758025330
S[65]=163789346770
S[66]=240044954650
S[67]=351802979982
S[68]=515592326818
S[69]=755637281470
S[70]=1107440261388
S[71]=1623032588208
S[72]=2378669869748
S[73]=3486110131138
S[74]=5109142719278
S[75]=7487812589028
S[76]=10973922720240
S[77]=16083065439520
S[78]=23570878028476
S[79]=34544800748718
S[80]=50627866188316
S[81]=74198744216794
S[82]=108743544965436
S[83]=159371411153754
S[84]=233570155370630
S[85]=342313700336068
S[86]=501685111489742
S[87]=735255266860374
S[88]=1077568967196528
S[89]=1579254078686272
S[90]=2314509345546562
S[91]=3392078312743092
S[92]=4971332391429454
S[93]=7285841736976018
S[94]=10677920049719022
S[95]=15649252441148478
S[96]=22935094178124590
S[97]=33613014227843614
S[98]=49262266668992000
S[99]=72197360847116592
S[100]=105810375074960304
...
S[1000]=26962901013997007773476449840406160338483621262752268591326543606162290720748003129661220722119075977873544416448534677592402973194126252297783679735507922650088522700

1. dumpr2(n)=
   
2. {
   
3.     local(UP,UM,DP,DM,s);
   
4.     UP=matrix(n,n);UM=matrix(n,n);DP=matrix(n,n);DM=matrix(n,n);
   
5.     UM[1,1]=DM[1,1]=1;DP[1,1]=UP[1,1]=1;
   
6.     UP[2,1]=0;UP[2,2]=0; DP[2,1]=1;DP[2,2]=0;
   
7.     UM[2,1]=0;UM[2,2]=1; DM[2,1]=0; DM[2,2]=0;
   
8.     for(u=3,n,
   
9.          UP[u,1]=DP[u-1,2]+DM[u-1,2];         UM[u,1]=0;
   
10.          DP[u,1]=DP[u-1,1]+UP[u-1,2]+UM[u-1,2];         DM[u,1]=0;
    
11.          for(v=2,u-1,
    
12.              if((u-v)%4==0, UP[u,v]=UM[v-1,v-1]);
    
13.              if((u-v)%4==1, UP[u,v]=0);
    
14.              if((u-v)%4==2, UP[u,v]=0);
    
15.              if((u-v)%4==3, UP[u,v]=DM[v-1,v-1]);
    
16.              if((v-1)%4==0, UM[u,v]=0);
    
17.              if((v-1)%4==1, UM[u,v]=DP[u-v,1]);
    
18.              if((v-1)%4==2, UM[u,v]=UP[u-v,1]);
    
19.              if((v-1)%4==3, UM[u,v]=0);
    
20.              if((u-v)%4==0, DP[u,v]=0);
    
21.              if((u-v)%4==1, DP[u,v]=UM[v-1,v-1]);
    
22.              if((u-v)%4==2, DP[u,v]=DM[v-1,v-1]);
    
23.              if((u-v)%4==3, DP[u,v]=0);
    
24.              if((v-1)%4==0, DM[u,v]=DP[u-v,1]);
    
25.              if((v-1)%4==1, DM[u,v]=0);
    
26.              if((v-1)%4==2, DM[u,v]=0);
    
27.              if((v-1)%4==3, DM[u,v]=UP[u-v,1]);
    
28.          );
    
29.          UP[u,u]=0; DP[u,u]=0;
    
30.          UM[u,u]=UM[u-1,u-1]+DP[u-1,u-2]+DM[u-1,u-2];
    
31.          DM[u,u]=UP[u-1,u-2]+UM[u-1,u-2];
    
32.          s=0; for(v=1,u, s+=UP[u,v]+DP[u,v]+UM[u,v]+DM[u,v]);
    
33.          print("S[",u,"]=",s);
    
34.     )
    
35. }

复制代码

mathe

注意到四个数组递推式里面第二下标基本上都是类似DP[x,1],DP[x,x]; 只有DP[x,1]会用到UM[y,2]等，DM[x,x]会用到UP[y,y-1]等等。
另外注意到性质
UM[n,x]=DP[n,n+1-x]
DM[n,x]=UP[n,n+1-x]
UP[n,x]=DM[n,n+1-x]
DP[n,x]=UM[n,n+1-x]
这个性质无论对于初始值或者递推式都成立，所以这个性质会一直保存。
于是计算过程中实际上我们只需要保存DP[x,1],DM[x,1],UP[x,1],UM[x,1], 这样可以极大的节省空间。
而DP[x,2]等可以通过函数计算，得到效率更高的pari/gp代码

1. getUP2(u)=
   
2. {
   
3.    local(r,v);v=2;
   
4.    if((u-v)%4==0, r=1);
   
5.    if((u-v)%4==1, r=0);
   
6.    if((u-v)%4==2, r=0);
   
7.    if((u-v)%4==3, r=1);
   
8.    if(u==2,r=0);
   
9.    r
   
10. }
    
11. 
    
12. getUM2(u,DP)=
    
13. {
    
14.    if(u==2,1, DP[u-2])
    
15. }
    
16. 
    
17. getDP2(u)=
    
18. {
    
19.    local(r,v);v=2;
    
20.    if((u-v)%4==0, r=0);
    
21.    if((u-v)%4==1, r=1);
    
22.    if((u-v)%4==2, r=1);
    
23.    if((u-v)%4==3, r=0);
    
24.    r
    
25. }
    
26. 
    
27. getDM2(u)=
    
28. {
    
29.     0
    
30. }
    
31. 
    
32. dumpr3(n)=
    
33. {
    
34.     local(UP,UM,DP,DM,s);
    
35.     UP=vector(n);UM=vector(n);DP=vector(n);DM=vector(n);
    
36.     UM[1]=DM[1]=1;DP[1]=UP[1]=1;
    
37.     UP[2]=0; DP[2]=1;
    
38.     UM[2]=0; DM[2]=0;
    
39.     for(u=3,n,
    
40.          s=0;
    
41.          UP[u]=getDP2(u-1)+getDM2(u-1); UM[u]=0;
    
42.          DP[u]=DP[u-1]+getUP2(u-1)+getUM2(u-1,DP); DM[u]=0;
    
43.          s+=2*(UP[u]+UM[u]+DP[u]+DM[u]);
    
44.          for(v=2,u-1,
    
45.              if((u-v)%4==0, s+=DP[v-1]);
    
46.              if((u-v)%4==3, s+=UP[v-1]);
    
47.              if((v-1)%4==1, s+=DP[u-v]);
    
48.              if((v-1)%4==2, s+=UP[u-v]);
    
49.              if((u-v)%4==1, s+=DP[v-1]);
    
50.              if((u-v)%4==2, s+=UP[v-1]);
    
51.              if((v-1)%4==0, s+=DP[u-v]);
    
52.              if((v-1)%4==3, s+=UP[u-v]);
    
53.          );
    
54.          print("S[",u,"]=",s);
    
55.     )
    
56. }
    

复制代码

由此就可以轻松计算出比如
S[10000]=31127930776577878223912939652283917007309720910229733404980767096433599906671652710001938387364854655740186734590908649337356091922621078920216052890139240853978834431849749301441120982004337938233139987156772948822431045256171786679546693883324545906104252627630400702096311093294706718040576545408214926280868115722806877605932122196052494082623011237601970298979931170969289976068813021526033675831059992990730577890989631841080978643700990585349553415808578723546946916820500168052783156513103111742386023998708284150142291655601723334559334350809797047051453261439348573046522312830382200517486230343043897711784893663693727639779892990757401519165412641082883760609113920300639590955495404532854649163537655214920643816932518331623066331271805714815696682277895216235139841994069819511789713982835479855092133910403059302059116100776409354150790798813753273844790430066915461356063289968467220558523526513213228886433823912526799122628736929131922922546052623254928685742281834365448375330946022402419007606452114909224699039372244294796852125356356305365277108241592981671643800362193173209313411961857120583215000544762786535022200235646986267655715861136663687268833584319373370806212277764365165024210936127505563077780044446172967341034465955736157812639997021613611139824073413196090993637257782802715278260197652570802957241392696659896441870090217096364557746038056749198966414529129939068897927148170015396744856971653040759512206663129263689011235493838837509291180058136049825236927951726835961962015206904611846148078834006589220003421416282780956845528315528806900524316290074905895950832826283918972260149280538119730487802435228313647395336

推导到这里发现关键是DP[u,1]的递推式，它基本上等于DP[u-1,1]+DP[u-2,1]+“1或0”，而这个累加值是1或0取决于u除以4的余数。所以DP应该每隔四项会比较规律，应该可以有比较简洁的递推公式。

iseemu2009

太复杂了，编程题的核心就是算法。如何对某个问题找到更高效、更简洁的算法对数学旧知识的掌握和新理论的发明都有关系。国外有很多这样启迪思维的题，不是靠什么机械计算就能完成的。邱成桐说，目前欧美那边有80%的数学新理论、前沿知识未曾传到过中国，我相信他说的是真的。