观点 数学

砝码称重问题,因式分解有妙用

钓主 发表于  2010-12-21 17:58

如果天平两端都允许放砝码,并且假定所有的砝码都是整数克。为了称出从 1 克到 40 克 所有整数克 的物品,最少需要几个砝码?

感兴趣的读者不妨自己先试着想想,再往下看。

秘密在于 3 的幂

说起来这个问题历史还算是挺悠久的。据《数学游戏与欣赏》( [英] 劳斯·鲍尔 [加] 考克斯特 著,杨应辰等 译),这个问题被称作巴协 (Bachet) 砝码问题;而据《数学聊斋》(王树禾著),该问题至少可追溯到 17 世纪法国梅齐里亚克 (Meziriac, 1624) 。他们给出的答案是:

最少需要 4 个砝码,规格分别为 1 克、3 克、9 克和 27 克。

例如,为了称出 2 克的物品,我们只需在天平一端放 3 克砝码,在另一端放上 1 克的砝码;而要称出 7 克的物品,则可以在一端放上 1 克和 9 克的砝码,另一端放上 3 克的砝码。

类似地,要称出 1 克到 4 克中所有整数克的物品,只需要 2 个砝码;要称出 1 克到 13 克中所有整数克的物品,则只需要 3 个砝码;要称出 1 克到 121 克中所有整数克的物品则要 5 个砝码,它们分别是 1 克、3 克、9 克、27 克和 81 克,如此等等。

也许有人已经心领神会了,但是如果就此满足而匆匆离去的话,可能就错失了一个领略数学思想的机会——问题到这里并未结束啊!例如,4 个砝码究竟是不是最少的?还有没有其他的组合?对这些疑问的一个彻底的分析和说明,是 19 世纪由麦克马洪 (MacMahon) 给出的。下面就来领略一下其中的思想吧,或许你会从中学到很多。

因式分解的妙用

假设有一个重为 a 克的砝码,那么用它自然能够称出 0 克和 a 克的物品。不过,如果虚设天平的某一端为正的话,利用此天平和砝码我们还能称出 - a 克的物品——不妨规定把 a 克砝码放在天平右侧,将物品放在天平左侧,由此可以称出 a 克的物品;但若把 a 克砝码放在天平左侧,把物品放在天平右侧,由此称出的物品重量记作 - a。目前这样一种设想有点怪异,但这实际上和人类引入负数的思想是相同的。很快大家便会发现,这种设定非常精妙地简化了我们的计算和推导。现在暂且把该砝码能够称出的重量 - a,0,a 放进一个表达式中:

http://www.guokr.com/gkimage/hp/xc/hj/hpxchj.png

