推 redcarp0702 : 十分感謝!!!! 03/24 12:39
※ 編輯: eminem2003 (101.137.253.123), 03/24/2019 19:05:57
※ 引述《redcarp0702 (紅鯉魚)》之銘言:
: http://i.imgur.com/pl9Hz6j.jpg
: 目前學校剛教完計數原理,看完題目覺得跟二項式係數有關,但想了一個小時完全沒頭緒,m_k除了均為持續遞增的自然數外,就完全沒規律了,求解謝謝!!
: -----
: Sent from JPTT on my Sony E6853.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.137.157.39
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1553363409.A.B9B.html
寫了一個略嫌(?)粗糙的證明,待高手檢驗
以下C(a,b)表示Ca取b
題目是說任意給兩正整數n,k
若存在由小到大的k個正整數,上面是寫m1~mk
依序放到 C( ,1)+C( ,2)+C( ,3)+....C( ,k)的那些空白處
也就是 C(m1,1)+C(m2,2)+C(m3,3)+....C(mk,k) 之值為n的話,
m1~mk的選擇是唯一的
為了方便我假設 F(v,k)=C(v1,1)+C(v2,2)+C(v3,3)+....C(vk,k)
v是一個k維非負整數向量, vi表示第i個分量 而且v1<v2<...vk
用數學歸納法
x=1的時候顯然(用x是因為不重複符號
難處在於
當x=k成立時,k+1怎麼也得到論證成立
x=k成立時,原命題的等價敘述是
一旦給定任何一個上述向量v=(v1,v2,...,vk),所得到F(v,k)的值
和任何另一個上述性質向量u=(u1,u2....,uk),得到的F(u,k)值必不相等
現在考慮x=k+1
比較以下兩者的差值
F(v,k+1)=C(v1,1)+C(v2,2)+C(v3,3)+....C(vk,k)+C(vk+1,k+1)簡稱F1
F(u,k+1)=C(u1,1)+C(u2,2)+C(u3,3)+....C(uk,k)+C(uk+1,k+1)簡稱F2
先直接比最後項C(vk+1,k+1)和C(uk+1,k+1)
首先只需要討論兩者不相等的情況,
因為如果相等,F1和F2的前面k項總和是相等的,這個時候因為x=k成立
必然得到u=v
所以最後兩項不相等,為了方便理解,我用實際數字示範
以下證明用到的關鍵是 C(n,k-1)+C(n,k)=C(n+1,k)的移項
C(n+1,k)-C(n,k)=C(n,k-1)
然後我的目的是要證明差值無法相等
WLOG, C(vk+1,k+1)>C(uk+1,k+1)
就假設前者是C(101,61) (數字亂掰的) 對應的總和是F1
也就是現在的情形k=60已經好了要證明k+1=61
我想要證明此時無論u怎麼給,F1永遠大於F2
換句話說,兩者最後一項之間的大小決定兩者總值大小
本質上就是再算前面k項差值的估計值並且她無法大過最後一項之間的差
現在目標是想決定u使得F2的值可以追上目前和F1的差距
uk的最好選擇(以下所說的最好選擇都是使得差值最小的選擇)
就是C(100,61) (因為61被定住了,比101小最大數字為100)
但是F1-F2目前只看最後一項差值是C(101,61)-C(100,61)=C(100,60)
所以目前F1比F2至少還大C(100,60)
uk-1的最好選擇就是C(99,60) (因為60被定住了,比100小最大數字為99)
但是F1-F2目前差額變成了C(100,60)-C(99,60)=C(99,59)
所以目前F1比F2至少還大C(99,59)
好了有沒有看出來即使每一次都選u讓F2和F1的差值最小都還是永遠追不上
可以繼續玩下一個
uk-2的最好選擇就是C(98,59) (因為59被定住了,比99小最大數字為98)
不囉嗦,差值變成了C(98,58)
所以繼續再玩到沒得玩,本例子的結局是
差額變成了C(41,1)
但是u1的最好選擇只有C(40,1)
所以用這組數字得到的結果就是F1>F2無論u的選擇
但是你把數字變成未知正整數可以得到一模一樣結果,剛剛只是方便理解
真的要證明就把上面的101改成q,61改成p吧,然後依序減1做一模一樣論證
記得要假設q>p
重新整理一下最終得到的結論就是:
若
當x=k時成立
x=k+1也會成立,根據上面的估計
因為只需要討論兩者最後一項不相等的情況
然而最後一項比較大的總值也會比較大,無論u向量的選擇,
一旦v向量給定以後,換句話說就是總值F1,F2兩者不會相等
會出現這樣的情形是因為我們假設兩者最後一項不相等,
一旦不相等,總值就會不相等,
不過若兩者最後一項相等,根據一開始討論,
u=v
因此選擇m1,m2.....mk+1的選擇只有唯一一種
數學歸納法結束