YLL討論網

skywalker · 由 **skywalker** 於星期日二月 11, 2007 9:38 am

設n≧4，a₁、a₂、.....a_n是開區間(0,2n)內互不相同的整數，證明存在{a₁,a₂....,a_n}的

一個子集，他的所有元素之和被2n整除

宇智波鼬 · 由 **宇智波鼬** 於星期日二月 11, 2007 7:59 pm

0<a_k<2n
則a_k可以是1,2,3,...,2n-2,2n-1.
共2n-1種.
將(1,2n-1) (2,2n-2) (3,2n-3)...共n-1組.
若我們挑的n個數中所有數均屬這些組別所形成之集合,
則根據鴿籠原理便可輕易得出有二個數和為2n.
若所挑選出之n個數沒有任何兩數屬於同一組別,則它們必為:
1,2,3,....,n-1,n.
則1+(n-1)+n=2n, 2+(n-2)+n=2n, 3+(n-3)+n=2n,...
用此方法即可使題目要求成立.

還有一種情況便是,
1,2,3,....,n-1,n將<n的某些數i,j,k...替換成n+k(+j,+i)也能使所挑選出之n個數沒有任何兩數屬於同一組別.
此時設>n的數中最小的為:n+m. 則必須要有n-m-1這個數存在.(否則n+m非最小)
1+(n-m-1)+(n+m)=2n. 所以仍能使題目成立.

亞斯 · 由亞斯於星期二二月 13, 2007 10:31 am

宇智波大最後一段寫法有點問題
假設n=5
取到{1,2,5,6,7}
照你的說法m=1
5-1-1=3不在裡面

galaxylee · 由 **galaxylee** 於星期二二月 13, 2007 5:37 pm

考慮n這個數有否被選到的情形

(1)若n不屬於{a1,a2,...,an}

則a1,a2,...,an分屬於n-1個不同集合{1,2n-1},...{n-1,n+1}

由抽屜原理知其中必有兩個數屬於同一集合

從而兩數和為2n能被2n整除，結論正確

(2)若n屬於{a1,a2,...,an}，不妨設an=n

從a1,a2,...,a(n-1)中任取三個數ai＜aj＜ak

由於ak-ai＜2n，所以aj-ai與ak-aj中至少有一個不被n整除

故a1,a2,...,a(n-1)必有兩數之差不被n整除

假設a2-a1不被n整除(a1＜a2)

令s1=a1，t1=a2，s2=a1+a2，s3=a1+a2+a3，...，s(n-1)=a1+a2+...+a(n-1)

(i)若s1,t1,s2,...,s(n-1)這n個數中有一個被n整除

設此數為kn，若k為偶數，則結論正確

若k為奇數，則將此數加上an=n得總和(k+1)n，結論正確

(ii)若s1,t1,s2,...,s(n-1)這n個數中沒有一個數能被n整除

將這n個數除以n，餘數可能為1,2....,(n-1)

由抽屜原理知必有兩數所得之餘數相等，而這兩數之差為n的倍數

所以此差為a1,a2,...,a(n-1)中某些數的和

設此差為rn，若r為偶數，則結論正確

若r為奇數，則將此差加上an=n得總和(r+1)n，結論正確

證畢

YLL討論網

[數學]四川省數學競賽

[數學]四川省數學競賽