求證:在不超過2n的任意n+1個自然數中,至少有一個數是另一個 數的倍數國中 回應 笑哥 Re: 證明題 2008-06-14 20:14 1~2n中含n個偶數,n個奇數 取出之n+1個數必至少有一偶數和一奇數 設任取出n+1個數中有k個偶數,n+1-k個奇數,0 < k < n+1 則此k個偶數,必為1~2n中k個奇數之2倍,若欲避開此k個奇數,使其不成立 則剩下n-k個奇數可挑,但必須挑出n-k+1個奇數, 無可避免必挑出一奇數使其中一偶數為其兩倍 因此取出的數中至少有一個數是另一個數的倍數成立 tw1991x Re: 證明題 2008-06-15 06:33 若取一數為奇數(m) 令奇數為k+1個,偶數為k個,a、b皆為奇數 k+1+k=m 2k+1=ab(成立) 若取一數為偶數 令奇數為k個,偶數為k個 2k=此數(成立) ※任何數皆為1的倍數,所以成立。
笑哥 Re: 證明題 2008-06-14 20:14 1~2n中含n個偶數,n個奇數 取出之n+1個數必至少有一偶數和一奇數 設任取出n+1個數中有k個偶數,n+1-k個奇數,0 < k < n+1 則此k個偶數,必為1~2n中k個奇數之2倍,若欲避開此k個奇數,使其不成立 則剩下n-k個奇數可挑,但必須挑出n-k+1個奇數, 無可避免必挑出一奇數使其中一偶數為其兩倍 因此取出的數中至少有一個數是另一個數的倍數成立
tw1991x Re: 證明題 2008-06-15 06:33 若取一數為奇數(m) 令奇數為k+1個,偶數為k個,a、b皆為奇數 k+1+k=m 2k+1=ab(成立) 若取一數為偶數 令奇數為k個,偶數為k個 2k=此數(成立) ※任何數皆為1的倍數,所以成立。
回應
笑哥
Re: 證明題
2008-06-14 20:14取出之n+1個數必至少有一偶數和一奇數
設任取出n+1個數中有k個偶數,n+1-k個奇數,0 < k < n+1
則此k個偶數,必為1~2n中k個奇數之2倍,若欲避開此k個奇數,使其不成立
則剩下n-k個奇數可挑,但必須挑出n-k+1個奇數,
無可避免必挑出一奇數使其中一偶數為其兩倍
因此取出的數中至少有一個數是另一個數的倍數成立
tw1991x
Re: 證明題
2008-06-15 06:33令奇數為k+1個,偶數為k個,a、b皆為奇數
k+1+k=m
2k+1=ab(成立)
若取一數為偶數
令奇數為k個,偶數為k個
2k=此數(成立)
※任何數皆為1的倍數,所以成立。