[理工] 97 台大電機 離散 鴿籠

[jerry900287 ()]

如圖 http://i.imgur.com/JwKsw5Z.png

我的作法是將他切割成 5 個子集

{0,9} {1,8} {2,7} {3,6} {4,5}

那麼當取7個數的時候的時候必有4個數{x1,x2}{y1,y2}

x1 + x2 = y1 + y2 = 9 了

所以答案為 (C) 7


有點不是很確定..

雖然答案是 7 但是詳解沒給做法

所以問一下大大們的看法

因為我對他裡面的一句"any subset of S of size K contains..."有點疑惑

這邊的size K 是指甚麼?? 如果根據他後面的 "disjoint subsets of size two"

感覺是集合大小為 K ?!

整個翻譯起來又有點怪QQ?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.121.57
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1489076592.A.2A0.html
→ vcyc: 你前面的想法應該是對的 他題目就是要求集合S中的最小數目子
→ vcyc: 集S'(大小為K)滿足任意S'中只要大小為K就可以找到兩個互斥
→ vcyc: 的子集M,N(大小為2)且M N中各自元素和為9吧
推 shownlin: 應該是子集的子集吧？
推 shownlin: 子集的大小最少要多少 才會包含兩個互斥子集元素和為9
→ shownlin: 順帶一提這題是ucsd的考題
→ shownlin: 因爲取子集的動作相當於你在S的元素中任取k個元素出來
→ shownlin: 組成集合解讀成「最少要從s取k個元素」
→ shownlin: 兩種作法是一樣的 所以解讀不出來也是會答對
好的 我了解惹~~ 感謝
※ 編輯: jerry900287 (111.243.100.154), 03/10/2017 21:05:01