我想到了...(想好久)
設a1<a2<...<an
找一種排列a1|ab|ac|...|az最長(稱為一組)
接著,aj上面沒有最小的,以aj為首用剩下的數排最長的 (第二組)
....這樣一直排下去
如果<=n個,必有一組超過n+1個元素(請教哥龍)
如果>=n+1個,取每一組最大的元素,必有兩個整除的,矛盾
※ 引述《chaogold (dchaodx)》之銘言：
: 來想想一題吧~
: M是n^2+1個正整數集合
: 任取n+1個
: 都有兩個有整除關係
: 證明
: 可以取出n+1個
: 由小排到大後
: 連徐兩兩都有整除關係
: 即有a_1,a_2.....a_n+1
: a_i|a_i+1
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.167.188.191
※ 編輯: Dawsen 來自: 218.167.188.191 (12/28 13:09)