Re: [中學] 代數
※ 引述《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
→
06/23 01:50, , 1F
06/23 01:50, 1F
推
06/23 01:52, , 2F
06/23 01:52, 2F
→
06/23 01:57, , 3F
06/23 01:57, 3F
※ 編輯: walkwall (114.40.180.123), 06/23/2017 02:06:07
→
06/27 07:56, , 4F
06/27 07:56, 4F
→
06/27 07:57, , 5F
06/27 07:57, 5F
推
06/27 08:00, , 6F
06/27 08:00, 6F
→
06/27 08:00, , 7F
06/27 08:00, 7F
→
06/27 08:04, , 8F
06/27 08:04, 8F
→
06/27 08:04, , 9F
06/27 08:04, 9F
討論串 (同標題文章)
