考慮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,結論正確
證畢