推 annheilong:非常感謝!! 03/02 00:22
※ 引述《annheilong (方格子)》之銘言：
: 竟然在99北大資工看到Orz
: ---
: Prove the following statement.
: For n >= 1, let a_1, a_2, ..., a_n be a sequence of n integers where they
: are not necessarily positive and not necessarily all distinct.
: Then there exists a non-empty subsequence a_i, a_i+1, ..., a_j such that
: the sum a_i + a_i+1 + ... + a_j is a multiple of n.
: ---
: 我是覺得北大的題意我比較看得懂
: 中山莫名其妙來個k...題意看不懂Orz
: 有沒有人會解這題呢?
這書上有看到,可是還是忘了怎嚜寫
let x1=a1
x2=a1+a2
...
xn=x1+x2+...+xn
x1 x2 x3...xn各別除以n
caseI:x1.x2.x3...xn中存在xk被n整除
則n|xk
則n|a1+a2+a3+....ak
caseII
x1.x2.x3...xn 各別除以n之餘數不為0
則x1 x2 ....xn除以n之餘數為1 2 3...n-1
by p.h.
則必存在xi-1. xj除以n餘數相同 i<j
則 n|xj-xi-1
則 n|a1+a2+.....ai-1+ai+...+aj-(a1+a2+....ai-1)
則 n|a1+a2+....+aj
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.231.168.102
※ 編輯: cakeboy 來自: 61.231.168.102 (03/02 00:21)