[理工] 101 暨南 離散 鴿籠

看板Grad-ProbAsk作者時間8年前 (2017/07/21 16:30), 8年前編輯推噓6(6推 0噓 13→)
留言19則, 3人參與, 最新討論串1/1
如圖 http://i.imgur.com/2MJayh6.png
因為這題沒有詳解 想請教各位大大這題該怎麼著手 我的作法是 a1 , a2 , a3 , a4 , a5 同除5後 餘數為 r1 , r2 , r3 , r4 , r5 ,for all 0 <= ri <= 4 然後若 ri 為 0 即得證 若 ri 不為 0 則 r1 , r2 , r3 , r4 , r5 ,for all 1 <= ri <= 4 然後就不會了QQ 有大大有想法嗎?? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.243.103.63 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1500625807.A.29A.html
推
07/21 18:38, , 1F
令所有S_i=a_0+?+a_i
07/21 18:38, 1F
→
07/21 18:38, , 2F
對於所有S_i mod 5 = r_i
07/21 18:38, 2F
→
07/21 18:38, , 3F
若存在r_i=0 for some i 則存在一總和可被整除
07/21 18:38, 3F
→
07/21 18:38, , 4F
若r_i皆≠0則必落在{1,2,3,4}之中
07/21 18:38, 4F
→
07/21 18:38, , 5F
根據鴿籠原理必存在i<j使得r_i=r_j 得證
07/21 18:38, 5F
→
07/21 18:39, , 6F
第一行？是...... App出包
07/21 18:39, 6F
→
07/21 18:40, , 7F
啊是從a_1開始 那就a_0平移到a_1沒看清楚
07/21 18:40, 7F
推
07/22 17:06, , 8F
to S大: 為何存在r_i=r_j就可得證sum為五倍數
07/22 17:06, 8F
→
07/22 17:07, , 9F
？
07/22 17:07, 9F
推
07/22 20:09, , 10F
Case 1 : 若五個remainder都相同時取五個得證
07/22 20:09, 10F
→
07/22 20:10, , 11F
Case 2: 存在至少一個1一個4或一個2一個3得證
07/22 20:10, 11F
推
07/22 20:12, , 12F
Case 3 : 以上皆不成立時代表只有(1 3)(2 3)(2 4)(3 4)這
07/22 20:12, 12F
→
07/22 20:12, , 13F
四種組合
07/22 20:12, 13F
→
07/22 20:13, , 14F
每項組合中必有一數超過3個 然後慢慢加出來得證
07/22 20:13, 14F
→
07/22 20:14, , 15F
像是(1 2)中1*3+2或2*2+1
07/22 20:14, 15F
→
07/22 20:14, , 16F
上面(2 3)打錯是(1 2)
07/22 20:14, 16F
推
07/22 20:29, , 17F
假設r_1=r_3 則S_3-S_1為五的倍數(同餘)
07/22 20:29, 17F
→
07/22 20:29, , 18F
S_3-S_1=(a_1+a_2+a_3)-(a_1)=a_2+a_3
07/22 20:29, 18F
推
07/22 23:07, , 19F
感謝S大, 我瞭解了
07/22 23:07, 19F
!!!!!!感謝上面兩位大大的作法 ※ 編輯: jerry900287 (111.243.103.63), 07/23/2017 00:41:03
‣ 更多 jerry900287 的文章
文章代碼(AID): #1PSRkFAQ (Grad-ProbAsk)