推 haha31:整除 04/02 15:57
Show that given a set of n+1 positive integer, none exceeding 2n, there
is at least one integer in this set that divides another integer in the set.
疑問: divides 是指 "整除another" 還是 "被another除"?
以下是我參考類題的證法: 請大家幫我看看
pf: 把1到2n依下列方式分成n組 : [1]={1,2,4,8,...},[3]={3,6,12,24,...}
[5]={5,10,20,40,...},...,[k]={(2^t)*k | t≧0,t屬於N},k:odd,...,
[2n-1]={2n-1} 由鴿籠定理知, 取n+1個數為一個集合, 必有兩數在同一組
所以至少有一個整數會被另一個整數整除
a
以上是參考某題的答案 而某題是問 必有兩數a,b 使得 ── =2^k, k屬於N
b
說實在我也沒想到這樣分組 只是這樣分好像OK....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.32.102.8