【問題】兩題組合

[論壇帳號 10]

1.從1,2,3,...,2n中任選n+1個整數，試證：其中必有一數為另一數的因數或倍數。

2.設集合S是由5個小於10的正整數所組成，試證：一定存在S的兩個非空子集合，使得這兩個子集合的元素各自相加後所得的和是相等的。

(我知道這兩題很簡單，沒什麼水準，不過我不知道怎麼看...)

[清風明月 10]

1. 2的倍數有n個

　3的倍數有[2n/3]個

　4的倍數有[n/2]個

　.

　.

　n的倍數有2個

　從n+1到2n的倍數只有1個

取出了n+1個數　根據鴿籠原理得證

[heinsolid 10]

1.

把1~2n全部寫成一個奇數乘上2的某次方，然後整理：

1, 1*2, 1*4, 1*8...(超過2n就停)

3, 3*2, 3*4, 3*8...

5, 5*2, 5*4, 5*8...

......

2n-1

總共分成n類，若要在其中取n+1個數，必有兩個在同一類，顯然同一類的兩個數有因倍數關係。

2.

顯然集合S本身的總和不可能和它的真子集合相同，所以不考慮。

集合S的子集合，除去本身和空集合，有30個(2^5-2)。元素總和範圍是1~30(6+7+8+9)，也30個。

再來證明S的30個非空真子集合的元素總和，不可能是1~30剛好各一個而不重複。

若非如此，1必定屬於S，2也得有，3就不能取，4一定要有，5,6,7不能取，還有兩個元素沒取，但是8,9拿或不拿都不行，矛盾。

[論壇帳號 10]

謝謝學長解答。