[其他] TC題 (23) 排列組合

看板Math作者 (肥鵝)時間3年前 (2020/05/28 23:20), 編輯推噓8(8推 0噓 18→)
留言26則, 2人參與, 3年前最新討論串1/1
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://www.ptt.cc/bbs/Math/M.1590679219.A.D39.html
推
05/29 01:33, 3年前 , 1F
由 1, 3, 4 知路徑必為凸多邊形，也就只能是長方形
05/29 01:33, 1F
→
05/29 01:33, 3年前 , 2F
對於任意經過 A 的長方形，路徑方向也是唯一的
05/29 01:33, 2F
→
05/29 01:33, 3年前 , 3F
接下來就按照長寬一一計算符合條件的長方形個數
05/29 01:33, 3F
→
05/29 01:33, 3年前 , 4F
2+4+6+6+3+2+2 = 25
05/29 01:33, 4F
推
05/29 01:49, 3年前 , 5F
4. 的排除法會造成要討論回到 A 點多次的情況
05/29 01:49, 5F
→
05/29 01:50, 3年前 , 6F
不過因為網格形狀的關係，終究只能回 A 點一次
05/29 01:50, 6F
推
05/29 02:38, 3年前 , 7F
發現漏考慮了 A 點是凹點的情況(冏
05/29 02:38, 7F
推
05/29 02:49, 3年前 , 8F
A 點是凹點的情況：
05/29 02:49, 8F
→
05/29 02:49, 3年前 , 9F
可以把內凹部分外翻成長方形，其周長不變
05/29 02:49, 9F
→
05/29 02:49, 3年前 , 10F
每個內部包含 A 的長方形共有四種翻法
05/29 02:49, 10F
→
05/29 02:49, 3年前 , 11F
此種長方形右上角的頂點必位於街道右上方
05/29 02:49, 11F
→
05/29 02:49, 3年前 , 12F
2x3 的格子點，可列舉出共有
05/29 02:49, 12F
→
05/29 02:50, 3年前 , 13F
5+5+4+4+5+5 = 28 個
05/29 02:50, 13F
→
05/29 02:50, 3年前 , 14F
故可選擇的路徑共有 28*4 + 25 = 137 種
05/29 02:50, 14F
推
05/29 03:36, 3年前 , 15F
但這種情況就有可能回到 A 點兩次了(倒地
05/29 03:36, 15F
推
05/29 04:20, 3年前 , 16F
這種情況算的是矩形中包含過 A 的矩形，周長互補
05/29 04:20, 16F
→
05/29 04:20, 3年前 , 17F
有 34 種，可選路徑數增加至 171 條
05/29 04:20, 17F
推
05/29 09:21, 3年前 , 18F
(更正：矩形中包含頂點是 A 的矩形，且不相交
05/29 09:21, 18F
→
05/29 09:21, 3年前 , 19F
然後內外路徑可分先後走，所以是增加了 34*2 種
05/29 09:21, 19F
→
05/29 09:21, 3年前 , 20F
共 205 種可能
05/29 09:21, 20F
→
05/29 11:11, 3年前 , 21F
100P 終於XD
05/29 11:11, 21F
推
05/29 11:12, 3年前 , 22F
我怎麼覺得還是有漏算XDD
05/29 11:12, 22F
→
05/29 11:12, 3年前 , 23F
結果沒有中陷阱嘛（喂
05/29 11:12, 23F
→
05/29 11:12, 3年前 , 24F
目前正在透過斜線的方式想辦法化簡列舉過程
05/29 11:12, 24F
→
05/29 11:13, 3年前 , 25F
不知道有沒有更好的化簡方式XDD
05/29 11:13, 25F
→
05/29 11:22, 3年前 , 26F
哦哦沒問題，驗算過是一樣的 OwO
05/29 11:22, 26F
‣ 更多 TimcApple 的文章
文章代碼(AID): #1UpzQpqv (Math)