堆叠杯子的趣味难题

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. }

复制代码