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