Re: [理工] [離散] 請問一題鴿籠

[annheilong (方格子)]

※ 引述《chencccc (小達)》之銘言：
: ※ 引述《lock7863701 (Ayo)》之銘言：
: : Let x1,x2...x20 為整數, x1,x2...x20≧1 x1+x2+...+x20 = 30
: : (a)Show that there exist i and j such that i≦j and xi+....+xj = 9
: : (b)Show that there exist i and j such that i≦j and xi+....+xj = 10
: : 有問題的是第二小題
: : 我假設s1 = x1;
: : s2 = x1+x2;
: : s3 = x1+x2+x3;
: : 以此類推
: : 然後1≦s1<s2....<s20≦30
: : 之後列出s1,s2,....s20,s1+9,s2+9,...s20+9≦39 得證
: : 但是第二小題卻剛好都是40個
: : 請問該怎麼解呢
: : ps. 99高大
: 1≦s1<s2....<s20≦30
: 11≦s1+10<s2+10....<s20+10≦40
: 上述共計有40個數介於1至40
: 如果存在一個a<b =>sb=sa+10 =>找到啦
: 否則此40個數全相異 這40個數分別為1~40
: 其中一定有某個s=10

能不能這樣證明呢?

將x1, x2, ... x20看作20個桶子

現有30顆球，裝在20個桶子內

xi = a表示 xi中有a顆球

因x1, x2, ..., x20 >= 1

故x1, x2, ..., x20至少有1顆球

餘下10顆球，只多只能分裝至10個桶子

則至少有10個桶子只有1顆球 => 2得證

因10 > 9 => 1得證

--
推 xxxx        :老闆都不懂.. ( ′-`)y-～
→ ooooooooo   :這裡禁煙喔XDDDD
--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.228.129.229
→ charliejack:你題意就搞錯嚕 他要問 Xi~Xj 中"連續" 有九顆
→ charliejack:你證的是 x1 ~ x20 中 有10個xi 是一顆球
→ annheilong:嗯嗯... x1~x20視為不同的... 感恩