Re: [其他] 鴿籠
※ 引述《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
推
12/16 21:53, , 1F
12/16 21:53, 1F
討論串 (同標題文章)