免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 求大神解题!

本帖最后由 zhenglian1 于 2021-4-15 22:03 编辑

求大神帮忙解题,谢谢!
111.jpg
2021-4-15 21:59
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

这种题想好想,写难写……

首先考虑下图的情形:
QQ截图20210416234834.png
2021-4-17 00:28

图中的 `A_n` 及 `B_n` 表示由 `S` 到该点处的走法数,注意最右边是不连的。
首先看 `n=1`,即
QQ截图20210416234821.png
2021-4-17 00:28
,显然 `A_1=B_1=1`。

当由 `n` 延长至 `n+1` 时,即在右边接一个 `\sqsubset`,如下图:
QQ截图20210416235014.png
2021-4-17 00:30

要走到 `A_{n+1}`,无论是从 `A_n` 出发还是从 `B_n` 出发,都是只有一种走法,所以 `A_{n+1}=A_n+B_n`,对 `B_{n+1}` 同理,即 `A_{n+1}=B_{n+1}=A_n+B_n`,这在前 19 格都成立,所以 `A_{19}=B_{19}=2^{18}`。

来到拐弯的地方,情况就不同了,如下图:
QQ截图20210417001350.png
2021-4-17 00:38

我们来枚举一下由 19 到 21 的走法:

要走到 `A_{21}`,如果由 `A_{19}` 出发,有以下三种走法:
QQ截图20210417001447.png
2021-4-17 00:41
QQ截图20210417001504.png
2021-4-17 00:41
QQ截图20210417001529.png
2021-4-17 00:41

如果由 `B_{19}` 出发,有以下三种走法:
QQ截图20210417001602.png
2021-4-17 00:42
QQ截图20210417001618.png
2021-4-17 00:42
QQ截图20210417001647.png
2021-4-17 00:42

所以有 `A_{21}=3A_{19}+3B_{19}=6\times2^{18}`;

要走到 `B_{21}`,如果由 `A_{19}` 出发,有以下四种走法:
QQ截图20210417001706.png
2021-4-17 00:45
QQ截图20210417001741.png
2021-4-17 00:45
QQ截图20210417001802.png
2021-4-17 00:45
QQ截图20210417001943.png
2021-4-17 00:45

如果由 `B_{19}` 出发,有以下三种走法:
QQ截图20210417004602.png
2021-4-17 00:46
QQ截图20210417004624.png
2021-4-17 00:47
QQ截图20210417004643.png
2021-4-17 00:47

所以有 `B_{21}=4A_{19}+3B_{19}=7\times2^{18}`。

打破平衡的原因就是那唯一一条能往左走的路线。

回到直路,也就是回到 `A_{n+1}=B_{n+1}=A_n+B_n` 的时间,所以 `A_{22}=B_{22}=13\times2^{18}`,直到 `A_{39}=B_{39}=13\times2^{35}`,最后补回最右边的竖线,所以到 `F` 的走法总数为 `A_{39}+B_{39}=13\times2^{36}`。
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

这种题想好想,写难写……

首先考虑下图的情形:

图中的 `A_n` 及 `B_n` 表示由 `S` 到该点处的走法数, ...
kuing 发表于 2021-4-17 01:02

解释的非常清楚详细,大神,请接受我的膝盖!

TOP

有没有可能补成大矩形,然后用减法?

TOP

回复 4# isee

太难了……

TOP

@编程大神,能否用程序枚举验证呢?当然不是验证原题,数字太大了,改小一点,比如把 20 改成 3

补充:
如果前半段为 `n` 格(`n\geqslant2`),后半段为 `m` 格(`m\geqslant3`),按 2# 的分析:
`A,B_{n-1}=2^{n-2}`, `A_{n+1}=6\times2^{n-2}`, `B_{n+1}=7\times2^{n-2}`, `A,B_{n+2}=13\times2^{n-2}`, `A,B_{n+m-1}=13\times2^{n+m-5}`,所以走法总数为 `13\times2^{n+m-4}`。(其实 `m=2` 也符合此式)
当 `m=n=3` 时结果为是 52。

TOP

本帖最后由 tommywong 于 2021-4-18 08:55 编辑

之前玩過程序走遍所有路徑
下圖中,從A 出發,先走向B,最後回到A,不重複地走遍所有路段,有幾種不同路徑?
http://www.mathchina.com/bbs/for ... =1950355&extra=

