论坛 › 难题征解 › 堆叠杯子的趣味难题

iseemu2009 发表于 昨天 11:17

堆叠杯子的趣味难题

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

mathe 发表于 昨天 12:18

这个相当于直线排列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).

四来 发表于 昨天 12:24

这样算一种还是两种？

mathe 发表于 昨天 16:36

我们记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程序

dumpr(n)=
{
    local(R,s);
    R=matrix(n,n);
    R=1;
    R=1;
    R=2;R=1;
    for(u=4,n,
       R=R+R+R;
       R=1;
       for(v=3,u-1,
          R=R;
       );
       s=0;
       for(v=1,u-1,s+=R);
       print("S[",u,"]=",2*s);
    );
}


得到结果如下
S=12
S=20
S=34
S=56
S=88
S=136
S=208
S=314
S=470
S=700
S=1038
S=1534
S=2262
S=3330
S=4896
S=7192
S=10558
当然如果继续计算到S也很容易，只是数值会超级大

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

iseemu2009 发表于 昨天 19:13

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

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

iseemu2009 发表于 昨天 19:16

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

mathe 发表于 昨天 19:57

明白了，两个模型还是略有不同，所以本题模型处理起来要复杂一些，但是计算量应该类似。
我们用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 发表于 昨天 22:28

S=6
S=12
S=16
S=22
S=36
S=58
S=82
S=114
S=174
S=266
S=382
S=548
S=816
S=1212
S=1762
S=2566
S=3780
S=5560
S=8128
S=11892
S=17454
S=25604
S=37498
S=54932
S=80538
S=118062
S=172996
S=253510
S=371574
S=544600
S=798112
S=1169658
S=1714260
S=2512406
S=3682066
S=5396294
S=7908702
S=11590806
S=16987102
S=24895768
S=36486576
S=53473720
S=78369490
S=114856026
S=168329748
S=246699284
S=361555312
S=529885016
S=776584302
S=1138139664
S=1668024682
S=2444608936
S=3582748602
S=5250773338
S=7695382276
S=11278130826
S=16528904166
S=24224286500
S=35502417328
S=52031321438
S=76255607940
S=111758025330
S=163789346770
S=240044954650
S=351802979982
S=515592326818
S=755637281470
S=1107440261388
S=1623032588208
S=2378669869748
S=3486110131138
S=5109142719278
S=7487812589028
S=10973922720240
S=16083065439520
S=23570878028476
S=34544800748718
S=50627866188316
S=74198744216794
S=108743544965436
S=159371411153754
S=233570155370630
S=342313700336068
S=501685111489742
S=735255266860374
S=1077568967196528
S=1579254078686272
S=2314509345546562
S=3392078312743092
S=4971332391429454
S=7285841736976018
S=10677920049719022
S=15649252441148478
S=22935094178124590
S=33613014227843614
S=49262266668992000
S=72197360847116592
S=105810375074960304
...
S=26962901013997007773476449840406160338483621262752268591326543606162290720748003129661220722119075977873544416448534677592402973194126252297783679735507922650088522700
dumpr2(n)=
{
    local(UP,UM,DP,DM,s);
    UP=matrix(n,n);UM=matrix(n,n);DP=matrix(n,n);DM=matrix(n,n);
    UM=DM=1;DP=UP=1;
    UP=0;UP=0; DP=1;DP=0;
    UM=0;UM=1; DM=0; DM=0;
    for(u=3,n,
         UP=DP+DM;         UM=0;
         DP=DP+UP+UM;         DM=0;
         for(v=2,u-1,
             if((u-v)%4==0, UP=UM);
             if((u-v)%4==1, UP=0);
             if((u-v)%4==2, UP=0);
             if((u-v)%4==3, UP=DM);
             if((v-1)%4==0, UM=0);
             if((v-1)%4==1, UM=DP);
             if((v-1)%4==2, UM=UP);
             if((v-1)%4==3, UM=0);
             if((u-v)%4==0, DP=0);
             if((u-v)%4==1, DP=UM);
             if((u-v)%4==2, DP=DM);
             if((u-v)%4==3, DP=0);
             if((v-1)%4==0, DM=DP);
             if((v-1)%4==1, DM=0);
             if((v-1)%4==2, DM=0);
             if((v-1)%4==3, DM=UP);
         );
       UP=0; DP=0;
       UM=UM+DP+DM;
       DM=UP+UM;
         s=0; for(v=1,u, s+=UP+DP+UM+DM);
         print("S[",u,"]=",s);
    )
}

查看完整版本: 堆叠杯子的趣味难题