→ redcarp0702 : 感恩！！！懂了 03/24 12:39
※ 引述《redcarp0702 (紅鯉魚)》之銘言
: http://i.imgur.com/pl9Hz6j.jpg
: 目前學校剛教完計數原理，看完題目覺得跟二項式係數有關，但想了一個小時完全沒
頭緒
: ，m_k除了均為持續遞增的自然數外，就完全沒規律了，求解謝謝！！
: -----
: Sent from JPTT on my Sony E6853.
eminem2003 想法正確
以下使用同樣的概念，寫簡潔一點
(Lem) 若 n, k 是正整數，0 <= m1 < m2 < ... < mk
且已知 n = C(m1,1) + ... + C(mk,k)
則 mk 只有一個可能值 x
(pf) 設 C(x,k) <= n < C(x+1,k)
注意 x 一定有且只會有一個，且明顯 x >= k
可得 mk 不會大於 x 。以下將證明 mk 也不會小於 x
若 x = k，則 mk < x 會造成 n = 0 不合條件
因此設 x > k，則 mk <= x-1，同時 mi <= x-k+i-1
n = C(m1,1) + C(m2,2) + ... + C(mk,k)
<= C(x-k,1) + C(x-k+1,2) + ... + C(x-1,k)
< C(x-k-1,0) + C(x-k,1) + C(x-k+1,2) + ... + C(x-1,k)
= C(x,k) <= n ，得到 n < n 矛盾
p.s. 需要 x > k 來保證 C(x-k-1,0) = 1 > 0
(Thm) 若 n, k 是正整數，則存在唯一解 0 <= m1 < m2 < ... < mk
滿足 n = C(m1,1) + ... + C(mk,k)
(pf) 顯然 k = 1 正確。假設 k = t - 1 正確
由 Lem 可知，如果解存在，則 mt 只能是 x
考慮 n - C(x,t)
如果是 0，則確定其他 mi = i-1
如果不是 0，由歸納法假設，存在唯一解滿足
n - C(x,t) = C(m1,1) + ... + C(m(t-1),(t-1))
因此 n = C(m1,1) + ... + C(mt,t) 解存在且唯一
原定理由數學歸納法得證
----
Sent from BePTT
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.0.160
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1553366489.A.39D.html