2104152159fdb6435c7412e5e7.jpg
2021-4-17 15:25
  1. clc;clear;
  2. A=zeros(10,10);
  3. A(1,2)=1;A(1,4)=1;
  4. A(2,3)=1;A(2,4)=1;
  5. A(3,5)=1;A(3,6)=1;
  6. A(4,5)=1;
  7. A(5,6)=1;A(5,8)=1;
  8. A(6,7)=1;A(6,8)=1;
  9. A(7,9)=1;A(7,10)=1;
  10. A(8,9)=1;
  11. A(9,10)=1;
  12. A=A+A';
  13. a=1;
  14. for k=1:sum(sum(A))/2
  15.     s(k)=0;
  16.     T=[];
  17.     n=size(a,1);
  18.     for i=1:n
  19.         B=A;
  20.         if(k>1)
  21.             for K=1:k-1
  22.                 B(a(i,K),a(i,K+1))=B(a(i,K),a(i,K+1))-1;
  23.                 B(a(i,K+1),a(i,K))=B(a(i,K+1),a(i,K))-1;
  24.             end
  25.         end
  26.         for j=1:10
  27.             if(B(a(i,k),j)==1 && sum(a(i,:)==j)==0)
  28.                 t=[a(i,:),j];
  29.                 T=[T;t];
  30.                 if(j==10)
  31.                     s(k)=s(k)+1;
  32.                     if(k==5)
  33.                         disp(t);
  34.                     end
  35.                 end
  36.             end
  37.         end
  38.     end
  39.     a=T;
  40. end
  41. s
  42. sum(s)
复制代码
我讓程序輸出了所有5步路徑
     1     2     3     6     7    10

     1     4     5     6     7    10

     1     4     5     8     9    10

1至15步的路徑數
s=0     0     0     0     3    12    19    14     4     0     0     0     0     0

所有路徑數
sum(s)=52
现充已死,エロ当立。
维基用户页:https://zh.wikipedia.org/wiki/User:Tttfffkkk/
Notable algebra methods:https://artofproblemsolving.com/community/c728438
《方幂和及其推广和式》 数学学习与研究2016.

TOP

回复 7# tommywong

虽然程序的核心部分还看不懂,不过为了便于验证其他数字,还是试着把前面那些 A...=1 改进一下……

首先简化一下图形,注意到
QQ截图20210418015251.png
2021-4-18 01:55
等价于
QQ截图20210418015321.png
2021-4-18 01:55
等价于
QQ截图20210418015342.png
2021-4-18 01:55
,所以图形可以画成这样:
QQ截图20210418020529.png
2021-4-18 02:06

顶点的编号如上图规律,这样就可以用 for 来写那些 A...=1 了,中间的斜线是 A(2n-2,2n+1),最后的点是 2(n+m-1),最少步数是其一半且必为三条。
  1. clc;clear;
  2. n1=4;
  3. n2=4;
  4. n3=(n1+n2-1)*2;
  5. A=zeros(n3,n3);
  6. A(1,2)=1;A(n3-1,n3)=1;A(n1*2-2,n1*2+1)=1;
  7. for l=1:2:n3-3
  8.     A(l,l+2)=1;A(l+1,l+3)=1;A(l+1,l+2)=1;
  9. end
  10. A=A+A';
  11. a=1;
  12. for k=1:sum(sum(A))/2
  13.     s(k)=0;
  14.     T=[];
  15.     n=size(a,1);
  16.     for i=1:n
  17.         B=A;
  18.         if(k>1)
  19.             for K=1:k-1
  20.                 B(a(i,K),a(i,K+1))=B(a(i,K),a(i,K+1))-1;
  21.                 B(a(i,K+1),a(i,K))=B(a(i,K+1),a(i,K))-1;
  22.             end
  23.         end
  24.         for j=1:n3
  25.             if(B(a(i,k),j)==1 && sum(a(i,:)==j)==0)
  26.                 t=[a(i,:),j];
  27.                 T=[T;t];
  28.                 if(j==n3)
  29.                     s(k)=s(k)+1;
  30.                     if(k==n3/2)
  31.                         disp(t);
  32.                     end
  33.                 end
  34.             end
  35.         end
  36.     end
  37.     a=T;
  38. end
  39. s
  40. sum(s)
  41. 13*2^(n1+n2-4)
复制代码
开头的 n1,n2 就是 n,m(因为中间用了 n 所以只好换),更改它们,最后输出的两个数如果相同就是 6# 的公式对了。
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

回复 8# kuing

     1     2     4     6     8    10    12    14

     1     2     4     6     9    11    13    14

     1     3     5     7     9    11    13    14

s=   0     0     0     0     0     0     3    18    46    64    51    22     4     0     0     0     0     0     0     0     0
sum(s)=208
13*2^(n1+n2-4)=208

TOP

本帖最后由 tommywong 于 2021-4-18 04:34 编辑

循環k會考慮每一步
循環i會考慮每一行a
這是頭三次循環k輸出的a

a =

     1     2
     1     3


a =

     1     2     3
     1     2     4
     1     3     2
     1     3     5


a =

     1     2     3     5
     1     2     4     5
     1     2     4     6
     1     3     2     4
     1     3     5     4
     1     3     5     7

循環K扣掉該行a已被消耗的路徑
k=1時a=1還沒有消耗路徑所以略過循環K
循環j會處理該行a的下一步j點
通過條件會有j,不通過條件會冇j
通過條件B(a(i,k),j)==1代表該行a到達的點與j連通,這裡會讓a走向可行路徑
通過條件sum(a(i,:)==j)==0代表該行a沒有j,這裡會讓點不重複到達
j==n3時該行有j的a已經到達終點

TOP

返回列表 回复 发帖