Re: [理工] [離散] 數列

[gskman (小魯米)]

沒人證我來證一下好了@@

令n個數 A1 = X1
        A2 = X1+X2
        A3 = X1+X2+X3
           .
           .
        An = X1+ .. +Xn

這樣的話就n相異數,若是n能在這n個數裡找到整除則 得證
若是不行的話,就會產生n個數被Xk除完之後餘數是 {1,..,k-1}
最差情況是k=n (我就只討論k=n,k的餘數個數<=2個相同)
存在i<=j
Ai-1 =X1+X2+....+Xi-1
Aj   =X1+.......+Xj
n除Ai-1 的餘數等於 n除Aj 的餘數,

那就可以找到  n| Aj - Ai-1
也就是        n| Xi + Xi+1 +..+ Xj

※ 引述《vity (逍遙盃-佛得)》之銘言：
: 令X1, X2,..., Xn 為一整數數列。
: 證明：對任一整數k, 1 <= k<= n,
: 存在兩個整數，i 和 j，i <= j
: 使Xk整除 Xi+Xi+1+...+Xj
: 完全不知道怎麼下手...還是硬著頭皮寫點想法
: 反證法:不存在兩個整數i, j 能讓Xk整除
: 令t = Xi+Xi+1+...+Xj
:     = n * Xk + q, n, q屬於N
: 接下來想辦法讓q=0, 就達到矛盾
: ....要求救了

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.77.154
推 vity:謝了 很漂亮的解法
→ gskman:樓上　我想問你一下　題目確定是這樣嗎?? 因為我剛想了一下
→ gskman:如果是被Xk除的話 應該是恆成立才對 感覺比較像是除k才對
→ gskman:難怪我覺得怎麼都沒人證XD
推 vity:你這麼一說...真的是k, 我曾經檢查過Xk不是恆成立...
→ gskman:恆成立阿 取i=j=k就好了 Xk恆被Xk整除
※ 編輯: gskman          來自: 59.115.77.154        (11/19 21:21)
推 AIdrifter:是阿 我原本也是打這證法~"~ 可是一看Xk?? 我又刪掉了