作者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/cn.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