推 JohnMash :excellent 09/01 08:31
※ 編輯: bineapple 來自: 123.192.216.62 (09/01 19:10)
※ 編輯: bineapple 來自: 123.192.216.62 (09/01 19:10)
→ snew1209 :請問鴿籠原理那邊 {1,2,3,4,5} 取到1,3,5的狀況 09/03 13:53
※ 引述《s6423579 (DT)》之銘言：
: 請教一下各位高手了...真的想不出來。
: 若S為一集合，S={1,2,.....,25}，若A為S的一個子集合，
: 且A中任兩元素之差均不為完全平方數，試問集合A中最多有幾個元素?
: 有好構想的提供一下吧!!
因為有{1 3 6 8 11 13 16 18 21 23}
可知A至少可有10個
（找出這個例的方法為消去法 把S中最小數加上1,4,9,16後的數消去
然後重複這個步奏
也就是先把1+1 1+4 1+9 1+16消去
剩下最小的是3 再把3+1 3+4 3+9 3+16消去...最後就得到上面那個例子）
若A有11個元素
考慮以下5個集合
{1~5},...,{21~25}
根據鴿籠原理
得知上面有一個集合裡至少有3個A中的元素
不難看出若上面五個集合中任一個若要取出3個元素
則一定有兩個元素相差1或4
故和A的定義矛盾
因此得知A最多可有10個
--
Stirling's formula:
1 log(2π) ∞ B_1(t)
logΓ(s)=(s-─)logs-s+────-∫────dt,
2 2 0 s+t
where B_1 is the first Bernoulli function.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.192.216.62
※ 編輯: bineapple 來自: 123.192.216.62 (09/01 04:34)