算法-算法趣题：证明所有乘积的总和和分拆的方式无关

Question

有 n 枚硬币堆在一起。把它们任意分成两堆，并计算出这两堆的硬币数的乘积。然后，任意选择其中的一堆硬币，把它继续分成两个更小的堆，并计算出这两堆的硬币数的乘积。不断这样做下去，直到最后每堆都只剩一枚硬币为止。求证：把途中产生的所有乘积全部加在一起，结果是一个定值，它不随分法的改变而改变。
各抒己见。

Answer 1

可以看一下Matrix的文章，话说一楼这回答....

趣题：证明所有乘积的总和与分拆的方式无关

Answer 2

总值应该是n*(n-1)/2

建立递归函数f(n)=f(n-1)+n-1
然后就可以得到答案了
f(m1+m2)=f(m1)+f(m2)+m1*m2也可以由该式子导出

Answer 3

这个问题有一个异常帅的秒杀方法。每次把一堆硬币分成两堆后，计算两堆硬币数量的乘积，实际上相当于是在计算有多少对硬币在这一步被分开了。最后所有乘积的总和，也就是在整个过程中被分开的硬币对的总数。然而， n 枚硬币之间共有 C(n, 2) = n(n - 1) / 2 个硬币对，所有的硬币对最终都被分开了，因而问题的答案就是 n(n - 1) / 2 ，这不随分法的变化而变化。

其实，借助几何构造，这个问题也有一个非常直观的秒杀方法：

如图，初始时线段的总长为 n ，那么我们就作一个边长为 n 的等腰直角三角形。如果把线段分成了 x 和 y 两段，由此产生的乘积 xy 就对应于左图的等腰直角三角形中阴影矩形的面积。继续细分两个子线段，也就相当于递归地处理两个剩余的空白三角形。当所有子线段都被分到无穷短时，矩形面积的总和将会无穷接近于整个等腰直角三角形的总面积，也就是 n x n/2 。