作者sorryla (Mr.东)
看板Prob_Solve
标题[问题] 分堆问题 证明
时间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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1459471026.A.184.html
1F：推 FRAXIS: 我猜 induction 04/01 08:56
2F：推 ckc1ark: 假设n个人 分两堆x+y後 两堆人互握(共会有x*y次) x和y再 04/01 21:31
3F：→ ckc1ark: 继续做下去 这样的行为会让每个人都握到其他所有的人 所 04/01 21:31
4F：→ ckc1ark: 以握手的总次数是n*(n-1)/2 04/01 21:31
5F：→ ckc1ark: 或是说任两个人只在被分成不同堆时会互握到一次 04/01 21:32
6F：推 LPH66: induction (数学归纳法) 无误 04/01 21:40