寫了一個略嫌(?)粗糙的證明，待高手檢驗 以下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的選擇只有唯一一種 數學歸納法結束 ※ 引述《redcarp0702 (紅鯉魚)》之銘言： : http://i.imgur.com/pl9Hz6j.jpg : 目前學校剛教完計數原理，看完題目覺得跟二項式係數有關，但想了一個小時完全沒頭緒，m_k除了均為持續遞增的自然數外，就完全沒規律了，求解謝謝！！ : ----- : Sent from JPTT on my Sony E6853. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.137.157.39 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1553363409.A.B9B.html ※ 編輯: eminem2003 (101.137.253.123), 03/24/2019 19:05:57