Re: [其他] 鴿籠

[doa2 (邁向名師之路)]

※ 引述《wsx02 ()》之銘言：
: let x1,...,x20 in Z
: x1,...,x20 >= 1,  and x1+...+x20 = 30
: show that there exist i and j such that i<=j and xi+...+xj=10
: 每個x都+10之後得到40個數字介於1~40之間.. 湊不出鴿子跟籠子..
: 請問這題應該怎麼證呢?
: 謝謝
設Sk=x1+x2+..+xk

則1<=S1<S2<...<S20=30

且11<=S1+10<S2+10<S3+10<...<S20+10=40

(1)若存在Sk=10,則x1+x2+...+xk=10  (即i=1, j=k)

(2)若不存在Sk=10,則S1,S2,...,S20,S1+10,S2+10,...S20+10共40個數

介於1~40之間,且均不等於10,故必至少有兩個數相等

且S1,S2,...S20均不相等,S1+10,S2+10,...,S20+10亦均不相等

則必存在Sm=Sn+10 =>  Sm-Sn=10 => x(n+1)+x(n+2)+...+xm=10

(即i=n+1, j=m)

故得證

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 59.126.141.67
推 wsx02       :謝謝