[理工] 97 台大電機 離散 鴿籠
作者: jerry900287 (滷蛋) 2017-03-10 00:23:05
如圖
![]()
我的作法是將他切割成 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?
我的作法是將他切割成 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?
作者: vcyc (維克多) 2017-03-10 08:53:00
你前面的想法應該是對的 他題目就是要求集合S中的最小數目子集S'(大小為K)滿足任意S'中只要大小為K就可以找到兩個互斥的子集M,N(大小為2)且M N中各自元素和為9吧
作者: shownlin (哈哈阿喔) 2017-03-10 10:56:00
應該是子集的子集吧？子集的大小最少要多少 才會包含兩個互斥子集元素和為9順帶一提這題是ucsd的考題因爲取子集的動作相當於你在S的元素中任取k個元素出來組成集合解讀成「最少要從s取k個元素」兩種作法是一樣的 所以解讀不出來也是會答對