现在,假设有两个不同规格的砝码,分别重 a 克和 b 克(a http://www.guokr.com/gkimage/z9/iq/kt/z9iqkt.png

可以看到,它不是别的,正好是

http://www.guokr.com/gkimage/8i/51/7h/8i517h.png

的展开式。

另外,假设有 m 个同样重为 a 克的砝码,则可以称出 - ma,- (m - 1)a,…,0,…,(m - 1)a,ma 克的物品。暂且按照上面的办法,把这些数也塞进一个表达式中 :

http://www.guokr.com/gkimage/3a/w2/2i/3aw22i.png

结合上面的分析,容易看出,如果有 m 个 a 克的砝码,n 个 b 克的砝码,等等,那么可以称出物品的克数就是表达式

http://www.guokr.com/gkimage/03/86/24/038624.png

展开后出现过的那些 x 的幂数,而展开式中 x 的 i 次项系数就表示用给定的这组砝码称出 i 克物品的不同方法数。

如果要称出 1 到 40 中所有的整克数,并且要求所用的砝码尽可能少,我们自然希望这些砝码能够“物尽其用”,称出的克数正好都是我们需要的克数,并且称的方法都是唯一的。也就是说,上述表达式展开后应该恰好是

http://www.guokr.com/gkimage/w1/nr/xs/w1nrxs.png

反过来,就是要把

http://www.guokr.com/gkimage/w1/nr/xs/w1nrxs.png

还原成

http://www.guokr.com/gkimage/03/86/24/038624.png

的形式。

对这个式子进行分解,一共有八种不同的方案:

http://www.guokr.com/gkimage/8z/tx/yf/8ztxyf.png

前四个式子展示了我们实际上是如何对原式进行逐步分解的。它们的意义依次为:(1) 40 个 1 克的砝码;(2) 1 个 1 克,13 个 3 克的砝码 ;(3) 1 个 1 克,1 个 3 克以及 4 个 9 克的砝码;(4) 1 个 1 克,1 个 3 克,1 个 9 克以及 1 个 27 克的砝码。其中,第四个分解式是最基本的,它就是我们想要的答案。

当然我们还要说明,除了上面列举的 8 种组合之外没有其他的组合。这是一个多少有些复杂的讨论,不过我们可以就此为止了,因为上面的分解式看起来应该明显包含了所有可能的分解。最少的那组已经明摆着了,无须再说。大家可以到 死理性派小组 参与更详细的讨论。

显示所有评论

全部评论(35)
  • 1楼
    2010-12-21 18:39 xyfd

    这个东西可以用来出考试题

    [1] 评论
  • 2楼
    2010-12-21 18:39 Sheldon 理论物理博士,科学松鼠会成员

    赞智商,一眼扫过去竟然没看懂

    [1] 评论
  • 3楼
    2010-12-21 20:13 蚁观沧海

    死文科僧表示有关键一步没有看懂……

    “很快大家便会发现,这种设定非常精妙地简化了我们的计算和推导。现在暂且把该砝码能够称出的重量 - a,0,a 放进一个表达式中: x^-a +1+x^a”

    为什么能放进这个表达式里?这个表达式是什么意思?x又有什么含义?为什么能想到塞进这个表达式里?
    死文科僧非常痛苦……

    [2] 评论
  • 4楼
    2010-12-21 20:17 蚁观沧海
    引用 蚁观沧海 的回应:死文科僧表示有关键一步没有看懂……“很快大家便会发现,这种设定非常精妙地简化了我们的计算和推导。现在暂且把该砝码能够称出的重量 - a,0,a 放进一个表达式中: x^-a +1+x^a”为什么能放进......


    和某人聊了一下又百度了因式分解……是用因式分解的思维方法然后过河拆桥?可是又是怎么想到的呢?

    [0] 评论
  • 5楼
    2010-12-21 20:57 方弦 科学松鼠会成员,信息学硕士生

    这个方法只能说是能解*恰好*能称出这么多种总量的砝码组合。如果说是要求能称量1到39克的重量的话,答案还是原来那个答案,但是文中的方法就不适用了。

    [0] 评论
  • 6楼
    2010-12-21 22:01 lding.呐

    真是太酷了~赞一个!!!还有些不明白,收藏下来慢慢品味品味再

    [0] 评论
  • 7楼
    2010-12-21 22:05 DiamondbacK 数学控
    引用 fwjmath 的回应:这个方法只能说是能解*恰好*能称出这么多种总量的砝码组合。如果说是要求能称量1到39克的重量的话,答案还是原来那个答案,但是文中的方法就不适用了。

    犀利。

    [0] 评论
  • 8楼
    2010-12-21 22:12 已注销用户

    显然就是组合数学中的母函数啊……

    [0] 评论
  • 9楼
    2010-12-21 22:16 DiamondbacK 数学控
    引用 fwjmath 的回应:这个方法只能说是能解*恰好*能称出这么多种总量的砝码组合。如果说是要求能称量1到39克的重量的话,答案还是原来那个答案,但是文中的方法就不适用了。

    犀利。
    这个问题第一步应该判断的是“秘密在于3的幂”,在文章中并没有体现出这个小标题的内涵。用2的幂浪费,用4的幂行不通,只能用3的幂(要是不用某个幂呢?这正是应该讨论一下的问题。)。在这个结论下,只要看要用几个3的幂能“够得着”40, 就行了。

    [0] 评论
  • 10楼
    2010-12-22 09:22 阿苏Asu

    LS说得有道理。(1/x+1+x)*(1/x^3+1+x^3)*(1/x^9+1+x^9)*(1/x^27+1+x^27) 展开共有3^4=81项,最高次数能够到1+3+9+27=40,注意到(81-1)/2=40。用其他数就不行,秘密就在等比数列公式[3^(n+1)-1]/(3-1)=3^0+3^1+3^2...+3^n。所以用3刚刚好,2浪费了,5显然不够。

    [0] 评论
  • 11楼
    2010-12-22 09:39 钓主 数学博士
    引用 fwjmath 的回应:这个方法只能说是能解*恰好*能称出这么多种总量的砝码组合。如果说是要求能称量1到39克的重量的话,答案还是原来那个答案,但是文中的方法就不适用了。


    40确实是一个精心选择的数,太小了则容易让人还原出动机,而太大了就又可能显得乏味。 我认为即使选择了其它的数,文中因式分解的思想还是可以自然的拓展的,无论如何,它提供了一种参照。再说趣味在很多情况下就是在一个巧妙的发现以后,让人追寻的玩味。40就是一个巧妙的数,就像很多知道典故的人所知的,1729等等是很巧妙的数一样,唯有巧妙,才会让人在面对这些数时有一种不同于其他数的激动。

    [0] 评论
  • 12楼
    2010-12-22 10:49 第一个名字

    可以请问一下 为什么要吧-a到a 写成X ^-a +1+ x^a的形式么

    [0] 评论
  • 13楼
    2010-12-22 11:07 GT
    引用 sheldon 的回应:赞智商,一眼扫过去竟然没看懂

    我也是没怎么看明白

    [0] 评论
  • 14楼
    2010-12-22 13:12 钓主 数学博士
    引用 第一个名字 的回应:可以请问一下 为什么要吧-a到a 写成X ^-a +1+ x^a的形式么


    请看“结合上面的分析,……
    这样写正是为了建立这个关键的联系,从而也就把问题和因式分解连到了一起。

    [0] 评论
  • 15楼
    2010-12-22 13:14 钓主 数学博士
    引用 蚁观沧海 的回应:死文科僧表示有关键一步没有看懂……“很快大家便会发现,这种设定非常精妙地简化了我们的计算和推导。现在暂且把该砝码能够称出的重量 - a,0,a 放进一个表达式中: x^-a +1+x^a”为什么能放进......


    参看上面的回应

    [0] 评论
  • 16楼
    2010-12-22 13:54 第一个名字
    引用 钓主 的回应:引用 第一个名字 的回应:可以请问一下 为什么要吧-a到a 写成X ^-a +1+ x^a的形式么

    请看“结合上面的分析,……
    这样写正是为了建立这个关键的联系,从而也就把问题和因式分解连到了一起。

    傲~~ 明白了 那个1 就是 X^0 …………

    [0] 评论
  • 17楼
    2010-12-22 16:14 Maxwellsdemon 电子工程专业

    貌似可以用信息熵来计算……最近数学建模讲到了……

    [0] 评论
  • 18楼
    2010-12-22 16:32 方弦 科学松鼠会成员,信息学硕士生
    引用 钓主 的回应:引用 fwjmath 的回应:这个方法只能说是能解*恰好*能称出这么多种总量的砝码组合。如果说是要求能称量1到39克的重量的话,答案还是原来那个答案,但是文中的方法就不适用了。

    40确实是一个精心选......


    其实无须什么“精心选择的数”。可以用数学归纳法证明,在天平上,n个砝码能从1开始连续称量的重量恰好是(3^n-1)/2。每步新砝码的选取都用贪心法就可以了。而如果用因式分解的方法的话,连从1到3连续称量需要的砝码数都算不出来,因为(x^-3+x^-2+x^-1+1+x+x^2+x^3)*x^3在R上不可约。

    因式分解的问题在于,难以扩展到一般情况,因为如果最优解有多余的重量组合可以称出来的话,因式分解的方法不能得出解,因为此时要分解的因式需要包含多余的重量组合,而这个在事先是无法猜出来的。

    [1] 评论
  • 19楼
    2010-12-22 19:17 钓主 数学博士
    引用 fwjmath 的回应:引用 钓主 的回应:引用 fwjmath 的回应:这个方法只能说是能解*恰好*能称出这么多种总量的砝码组合。如果说是要求能称量1到39克的重量的话,答案还是原来那个答案,但是文中的方法就不适用了。40......


    你的话当然不错,如果单纯就这个问题的求解而言,简单的推理归纳就足够了。
    你强调“此时要分解的因式需要包含多余的重量组合,而这个在事先是无法猜出来的”,你可能一时疏忽,实际上我们的方法已经给出了指导,只有通过这种分析方法之后才能搞明白怎样才是正确的补救方式(它和下面的第二问相关)。
    另外,你可以归纳出n个砝码能从1开始连续称量的重量恰好是(3^n-1)/2,你也能归纳出为要恰好能连续称量1到(3^n-1)/2,可以有哪些不同的组合吗?还有,对于任意的n,存在恰好能够(不多也不少)连续称量1到n的砝码组合吗?给你一些砝码,你能称出哪些量呢,并且各有多少种称量方式?……
    这些问题尽管也未必困难,不过也绝不是都很简单的,但是因式分解法无疑是可以统一处理它们的。
    方法都有局限,但是一种思想或方法如果不仅仅单独对待个别的特例,而且它能够解释这一特例为什么特别,以及这个特例可以以怎样的方式自然的延伸,从而指出我们可以提出更多的以及是怎样的问题,那么这种思想和方法就绝对够得上好的标准。
    Dirac说过,方程比人聪明。的确,一种方法比我们能想的可能都要多。

    [0] 评论
  • 20楼
    2010-12-22 20:13 方弦 科学松鼠会成员,信息学硕士生
    引用 钓主 的回应:引用 fwjmath 的回应:引用 钓主 的回应:引用 fwjmath 的回应:这个方法只能说是能解*恰好*能称出这么多种总量的砝码组合。如果说是要求能称量1到39克的重量的话,答案还是原来那个答案,......


    如果是囿于“恰好”的解的话,当然这种母函数的方法可以解决问题。但原来问题的一个自然推广显然是*能*称量出某些重量组合而不是*能且仅能*,我只是在说在这样的情况下,文中的方法难以解决这个问题。然而可以证明,用贪心法可以得到这类自然推广的解,因为砝码称量问题有拟阵的结构,而贪心法可以解决类似这样有拟阵结构的问题。贪心法可以回答比如说“求砝码数最小的砝码组合,使得这个组合可以称量所有小于1000的素数的重量”,而这显然是文中方法力所不逮的。

    的确母函数是解决计数问题的利器,你说的所有关于求组合个数用母函数解决也是非常方便。我只是说,在原问题的自然推广下,母函数并不是一种好方法。

    至于“要恰好能连续称量1到(3^n-1)/2,可以有哪些不同的组合吗?”这个问题,文中的方法并不适用。文中的方法适用的问题是“要恰好能连续称量1 到(3^n-1)/2,【且每种重量只有一种方法称量】,可以有哪些不同的组合吗?”。不加上这个限制条件的话,你需要在Z上分解所有(3^n-1)/2 次的首一对称多项式(这里的对称是指关于x的次数对称),这是难以实现的。

    另外,“对于任意的n,存在恰好能够(不多也不少)连续称量1到n的砝码组合吗?”这个问题,完全是显然的,因为必定存在,取n个1克的砝码即可。

    [0] 评论
  • 21楼
    2010-12-22 20:55 钓主 数学博士
    引用 fwjmath 的回应:引用 钓主 的回应:引用 fwjmath 的回应:引用 钓主 的回应:引用 fwjmath 的回应:这个方法只能说是能解*恰好*能称出这么多种总量的砝码组合。如果说是要求能称量1到39克的重量的话,答......


    嗯,这个问题的限制条件忘加了,要求的是对于任意的n,恰好能连续称出1到n的最少的砝码组合,它符合Mezirac提出问题的方式(砝码是由一整块碎裂得到的)。对于一般的n,这个问题看上去可能很愚蠢,因而还是忘了它。
    关于算法,我是外行,不过也知道贪婪算法是解决极值问题的利器,感谢你指明的它和与本文相关的一类问题的关系。
    最后,感谢你的评论和批评,它们对于更好的理解和评价文中的方法十分有帮助,有心的读者会从中看到更多。

    [0] 评论
  • 22楼
    2010-12-22 22:07 阿苏Asu

    楼主的文章是想解决如下命题:“对于任意的n (n>=1),存在恰好连续称量1到n的砝码组合,且使砝码的数量最少。”对于这个问题,因式分解(姑且这么叫)确实是最简单有效的。

    可以先简单的来看(x^-1+1+x)*(x^-2+1+x^2),(x^-1+1+x)*(x^-3+1+x^3),和(x^-1+1+x)*(x^-4+1+x^4),即我们使用一个重量为1的砝码和1个重量为2、3、或4的砝码来称。
    (x^-1+1+x)*(x^-2+1+x^2)=x^-3+x^-2+2x^-1+1+x+2x+x^2+x^3;
    (x^-1+1+x)*(x^-3+1+x^3)=x^-4+x^-3+x^-2+x^-1+1+x+x^2+x^3+x^4;
    (x^-1+1+x)*(x^-4+1+x^4)=x^-5+x^-4+x^-3+x^-1+1+x+x^3+x^4+x^5;
    从上面我们可以看到,用一个重量为1的砝码和1个重量为2的砝码可以连续称1到3的重量,但是注意到展开式有两项的系数为2,也就是说,存在两种不同的组合方法称到了同样的重量。用一个重量为1的砝码和1个重量为3的砝码可以连续称1到4的重量,且展开式每项的系数为1,也就是说,对于称量每一个重量存在且只存在一种组合。用一个重量为1的砝码和1个重量为4的砝码不能连续称1到5的重量(称不出2),虽然展开式每项的系数也为1。

    原因是什么的呢?(x^-1+1+x)*(x^-2+1+x^2)的展开项的最高次数是3,但是展开项的个数是9,(9-1)/2>3,因此必有幂次相同的重复项。(x^-1+1+x)*(x^-3+1+x^3)的展开项的最高次数是4,展开项的个数是9,(9-1)/2=4,因此正好没有重复的项和遗漏的项,每一项前面的系数为1。最后(x^-1+1+x)*(x^-4+1+x^4)的展开项的最高次数是5,展开项的个数是9,(9-1)/2<5,因此存在遗漏的项。容易看出,对于表示式(x^-1+1+x)*(x^-3+1+x^3)*(x^-9+1+x^9)*(x^-27+1+x^27)....(x^-(3^n)+1+x^(3^n))展开后的项数为3^(n+1),次数从-(1+3+9+27+...+3^n)=-(3^(n+1)-1)/2到(1+3+9+27+...+3^n)=(3^(n+1)-1)/2,每一项的系数均为1,没有重复和遗漏。

    可以证明,如果存在恰好连续称量1到n的砝码组合,且使砝码的数量最少,那么砝码的重量必为3的等比项(1, 3, 9, 27...),并使表达式(x^-1+1+x)*(x^-3+1+x^3)*(x^-9+1+x^9)*(x^-27+1+x^27)....的最高次数不低于n。我想,这个命题已经很强了。

    [0] 评论
  • 23楼
    2010-12-23 13:20 brgka

    假设有砝码n个,F1到Fn。每个砝码前加个系数Xi(只能取-1,0,+1)表示不同的砝码放置。一个自然数能被称出来等价于能表示为“Xi×Fi的求和,i从1到n”。
    因为Xi只有3种取法,所以共可以组合成3^n个数。去掉一个0(所有系数为0),再考虑到正负数各一半,所以能称出来的自然数有(3^n-1)/2个。当n=4的时候,刚好是40个。
    如果令Fi依次是3的幂,可以证明这些自然数各不相同。假设有SIGMA[Xi*Fi]=SIGMA[Yi*Fi],Xi和Yi是系数,要证明必有Xi=Yi。有SIGMA[(Xi-Yi)*Fi]=0,Xi-Yi取-2/-1/0/1/2,Fi是3的幂。把负的Xi-Yi移到等式另一边,容易看出必有Xi-Yi=0。如果3的最高幂在等式左边,那右边无论如何也加不到等于左边的。比如假设从3的0次幂一直到3的n-1次幂的系数都是最大的2,则和为3^n-1,仍然比3^n小。从这里顺便也能看出Fi是2的幂的话会出现重复的数字。当然用4的幂的话,有些数字就称不出了,比如2。

    [0] 评论
  • 24楼
    2010-12-23 13:27 brgka

    上面说了用3的幂做系数得到的数各不相同。又因为这样能得到的最大的数就是(3^n-1)/2 (从1加到3^(n-1)相当于用了所有的砝码),得到的最小的数当然是1,所以用这样的砝码刚刚好。
    如果要问怎样称1到M的重量,只要求最小的n使得(3^n-1)/2>=M就好了

    [0] 评论
  • 25楼
    2010-12-29 11:12 iexjc

    叹为观止,异常强大!

    [0] 评论
  • 26楼
    2011-01-10 13:58 bossxp

    希望我的孩子以后上学时能有机会接触,我们学习时太枯燥了。

    [0] 评论
  • 27楼
    2011-03-05 20:40 sx349

    一眼就看出来了...组合数学 母函数(生成函数) 这里面X是没有实际意义的 有用的是系数...
    话说当时我们做这类题的时候都在纠结放苹果只能放奇数个、放梨只能放一个之类的问题...

    [0] 评论
  • 28楼
    2012-02-15 19:46 shaw_2010

    犀利

    [0] 评论
  • 29楼
    2012-05-21 17:21 梁兵兵

    思路如下,如果只许加不许减,可以用1,2,4,8……2^n,用2进制就能表达,即在2^n里用1或者0表示“使用”/“不使用”状态。但根据题意,还可以存在“减”这个方法,即“加”/“空”/“减”这三种状态。于是,用“3进制”就能完美解题了。

    [0] 评论
  • 30楼
    2012-05-21 17:22 梁兵兵

    强大的“3进制”啊。

    [0] 评论

显示所有评论

你的评论

登录 发表评论

钓主
钓主 数学博士

作者的其他文章

更多科研事,扫码早知道

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2015] 0609-239号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区