[理工] [離散]101暨大資工(題目我憑印象打的XD)

看板Grad-ProbAsk作者 (考過換帳號)時間12年前 (2012/02/12 00:16), 編輯推噓1(1推 0噓 16→)
留言17則, 3人參與, 最新討論串1/1
考題我是憑印象記的(搞不好有錯XD) 請教大家這題該如何下手 感覺進考場都唸的都忘光光了XD A={a1,a2,a3,a4,a5} 證明存在一個 A的 non empty subset such that 這個non empty 的元素和is a multiple of 5 題目有錯煩請版友幫忙補充>< 感謝大家~ 謝謝^^ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 1.162.203.137
→
02/12 00:27, , 1F
鴿籠可以證出來吧　你分成0,5,{1,4},{2,3}而且條件很鬆
02/12 00:27, 1F
→
02/12 00:32, , 2F
我好像有點想錯XDD在讓我想想
02/12 00:32, 2F
→
02/12 00:37, , 3F
先討論mod之後出現零的情況　則得證
02/12 00:37, 3F
→
02/12 00:38, , 4F
然後討論mod後皆不為0 然後mod出現後的結果不能皆為
02/12 00:38, 4F
→
02/12 00:40, , 5F
同一個數　否則得證然後討論1的情況
02/12 00:40, 5F
→
02/12 00:42, , 6F
出現1後絕對不能出現4 然後2個1時不能出現3,3個1不能出現2
02/12 00:42, 6F
→
02/12 00:44, , 7F
2,3,4也同理可證　
02/12 00:44, 7F
→
02/12 00:46, , 8F
不然可以想成五顆球丟到1,2,3,4的箱子的情況
02/12 00:46, 8F
→
02/12 00:48, , 9F
當丟了一顆球後,必增加一個subset sum的情況
02/12 00:48, 9F
→
02/12 00:49, , 10F
如果沒增加,表出現了subset sum為5的情況
02/12 00:49, 10F
→
02/12 00:50, , 11F
而又有5顆球最後一定會產生subset sum為5的情況
02/12 00:50, 11F
推
02/12 23:52, , 12F
令S_i = (a_1 + ... + a_i) mod 5, for i=1~5
02/12 23:52, 12F
→
02/12 23:53, , 13F
假設S_i in {1, 2, 3, 4}，則根據鴿籠原理
02/12 23:53, 13F
→
02/12 23:54, , 14F
必有S_i = S_j (i<j)，因此S_j - S_i = a_{i+1}+..+a_j
02/12 23:54, 14F
→
02/12 23:54, , 15F
即為5的倍數 QED
02/12 23:54, 15F
→
02/12 23:55, , 16F
這個題目可推廣到任意n個正整數必有非空子集 和為n的倍數
02/12 23:55, 16F
→
09/11 14:55, , 17F
如果沒增加,表出現了s https://daxiv.com
09/11 14:55, 17F
‣ 更多 cisco 的文章
文章代碼(AID): #1FDfHAGs (Grad-ProbAsk)