作者TOMOHISA (YAMASHITA)
看板Math
标题[其他] 请问两题证明题
时间Wed Jul 22 12:03:43 2020
看到两题问题不知道如何清楚证明，
请问各位神手：
(1) 2n+1个男生和n个女生排成一排，
试证：一定可以找到一位男生，
使得他的任意一侧，
男生的个数恰是女生个数的两倍。
(2) n个男生和n个女生围成一圆圈，
试证：一定可以找到一对不相邻的男女生，
使得他们牵上一条绳子後，在此绳的任意一侧，
男生的个数等於女生的个数。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.138.106.175 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1595390625.A.D90.html
1F：推 TimcApple : (1) 若前 n 人中有 x 男 y 女 在平面上作点 (x,y) 07/22 16:31
2F：→ TimcApple : 则每列对应 (0,0) 到 (2n+1,n) 的捷径 07/22 16:32
3F：→ TimcApple : 作 L1: x=2y+1, L2: x=2y 07/22 16:36
4F：→ TimcApple : 则从 (0,0) 到 (2n+1,n) 的路 必有一段是 07/22 16:37
5F：→ TimcApple : 从 L2 水平跨到 L1, 取跨後那点的男生即为答案 07/22 16:38
6F：→ TimcApple : (2) 从某点开始 若前 n 人有 x 男 y 女 标 (n,x-y) 07/22 16:40
7F：→ TimcApple : 则得到 (0,0) 到 (2n,0) 的数列 07/22 16:41
8F：→ TimcApple : 取最低点 当成新的(0,0) 则所有点皆非负 07/22 16:50
9F：→ TimcApple : (i) 最高 1, 需要 n >= 3, 取任一高度 1 和高度 0 07/22 16:51
10F：→ TimcApple : 不乡邻即可 07/22 16:52
11F：→ TimcApple : (ii) 最高 >= 2, 有两个以上最高 取第一个最高点当 07/22 16:53
12F：→ TimcApple : 男生 第二个最高点下一位当女生 07/22 16:53
13F：→ TimcApple : (iii) 最高 >= 2, 只有一个最高点, 需要 n >= 3 07/22 16:54
14F：→ TimcApple : 取最高点前一点(高度h-1)当男生 07/22 16:55
15F：→ TimcApple : 最高点後 必有一点高度 h-2 且前一点是 h-1 当女生 07/22 16:56
16F：→ TOMOHISA : T大真是厉害，感谢 07/22 23:10