※ 引述《jknm0510a (Kang)》之銘言:
: 1. Show that at least 19 cables are needed for connecting eight computers to
: four printers such that four computers can directly access four different
: printer at the same time.
: 2. If 100 integers are select from the set S={1,2,3,....200}, then there are
: two integers such that one divides the other. (T or F)
: Ans: F
let x 屬於 S
由算數基本定理知 x = 2^k * y (y是某個奇數)
則 1<=y<=199 總共100個pigeonhole
所以當取101個數字時 至少會有兩個數字 a,b 會有一樣的 y
a= 2^k1 * y , b= 2^k2 * y
即 a|b or b|a
: 第二題我不知道為什麼為F,正確答案是必須取101個數字,所以想請強者證明一下
: 另外鴿籠原理真的好難阿.......沒想到一個簡單到不行的直覺性定理可以那麼難...
: 離散和線代完全不一樣,離散連題目都有些看不懂了..使用公式也需要思考和技巧
: 完全想不到要那樣子做,有沒有大大能說明一下離散題目的思考方式阿...
: 謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.104.186.150