推 hau : 謝謝！你給的例子跟答案給的例子一樣！ 03/20 11:19
推 pleasure19 : 厲害！ 03/20 13:19
※ 引述《hau (小豪)》之銘言：
: 題目：
: 設集合S={ 1,2,3,4,5,……,24,25 }。設S有一子集A，A中任二元素之差均不為完全平方
: 數，則此子集A最多有幾個元素？
: 解答：
: 他的解答直接列出一個例子，說有幾個。
: 問題是他如何得到這個例子？！
: 由S中的元素來看，且1^2=1，不難看出 n(A) ≦ 12
: 接下來……
: 我想知他如何構造出例子，或有其它方法？
我的例子是 {1, 3, 6, 8, 11, 13, 16, 18, 21, 23} 共十個元素
因為 2+2=4, 若選了差 2 的兩數則它們兩邊至少要隔 3 才能再選數
(eg. 若已選 8, 10, 則 6 跟 12 都不能選, 只能選 5 或 13)
由 1 起算, +2 +3 +2 +3 ... 到將超過 25 為止即是上述例子
可以檢查此例子裡亦不存在差 9 及差 16 的兩數, 故符合條件
以下證明 11 個不行
反設存在 11 個元素的集合
同樣將元素排序後求出相鄰兩數的差, 這些差共有十個, 總和至多 24
這些差不能有 1, 所以至少是 2, 這分配了 20 的總和
但餘下的 4 無論如何分配到十個差中都必然存在兩個 2 相鄰
亦即存在差 4 的兩數, 矛盾
--
LPH [acronym]
= Let Program Heal us
-- New Uncyclopedian Dictionary, Minmei Publishing Co.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.39.85
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1426783816.A.5C5.html
※ 編輯: LPH66 (123.195.39.85), 03/20/2015 00:51:02