作者TimcApple (肥鵝)
看板Math
標題[其他] TC題 (23) 排列組合
時間Thu May 28 23:20:17 2020
Problem 23
某街道圖如下，相鄰路口皆距離 100 公尺
https://i.imgur.com/O6QKNU8.jpg
小明想要畫一條路徑，作為單車活動路線
(1) 起點與終點皆在 A 路口
(2) 總長 2 公里
(3) 每個路口只能直走或右轉
(4) A 以外的路口，不能經過兩次或以上
請問共有多少種不同路徑可選擇？
========================================================
普通的排組題目ow o
特別喜歡這類型題目的某些細節
雖然一般是不太能直接從題目看出來的就是
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.160.4 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1590679219.A.D39.html
1F：推 arthurduh1 : 由 1, 3, 4 知路徑必為凸多邊形，也就只能是長方形 05/29 01:33
2F：→ arthurduh1 : 對於任意經過 A 的長方形，路徑方向也是唯一的 05/29 01:33
3F：→ arthurduh1 : 接下來就按照長寬一一計算符合條件的長方形個數 05/29 01:33
4F：→ arthurduh1 : 2+4+6+6+3+2+2 = 25 05/29 01:33
5F：推 arthurduh1 : 4. 的排除法會造成要討論回到 A 點多次的情況 05/29 01:49
6F：→ arthurduh1 : 不過因為網格形狀的關係，終究只能回 A 點一次 05/29 01:50
7F：推 arthurduh1 : 發現漏考慮了 A 點是凹點的情況(冏 05/29 02:38
8F：推 arthurduh1 : A 點是凹點的情況： 05/29 02:49
9F：→ arthurduh1 : 可以把內凹部分外翻成長方形，其周長不變 05/29 02:49
10F：→ arthurduh1 : 每個內部包含 A 的長方形共有四種翻法 05/29 02:49
11F：→ arthurduh1 : 此種長方形右上角的頂點必位於街道右上方 05/29 02:49
12F：→ arthurduh1 : 2x3 的格子點，可列舉出共有 05/29 02:49
13F：→ arthurduh1 : 5+5+4+4+5+5 = 28 個 05/29 02:50
14F：→ arthurduh1 : 故可選擇的路徑共有 28*4 + 25 = 137 種 05/29 02:50
15F：推 arthurduh1 : 但這種情況就有可能回到 A 點兩次了(倒地 05/29 03:36
16F：推 arthurduh1 : 這種情況算的是矩形中包含過 A 的矩形，周長互補 05/29 04:20
17F：→ arthurduh1 : 有 34 種，可選路徑數增加至 171 條 05/29 04:20
18F：推 arthurduh1 : (更正：矩形中包含頂點是 A 的矩形，且不相交 05/29 09:21
19F：→ arthurduh1 : 然後內外路徑可分先後走，所以是增加了 34*2 種 05/29 09:21
20F：→ arthurduh1 : 共 205 種可能 05/29 09:21
21F：→ TimcApple : 100P 終於XD 05/29 11:11
22F：推 arthurduh1 : 我怎麼覺得還是有漏算XDD 05/29 11:12
23F：→ TimcApple : 結果沒有中陷阱嘛（喂 05/29 11:12
24F：→ arthurduh1 : 目前正在透過斜線的方式想辦法化簡列舉過程 05/29 11:12
25F：→ arthurduh1 : 不知道有沒有更好的化簡方式XDD 05/29 11:13
26F：→ arthurduh1 : 哦哦沒問題，驗算過是一樣的 OwO 05/29 11:22