[其他] 請問兩題證明題

看板Math作者 (YAMASHITA)時間3年前 (2020/07/22 12:03), 編輯推噓1(1推 0噓 15→)
留言16則, 2人參與, 3年前最新討論串1/1
看到兩題問題不知道如何清楚證明， 請問各位神手： (1) 2n+1個男生和n個女生排成一排， 試證：一定可以找到一位男生， 使得他的任意一側， 男生的個數恰是女生個數的兩倍。 (2) n個男生和n個女生圍成一圓圈， 試證：一定可以找到一對不相鄰的男女生， 使得他們牽上一條繩子後，在此繩的任意一側， 男生的個數等於女生的個數。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.138.106.175 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1595390625.A.D90.html
推
07/22 16:31, 3年前 , 1F
(1) 若前 n 人中有 x 男 y 女 在平面上作點 (x,y)
07/22 16:31, 1F
→
07/22 16:32, 3年前 , 2F
則每列對應 (0,0) 到 (2n+1,n) 的捷徑
07/22 16:32, 2F
→
07/22 16:36, 3年前 , 3F
作 L1: x=2y+1, L2: x=2y
07/22 16:36, 3F
→
07/22 16:37, 3年前 , 4F
則從 (0,0) 到 (2n+1,n) 的路 必有一段是
07/22 16:37, 4F
→
07/22 16:38, 3年前 , 5F
從 L2 水平跨到 L1, 取跨後那點的男生即為答案
07/22 16:38, 5F
→
07/22 16:40, 3年前 , 6F
(2) 從某點開始 若前 n 人有 x 男 y 女 標 (n,x-y)
07/22 16:40, 6F
→
07/22 16:41, 3年前 , 7F
則得到 (0,0) 到 (2n,0) 的數列
07/22 16:41, 7F
→
07/22 16:50, 3年前 , 8F
取最低點 當成新的(0,0) 則所有點皆非負
07/22 16:50, 8F
→
07/22 16:51, 3年前 , 9F
(i) 最高 1, 需要 n >= 3, 取任一高度 1 和高度 0
07/22 16:51, 9F
→
07/22 16:52, 3年前 , 10F
不鄉鄰即可
07/22 16:52, 10F
→
07/22 16:53, 3年前 , 11F
(ii) 最高 >= 2, 有兩個以上最高 取第一個最高點當
07/22 16:53, 11F
→
07/22 16:53, 3年前 , 12F
男生 第二個最高點下一位當女生
07/22 16:53, 12F
→
07/22 16:54, 3年前 , 13F
(iii) 最高 >= 2, 只有一個最高點, 需要 n >= 3
07/22 16:54, 13F
→
07/22 16:55, 3年前 , 14F
取最高點前一點(高度h-1)當男生
07/22 16:55, 14F
→
07/22 16:56, 3年前 , 15F
最高點後 必有一點高度 h-2 且前一點是 h-1 當女生
07/22 16:56, 15F
→
07/22 23:10, 3年前 , 16F
T大真是厲害，感謝
07/22 23:10, 16F
‣ 更多 TOMOHISA 的文章
文章代碼(AID): #1V5xgXsG (Math)