作者mj813 (萨坨十二恶皆空)
看板Math
标题[中学] 每一点都要经过
时间Thu Aug 7 20:51:48 2025
三列，每列八个点。
共24个点以棋盘式排列。
由左下角点作一路径抵达右上角点，
（每步只能向上下左右走）
且每一点皆要经过一次。
则有几种不同的路径？
拜托各位了！感恩！
--
Sent from nPTT on my iPhone 12 mini
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.168.0.247 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1754571110.A.1B0.html
1F：→ Ricestone : 64? 08/07 22:27
2F：→ Ricestone : 一开始只能选右跟上，没有选上的话後面也都不能选下 08/07 22:32
3F：→ Ricestone : 而当你第一次选上之後整个棋盘会被一意地缩小成较小 08/07 22:33
4F：→ Ricestone : 的棋盘，只是起点跟终点变成同侧的状况 08/07 22:34
5F：→ Ricestone : 所以就直接同时讨论同侧跟异侧的小棋盘再推广 08/07 22:36
6F：→ Ricestone : 可知n>2时同侧跟异侧路径数都是2^(n-2) 08/07 22:37
7F：→ Ricestone : 应该有比较好的办法只是我可能忘了 08/07 22:37
8F：→ mj813 : 感谢 08/07 22:55
9F：→ Ricestone : 倒过来分析可能比较简明 08/08 15:16
10F：→ Ricestone : 先定义一下符号，{a_n}是3*n的棋盘起终点异侧的方法 08/08 15:17
11F：→ Ricestone : 数，{s_n}是同侧的方法（路径）数 08/08 15:17
12F：→ Ricestone : 则a_n将会是倒数一步为终点左侧以及倒数一步为终点 08/08 15:19
13F：→ Ricestone : 下侧的路径数的和，而其中左侧路径数实际上会等於 08/08 15:20
14F：→ Ricestone : a_(n-1)，因为多的那两点有且只有唯一的走法走完； 08/08 15:22
15F：→ Ricestone : 下侧路径则会是s_(n-1) （以上讨论基於n>=2时） 08/08 15:24
16F：→ Ricestone : 另外由相似的讨论可以知道s_n也一样是s_(n-1)+ 08/08 15:25
17F：→ Ricestone : a_(n-1)，所以可以知道s_n=a_n，进一步可以知道 08/08 15:25
18F：→ Ricestone : 当n>2时a_n=2*a_(n-1)，又因a_2=1，所以a_n=2^(n-2) 08/08 15:28
19F：→ musicbox810 : 这是一笔画问题吗？ 08/08 19:17
20F：→ Ricestone : 如果不是每点经过且只经过一次应该没办法问 08/08 20:19
21F：→ Ricestone : 就是汉米顿路径 08/08 20:19