Re: [中學] 代數

[walkwall (會走路的牆)]

※ 引述《cuttlefish (無聊ing ><^> .o O)》之銘言：
: X為正實數集合, s(X):= X的元素和, r(X):= X的最大元素/X的最小元素.
: 給定A={a1, a2, ..., an}為n個相異正整數, S:={s(X): X是A的非空子集合}.
: 試證明S可以分割成n個非空子集合S1, ..., Sn且 r(Si)<=2 對所有的i=1~n.
: 謝謝

將 A 內元素排序由小到大為 A={b1, b2, ..., bn}

Si := { (b1 + b2 + ... + bi) >= y >= 1/2 (b1 + b2 + ... + bi) }

上述定義包含最小值 b1 in S1, 最大值 b1 + b2 + ... + bn in Sn

且每個 Si 定義本身使得 r(Si) <= 2

只須證明所有其他元素均包含於其中一 Si 即可

-------

for all 其他元素 E, 必存在 j 使得 b1 + ... + bj >= E > b1 + ... + bj-1


(1) 若 Sj 與 Sj-1 之間無空隙, 即 (b1 + ... + bj-1) >= 1/2 (b1 + ... + bj)

則 E > b1 + ... + bj-1 >= 1/2 (b1 + ... + bn), 可歸在 Sj 內


(2) 若 Sj 與 Sj-1 之間有空隙, 即 (b1 + ... + bj-1) < 1/2 (b1 + ... + bj)

左右同乘2再同減 (b1 + ... + bj-1) => (b1 + ... + bj-1) < bj

即, "所有小於 bj 之元素總合" 也小於 bj

則因為 E > b1 + ... + bj-1 [前述 j 的定義], E 必然包含 bj

但若 E 包含 bj, 則 E >= bj = 1/2 bj + 1/2 bj
                           > 1/2 bj + 1/2 (b1 + ... + bj-1)
                           = 1/2 (b1 + ... + bj-1 + bj)

依 Sj 定義, E 也可歸於 Sj 內       Q.E.D.


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.40.180.123
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1498153372.A.8B7.html
→ walkwall    : 不過這應該不是普通的中學題目吧?  XD
推 Vulpix      : 推，不過Si的定義裡應該是到加bi而不是bn？
→ walkwall    : XDDD  哎唷沒錯  想睡了又迷糊了  我改一下
※ 編輯: walkwall (114.40.180.123), 06/23/2017 02:06:07
→ cuttlefish  : 感謝 不過因為Si是S的分割 所以Si的取法可能有點問
→ cuttlefish  : 題 至少(1)情況不會發生
推 cuttlefish  : 改成Bi:=b1+...+bi,Si:={y in S: Bi>=y>max{Bi-1,
→ cuttlefish  : 1/2Bi} }可能就對了
→ cuttlefish  : 然後小Typo, 應該E>b1+...+bj-1 implies E包含bk
→ cuttlefish  : where k>=j 不一定保證包含bj 雖然後面結論一樣