有 1000 枚硬币堆在一起。把它们任意分成两堆，并计算出这两堆的硬币数的乘积。然后，任意选择其中的一堆硬币，把它继续分成两个更小的堆，并计算出这两堆的硬币数的乘积。不断这样做下去，直到最后每堆都只剩一枚硬币为止。求证：把途中产生的所有乘积全部加在一起，结果是一个定值，它不随分法的改变而改变。
这是一个非常经典的问题。让我们把 1000 枚硬币换成 n 枚硬币，这样的话问题反而会更容易一些。如果初始时有 n 枚硬币，把它们分到底后，产生的所有乘积之和是多少呢？考虑一种特殊的分法：把 n 分成 1 和 n – 1 两堆，再把 n – 1 分成 1 和 n – 2 两堆……显然，由此得到的总和应该是 (n – 1) + (n – 2) + … + 2 + 1 = n(n – 1) / 2 。有了这个公式后，我们便很容易用数学归纳法证明，不管分法是什么，最终的结果一定是 n(n – 1) / 2 。首先验证，当 n = 1 时， n(n – 1) / 2 = 0 ，这是符合实际情况的：单独一枚硬币不会产生任何新的乘积。对于一般的 n ，把它分成 x 和 n – x 两堆，得到乘积 x(n – x) 。由归纳假设，这两堆硬币今后将各产生总和为 x(x – 1) / 2 的乘积，以及总和为 (n – x)(n – x – 1) / 2 的乘积。不难算出，x(n – x) + x(x – 1) / 2 + (n – x)(n – x – 1) / 2 正是 n(n – 1) / 2 。
其实，这个问题有一个异常帅的秒杀方法。每次把一堆硬币分成两堆后，计算两堆硬币数量的乘积，实际上相当于是在计算有多少对硬币在这一步被分开了。最后所有乘积的总和，也就是在整个过程中被分开的硬币对的总数。然而， n 枚硬币之间共有 C(n, 2) = n(n – 1) / 2 个硬币对，所有的硬币对最终都被分开了，因而问题的答案就是 n(n – 1) / 2 ，这不随分法的变化而变化。
现在，让我们把问题变一下。假设有一根长度为 n 的线段。把它分成两条子线段，并计算这两条子线段的长度的乘积。选择其中一条子线段，并把它继续分成两条更小的子线段，求出这两条子线段的长度的乘积。不断这样细分下去，直到所有的子线段长度都趋于 0 。在此过程中，不断累加所得的乘积，其总和的极限是多少？（注意，这里的描述还需要更严谨一些，不过我们暂不追究。）
显然，答案应该是一个比 n(n – 1) / 2 更大的数。因为根据前一个问题的解答，把长度为 n 的线段分成 n 个长度为 1 的线段，乘积的总和为 n(n – 1) / 2 ；但在此之后，我们还可以继续切分线段，让总和继续增加。那么，答案究竟是多少呢？我们也可以借助某个特殊的分法得出答案。假设我们按照如下方法把线段无穷细分：先把整条线段等分成两段，得到乘积 (n / 2)2 ；再把所得的两条子线段都进行平分，得到两个 (n / 4)2 ；再依次平分当前的四条子线段，得到四个 (n / 8)2 ……以此类推，最后的总和将会是 (n / 2)2 + 2 · (n / 4)2 + 4 · (n / 8)2 + 8 · (n / 16)2 + … = n2 / 4 + n2 / 8 + n2 / 16 + n2 / 32 + … = n2 / 2 。
不过，我们如何证明，任意一种分法都会导致总和最终会趋于 n2 / 2 ？升级版的问题变得不再离散，数学归纳法和组合方法似乎都派不上用场了。其实，借助几何构造，这个问题也有一个非常直观的秒杀方法。
如图，初始时线段的总长为 n ，那么我们就作一个边长为 n 的等腰直角三角形。如果把线段分成了 x 和 y 两段，由此产生的乘积 x · y 就对应于左图的等腰直角三角形中阴影矩形的面积。继续细分两个子线段，也就相当于递归地处理两个剩余的空白三角形。当所有子线段都被分到无穷短时，矩形面积的总和将会无穷接近于整个等腰直角三角形的总面积，也就是 n2 / 2 。
题目来源：mindyourdecisions.com
查看更多：reddit.com/r/math
沙发
2L!!
3L?
4l？
5L？
膜拜一下
第一个问题就想到了第二个问题的解决方法，结果反而没有解出来……
我记得以前用啥能量可以分析吧。。
phi(n) = n^2
每次分割总能量不变
总释放的能量为 phi(n) – n * phi(1) = n^2 – n
漂亮的解法。以前在《三体》中读到魏成解代数问题，看到的是几何；解几何问题，看到的是代数。难道就是这个样子？
只想到了三角那个
归纳组合都没想OTZ
第一題就想到第二題的方法了……然後就跪了……
帅气
看到了noi金牌大神@roosephu orz..
话说前几天刚证过这个，因为Ural1478的时间复杂度分析要用到……
学习了
膜拜
Schreibe hier Deinen Kommentar Du kannst diese HTML tags verwenden: <a> <abbr> <acronym> <b> &l;tblockquote> <cite> <code> <del> <em> <i> <q> <strike> <strong> var RecaptchaOptions = { theme : ‘red’, lang : ‘en’ , tabindex : 5 }; #submit {display:none;}
“每次把一堆硬币分成两堆后，计算两堆硬币数量的乘积，实际上相当于是在计算有多少对硬币在这一步被分开了。”
谁能帮我解释一下~？？？
第一题求和，第二题积分
好像可以用函数方程，设f(x)为长度为x的线段如此操作得到的结果，x>0,f(x)>0，则有方程f(x+y)=f(x)+f(y)+2xy，用柯西法可证f(x)=x^2/2,x∈Q+，又当x>0时f(x)>0，于是f(x)为增函数，求得f(x)=x^2/2,x∈R+
打错了，方程中2xy改为xy
所谓的“秒杀方法”非常棒，用直观来解释数学问题。
赞！！！
唉 只想到了归纳法。。。
16楼 意思是 假设每两个硬币之间有一条看不见的细线 那么总共n个硬币有n*(n-1)条细线 每分割一次 就有一部分细线断了 如分成x和y2堆 那这边x个和那边y个总共断了x*y条细线 就是双方的积 不断分割下去 所有的线都断了 分割也结束了 加起来断了的和就是要求算的积的和 也即n*(n-1)条
唉 只想到了归纳法。。。
16楼 意思是 假设每两个硬币之间有一条看不见的细线 那么总共n个硬币有n*(n-1)/2条细线 每分割一次 就有一部分细线断了 如分成x和y2堆 那这边x个和那边y个总共断了x*y条细线 就是双方的积 不断分割下去 所有的线都断了 分割也结束了 加起来断了的和就是要求算的积的和 也即n*(n-1)/2条
同16楼……谁能解释一下
怎么理解为有多少对硬币分开
8楼的能量解法谁能解释一下..
@icshine
大小为 n 的石子势能为 phi(n) = n^2/2
每次分为 a b 两堆，势能变为 phi(a) + phi(b)
这个时候释放的能量为 phi(n) – phi(a) – phi(b) = ab 恰好为要计算的能量
由于初始势能为 phi(n) ，终止势能为 n phi(1) 。其余所有的能量都是在分开的时候释放了，所以总释放的能量为 phi(n) – n phi (1) = n(n – 1)/2
orz
膜拜大牛攒人品
Noip前夜，留爪以求人品。
When is a return too much? In case a 5 percent markup will be reasonable, why don’t you consider 10 percent? Can be a 25 % markup unfair? Would likely one hundred % profit become unbanscionocle? If your earnings edge become tied to the price tag on the gold coin, or even if it is linked to the marketplace value
如果每次分拆的两堆中，每堆最少也要有2枚硬币，最后每堆也要充分分到只有2枚硬币（或3枚）硬币的情形呢？乘积的最大最小值是多少？
太好玩了
我想到一种方法哈，将绳长乘以整数M，考虑绳子只能截为整数长度，则由硬币问题知最后积为 nM(nM-1)/2，然后再缩回原长，则积要除以M^2，最后因为绳子是连续的，取M->正无穷，就得到n^2/2啦。
一下子就想到了几何法，哈哈
数形结合，厉害呀。
f(x+y)=f(x)+f(y)+xy这个有点像波函数的干涉，又有点象气泡合并中的表面能。很有意思。
神人啊。。。。这些题都是你秒杀的么
@roosephu
看懂了。多谢！
没想到你这么快就回复了，今天才看到，不好意思= =
太妙了
@roosephu
为什么势能是n^2/2，怎么来的
嗯 很好的哦
第二数学归纳法可以秒吧
哦。。原来第一个方法就是归纳法 。。 刚才还没看解法
回38楼 这是他构造的 为的是使得PHI(N)-PHI(A)-PHI(B)=A*B
牛逼啊
证明很漂亮啊。
不知道这个题是否收录在你今年出的书里了呢？
正打算买这本书呢。
每次把一堆硬币分成两堆后，计算两堆硬币数量的乘积，实际上相当于是在计算有多少对硬币在这一步被分开了。”
谁能帮我解释一下~？？？
“每次把一堆硬币分成两堆后，计算两堆硬币数量的乘积，实际上相当于是在计算有多少对硬币在这一步被分开了。”
我尝试说一下吧，可能不够严谨。
这里是排列组合的概念，所说的对是不区分先后顺序的，即（a,b)和(b,a)是一个对。假设有一堆n个硬币（你可以想象它们都编了号，各自不同），那么其中存在的硬币对有C（n,2)个。而当把这堆硬币分成两堆后，两堆还各自保有一部分原有的硬币对。而在这个过程中，有多少硬件对被破坏了呢？就是那些硬币对中一个被分到了第一堆，一个被分到了第二堆的。一共有多少对呢？就是两堆硬币数量的乘积。这也是个排列组合的问题。
对长度为n的线段进行分割的理解：
当将n分成x份，每份长度为t时，答案是：[t*(n-t)*x]/2 = n*(n-t)/2，所以当长度趋近于0时，答案为：n*n/2。
第一题 “所有的硬币对最终都被分开了”
为什么是所有的都分开了？
假设有n枚，分成n-x 和 x ,求乘积后我第二叠即x枚继续分，那么第一叠里的硬币之间的硬币对 不是都没有被分开么？
第一题 “所有的硬币对最终都被分开了”
请问为什么是所有的都分开了？
假设有n枚，分成n-x 和 x ,求乘积后我第二叠即x枚继续分，那么第一叠里的硬币之间的硬币对 不是都没有被分开么？
每次把一堆硬币分成两堆后，计算两堆硬币数量的乘积，实际上相当于是在计算有多少对硬币在这一步被分开了。
很好理解啊，原来某一枚硬币和其余n-1枚硬币都可以配对，分成两堆后，这枚硬币和另外一堆的x枚硬币都被人为的拆散了，两堆总共被拆散的硬币对是(n-x)x，这里讲的“对”指的是配对的可能而不是实际配对。