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

[TimcApple (肥鵝)]

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
推 arthurduh1  : 由 1, 3, 4 知路徑必為凸多邊形，也就只能是長方形
→ arthurduh1  : 對於任意經過 A 的長方形，路徑方向也是唯一的
→ arthurduh1  : 接下來就按照長寬一一計算符合條件的長方形個數
→ arthurduh1  : 2+4+6+6+3+2+2 = 25
推 arthurduh1  : 4. 的排除法會造成要討論回到 A 點多次的情況
→ arthurduh1  : 不過因為網格形狀的關係，終究只能回 A 點一次
推 arthurduh1  : 發現漏考慮了 A 點是凹點的情況(冏
推 arthurduh1  : A 點是凹點的情況：
→ arthurduh1  : 可以把內凹部分外翻成長方形，其周長不變
→ arthurduh1  : 每個內部包含 A 的長方形共有四種翻法
→ arthurduh1  : 此種長方形右上角的頂點必位於街道右上方
→ arthurduh1  : 2x3 的格子點，可列舉出共有
→ arthurduh1  : 5+5+4+4+5+5 = 28 個
→ arthurduh1  : 故可選擇的路徑共有 28*4 + 25 = 137 種
推 arthurduh1  : 但這種情況就有可能回到 A 點兩次了(倒地
推 arthurduh1  : 這種情況算的是矩形中包含過 A 的矩形，周長互補
→ arthurduh1  : 有 34 種，可選路徑數增加至 171 條
推 arthurduh1  : (更正：矩形中包含頂點是 A 的矩形，且不相交
→ arthurduh1  :  然後內外路徑可分先後走，所以是增加了 34*2 種
→ arthurduh1  :  共 205 種可能
→ TimcApple   : 100P 終於XD
推 arthurduh1  : 我怎麼覺得還是有漏算XDD
→ TimcApple   : 結果沒有中陷阱嘛（喂
→ arthurduh1  : 目前正在透過斜線的方式想辦法化簡列舉過程
→ arthurduh1  : 不知道有沒有更好的化簡方式XDD
→ arthurduh1  : 哦哦沒問題，驗算過是一樣的 OwO