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

    有 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

52 条评论

  • minglingmaster

    沙发

  • 下水道

    膜拜一下

  • xubihang

    第一个问题就想到了第二个问题的解决方法,结果反而没有解出来……

  • roosephu

    我记得以前用啥能量可以分析吧。。
    phi(n) = n^2
    每次分割总能量不变
    总释放的能量为 phi(n) – n * phi(1) = n^2 – n

  • theta1990

    漂亮的解法。以前在《三体》中读到魏成解代数问题,看到的是几何;解几何问题,看到的是代数。难道就是这个样子?

  • elf

    只想到了三角那个
    归纳组合都没想OTZ

  • vuryleo

    第一題就想到第二題的方法了……然後就跪了……

  • lindnian

    帅气

  • Seter

    看到了noi金牌大神@roosephu orz..
    话说前几天刚证过这个,因为Ural1478的时间复杂度分析要用到……

  • MoeField

    学习了

  • neversurrender

    膜拜

    • Jeanette

      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;}

  • 地球观光客

    “每次把一堆硬币分成两堆后,计算两堆硬币数量的乘积,实际上相当于是在计算有多少对硬币在这一步被分开了。”

    谁能帮我解释一下~???

  • 数分坑爹

    第一题求和,第二题积分

  • minglingmaster

    好像可以用函数方程,设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+

  • minglingmaster

    打错了,方程中2xy改为xy

  • 知然

    所谓的“秒杀方法”非常棒,用直观来解释数学问题。

  • Lyd

    赞!!!

  • 渣渣

    唉 只想到了归纳法。。。
    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楼……谁能解释一下
    怎么理解为有多少对硬币分开

  • icshine

    8楼的能量解法谁能解释一下..

  • roosephu

    @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

  • cc

    orz
    膜拜大牛攒人品

  • Lydraw

    Noip前夜,留爪以求人品。

    • Kaiden

      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

  • lzyl

    如果每次分拆的两堆中,每堆最少也要有2枚硬币,最后每堆也要充分分到只有2枚硬币(或3枚)硬币的情形呢?乘积的最大最小值是多少?

  • plasma

    我想到一种方法哈,将绳长乘以整数M,考虑绳子只能截为整数长度,则由硬币问题知最后积为 nM(nM-1)/2,然后再缩回原长,则积要除以M^2,最后因为绳子是连续的,取M->正无穷,就得到n^2/2啦。

  • Maigo

    一下子就想到了几何法,哈哈

  • 老班

    数形结合,厉害呀。

  • morrowind

    f(x+y)=f(x)+f(y)+xy这个有点像波函数的干涉,又有点象气泡合并中的表面能。很有意思。

  • nc

    神人啊。。。。这些题都是你秒杀的么

  • icshine

    @roosephu
    看懂了。多谢!

    没想到你这么快就回复了,今天才看到,不好意思= =

  • xrz199721

    太妙了

  • emo

    @roosephu
    为什么势能是n^2/2,怎么来的

  • 天堂风吹的人

    嗯 很好的哦

  • rydrydryd

    第二数学归纳法可以秒吧

  • rydrydryd

    哦。。原来第一个方法就是归纳法 。。 刚才还没看解法

  • rydrydryd

    回38楼 这是他构造的 为的是使得PHI(N)-PHI(A)-PHI(B)=A*B

  • yarmu

    牛逼啊

  • 凡星有梦

    证明很漂亮啊。
    不知道这个题是否收录在你今年出的书里了呢?
    正打算买这本书呢。

  • cervelo

    每次把一堆硬币分成两堆后,计算两堆硬币数量的乘积,实际上相当于是在计算有多少对硬币在这一步被分开了。”

    谁能帮我解释一下~???

  • 自学青年

    “每次把一堆硬币分成两堆后,计算两堆硬币数量的乘积,实际上相当于是在计算有多少对硬币在这一步被分开了。”
    我尝试说一下吧,可能不够严谨。
    这里是排列组合的概念,所说的对是不区分先后顺序的,即(a,b)和(b,a)是一个对。假设有一堆n个硬币(你可以想象它们都编了号,各自不同),那么其中存在的硬币对有C(n,2)个。而当把这堆硬币分成两堆后,两堆还各自保有一部分原有的硬币对。而在这个过程中,有多少硬件对被破坏了呢?就是那些硬币对中一个被分到了第一堆,一个被分到了第二堆的。一共有多少对呢?就是两堆硬币数量的乘积。这也是个排列组合的问题。

  • pty

    对长度为n的线段进行分割的理解:
    当将n分成x份,每份长度为t时,答案是:[t*(n-t)*x]/2 = n*(n-t)/2,所以当长度趋近于0时,答案为:n*n/2。

  • mmliu

    第一题 “所有的硬币对最终都被分开了”

    为什么是所有的都分开了?

    假设有n枚,分成n-x 和 x ,求乘积后我第二叠即x枚继续分,那么第一叠里的硬币之间的硬币对 不是都没有被分开么?

  • mmliu

    第一题 “所有的硬币对最终都被分开了”

    请问为什么是所有的都分开了?

    假设有n枚,分成n-x 和 x ,求乘积后我第二叠即x枚继续分,那么第一叠里的硬币之间的硬币对 不是都没有被分开么?

  • 伍岭

    每次把一堆硬币分成两堆后,计算两堆硬币数量的乘积,实际上相当于是在计算有多少对硬币在这一步被分开了。

    很好理解啊,原来某一枚硬币和其余n-1枚硬币都可以配对,分成两堆后,这枚硬币和另外一堆的x枚硬币都被人为的拆散了,两堆总共被拆散的硬币对是(n-x)x,这里讲的“对”指的是配对的可能而不是实际配对。

发表评论