PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 分堆問題證明

看板Prob_Solve (計算數學 Problem Solving)作者boqCAE (煌)時間8年前 (2016/04/16 21:17)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/2 (看更多)

強數學歸納 step 1: 證明 n=1,2 成立 n=1, 顯然成立 n=2, 2=1+1 成立 step 2: 假設n<k時命題成立，接著考慮n=k 把 k 拆成 k=x+y 時， x<n 且 y<n x 可得到總和 x(x-1)/2 y 可得到總和 y(y-1)/2 再加上 x*y 可得 x(x-1)/2 + y(y-1)/2 + x*y = (x*x-x+y*y-y+2*x*y)/2 = ( (x*x+2*x*y+y*y) - (x+y) )/2 = ( (x+y)*(x+y) - ( x+y ) ) / 2 = (x+y)( (x+y) - 1 ) /2 = k * ( k - 1 ) /2 得證 ※ 引述《sorryla (Mr.東)》之銘言： : 標題: [問題] 分堆問題證明 : 時間: Fri Apr 1 08:37:04 2016 : : 最近小遇到一個問題，想不出證明方式，所以PO文請大大們求救 : : 問題: : : 起始給一個數字，然後每次都將數字分成兩堆，然後將這兩堆的乘積加起來 : 直到最後每一堆都剩下1為止，這總和會是一個常數 : : 例子: : : 起始為5: : : 我們可以有以下幾種可能分法: : : 5 5 : / \ / \ : 2 3 2*3 = 6 1 4 1*4 = 4 : /\ /\ / \ : 11 2 1 1*1 +2*1 = 3 2 2 2*2 = 4 : /\ /\ /\ : 1 1 1*1 = 1 1 1 1 1 1*1 + 1*1 = 2 : : 6 + 3 + 1 = 10 4 + 4 + 2 = 10 : : 這兩總分法最後的總和都是10 : : 我知道這個常數為N*(N - 1) / 2，N為起始數字 : : 但想不出好的證明方式 : : 請大大指教，謝謝! : : -- : ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 67.188.83.255 : ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1459471026.A.184.html : 推 FRAXIS: 我猜 induction 04/01 08:56 : 推 ckc1ark: 假設n個人分兩堆x+y後兩堆人互握(共會有x*y次) x和y再 04/01 21:31 : → ckc1ark: 繼續做下去這樣的行為會讓每個人都握到其他所有的人所 04/01 21:31 : → ckc1ark: 以握手的總次數是n*(n-1)/2 04/01 21:31 : → ckc1ark: 或是說任兩個人只在被分成不同堆時會互握到一次 04/01 21:32 : 推 LPH66: induction (數學歸納法) 無誤 04/01 21:40 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.25.12.210 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1460812646.A.F37.html

Re: [問題] 分堆問題 證明

Re: [問題] 分堆問題證明