[中學] 每一點都要經過

看板Math作者 (薩坨十二惡皆空)時間4月前 (2025/08/07 20:51), 編輯推噓0(0推 0噓 21→)
留言21則, 3人參與, 4月前最新討論串1/2 (看更多)
三列，每列八個點。 共24個點以棋盤式排列。 由左下角點作一路徑抵達右上角點， （每步只能向上下左右走） 且每一點皆要經過一次。 則有幾種不同的路徑？ 拜託各位了！感恩！ -- Sent from nPTT on my iPhone 12 mini -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.168.0.247 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1754571110.A.1B0.html
→
08/07 22:27, 4月前 , 1F
64?
08/07 22:27, 1F
→
08/07 22:32, 4月前 , 2F
一開始只能選右跟上，沒有選上的話後面也都不能選下
08/07 22:32, 2F
→
08/07 22:33, 4月前 , 3F
而當你第一次選上之後整個棋盤會被一意地縮小成較小
08/07 22:33, 3F
→
08/07 22:34, 4月前 , 4F
的棋盤，只是起點跟終點變成同側的狀況
08/07 22:34, 4F
→
08/07 22:36, 4月前 , 5F
所以就直接同時討論同側跟異側的小棋盤再推廣
08/07 22:36, 5F
→
08/07 22:37, 4月前 , 6F
可知n>2時同側跟異側路徑數都是2^(n-2)
08/07 22:37, 6F
→
08/07 22:37, 4月前 , 7F
應該有比較好的辦法只是我可能忘了
08/07 22:37, 7F
→
08/07 22:55, 4月前 , 8F
感謝
08/07 22:55, 8F
→
08/08 15:16, 4月前 , 9F
倒過來分析可能比較簡明
08/08 15:16, 9F
→
08/08 15:17, 4月前 , 10F
先定義一下符號，{a_n}是3*n的棋盤起終點異側的方法
08/08 15:17, 10F
→
08/08 15:17, 4月前 , 11F
數，{s_n}是同側的方法（路徑）數
08/08 15:17, 11F
→
08/08 15:19, 4月前 , 12F
則a_n將會是倒數一步為終點左側以及倒數一步為終點
08/08 15:19, 12F
→
08/08 15:20, 4月前 , 13F
下側的路徑數的和，而其中左側路徑數實際上會等於
08/08 15:20, 13F
→
08/08 15:22, 4月前 , 14F
a_(n-1)，因為多的那兩點有且只有唯一的走法走完；
08/08 15:22, 14F
→
08/08 15:24, 4月前 , 15F
下側路徑則會是s_(n-1) （以上討論基於n>=2時）
08/08 15:24, 15F
→
08/08 15:25, 4月前 , 16F
另外由相似的討論可以知道s_n也一樣是s_(n-1)+
08/08 15:25, 16F
→
08/08 15:25, 4月前 , 17F
a_(n-1)，所以可以知道s_n=a_n，進一步可以知道
08/08 15:25, 17F
→
08/08 15:28, 4月前 , 18F
當n>2時a_n=2*a_(n-1)，又因a_2=1，所以a_n=2^(n-2)
08/08 15:28, 18F
→
08/08 19:17, 4月前 , 19F
這是一筆畫問題嗎？
08/08 19:17, 19F
→
08/08 20:19, 4月前 , 20F
如果不是每點經過且只經過一次應該沒辦法問
08/08 20:19, 20F
→
08/08 20:19, 4月前 , 21F
就是漢米頓路徑
08/08 20:19, 21F
‣ 更多 mj813 的文章
文章代碼(AID): #1ebA5c6m (Math)
‣ 更多 mj813 的文章
文章代碼(AID): #1ebA5c6m (Math)