推 MeNeNe :感謝 :) 09/02 10:23
※ 引述《MeNeNe (咪逆逆)》之銘言：
: 1.任取n+1個不同的整數，求證:至少有兩個數的差能被n整除。
n 個數被 n 除的餘數 有 n 種可能(0~n-1)
則取 n+1 個數 必有 2 個數被 n 除的餘數相同
取這兩個數之差必能被 n 整除 !
: 2.從1,2,3....,99,100任取51個數，其中總有一個數是另一個數的倍數。
這題我解推廣型 : 2n 個數中 任取 n+1 個數 必有 2 個數可被另一方整除
考慮兩集合
A = {1,2,3,...,2n} 與 B = {1,3,5,...,2n-1}
對於所有 a 屬於 A 皆存在 b 屬於 B 使得 a = b*(2^k) , k >= 0
在 A 中任取 n+1 個數使得 Ai = Bi(2^ki) , i = 1~n+1
Ai 有 n+1 種 而 Bi 只有 n 種
故必有 Ai = b(2^ki) , Aj = b(2^kj) , i≠j
使得 Ai | Aj 或 Aj | Ai
: 3.任給n個數，必能從中取出3個數，使得他們的和能被3整除，求n的最小值。
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.198.131.51
※ 編輯: svanavs 來自: 60.198.131.51 (09/01 23:56)