正文

灌水问题——经典智力题推而广(转帖)2007-04-10 10:36:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/goal00001111/24740.html

分享到:

原文地址http://www.oursci.org/ency/math/002.htm
倒水问题的经典形式是这样的:

  “假设有一个池塘,里面有无穷多的水。现有2个空水壶,容积分别为5升和6升。问题是如何只用这2个水壶从池塘里取得3升的水。”

  当然题外是有一些合理的限制的,比如从池塘里灌水的时候,不管壶里是不是已经有水了,壶一定要灌满,不能和另一个壶里的水位比照一下“毛估估”(我们可以假设壶是不透明的,而且形状也不同);同样的,如果要把水从壶里倒进池塘里,一定要都倒光;如果要把水从一个壶里倒进另一个壶里,也要都倒光,除非在倒的过程中另一个壶已经满了;倒水的时候水没有损失(蒸发溢出什么的)等等等等。

  事实上,要解决上面这题,你只要用两个壶中的其中一个从池塘里灌水,不断地倒到另一个壶里,当第二个壶满了的时候,把其中的水倒回池塘里,反复几次,就得到答案了。以5升壶(A)灌6升壶(B)为例:

     A  B
     0  0 
     5  0  A→B 
     0  5 
     5  5  A→B 
     4  6 
     4  0  A→B 
     0  4 
     5  4  A→B 
     3  6

  现在我们问,如果是多于2只壶的情况怎么办(这样一来就不能用上面的循环倒水法了)?如何在倒水之前就知道靠这些壶是一定能(或一定不能)倒出若干升水来的?试举数例:
  1) 两个壶:65升和78升,倒38升和39升。
  2) 三个壶:6升,10升和45升,倒31升。

  我们可以看到,在1)中,65=5×13,78=6×13,而39=3×13。所以如果把13升水看作一个单位的话(原题中的“升”是没有什么重要意义的,你可以把它换成任何容积单位,毫升,加仑——或者“13升”),这题和最初的题目是一样的。而38升呢?显然是不可能的,它不是13的倍数,而65升和78升的壶怎么也只能倒出13升的倍数来。也可以这样理解:这相当于在原题中要求用5升和6升的壶倒出38/39升来。

  那么2)呢?你会发现,只用任何其中两个壶是倒不出31升水的,理由就是上面所说的,(6,10)=2,(6,45)=3,(10,45)=5,(这里(a,b)是a和b的最大公约数),而2,3,5均不整除31。可是用三个壶就可以倒出31升:用10升壶四次,6升壶一次灌45升壶,得到1升水,然后灌满10升壶三次得30升水,加起来为31升。

  一般地我们有“灌水定理”:

  “如果有n个壶容积分别为A1,A2,……,An(Ai均为大于0的整数)设w为另一大于0的整数。则用此n个壶可倒出w升水的充要条件为:
  1) w小于等于A1+A2+......+An;
  2) w可被(A1,A2,......,An)(这n个数的最大公约数)整除。”

  这两个条件都显然是必要条件,如果1)不被满足的话,你连放这么多水的地方都没有。2)的道理和上面两个壶的情况完全一样,因为在任何步骤中,任何壶中永远只有(A1,A2,......,An)的倍数的水。

  现在我们来看一下充分性。在中学里我们学过,如果两个整数a和b互素的话,那么存在两个整数u和v,使得ua+vb=1。证明的方法很简单:在对a和b做欧几里德辗转相除时,所有中间的结果,包括最后得到的结果显然都有ua+vb的形式(比如第一步,假设a小于b,记a除b的结果为s,余数为t,即b=sa+t,则t=(-s)a+b,即u=-s,v=1)。而两个数互素意味着欧几里德辗转相除法的最后一步的结果是1,所以1也可以记作ua+vb的形式。稍微推广一点,如果(a,b)=c,那么存在u和v使得ua+vb=c(两边都除以c就回到原来的命题)。

  再推广一点,如果A1,A2,……,An是n个整数,(A1,A2,......,An)=s,那么存在整数U1,U2,……,Un,使得

       U1A1 + U2A2 + ...... + UnAn = s.    (*)

  在代数学上称此结果为“整数环是主理想环”。这也不难证,只要看到

    (A1,A2,A3,A4,......,An) = ((((A1,A2),A3),A4),......,An).

  也就是说,可以反复应用上一段中的公式:比如三个数a,b,c,它们的最大公约数是d。假设(a,b)=e,那么(e,c)=((a,b),c)=d。现在有u1,u2使得u1a+u2b=e,又有v1,v2使得v1e+v2c=d,那么 

      (v1u1)a+(v1u2)b+(v2)c=d.

  好,让我们回头看“灌水定理”。w是(A1,A2,......,An)的倍数,根据上节的公式(*),两边乘以这个倍数,我们就有整数V1,V2,……,Vn使得 V1A1 + V2A2 + ...... + VnAn = w.注意到Vi是有正有负的。

  这就说明,只要分别把A1,A2,……,An壶,灌上V1,V2,……,Vn次(如果Vi是负的话,“灌上Vi次”要理解成“倒空-Vi次”),就可以得到w升水了。具体操作上,先求出各Vi,然后先往Vi是正数的壶里灌水,灌1次就把Vi减1。再把这些水到进Vi是负数的壶里,等某个壶灌满了,就把它倒空,然后给这个负的Vi加1,壶之间倒来倒去不变更各Vi的值。要注意的是要从池塘里灌水,一定要用空壶灌,要倒进池塘里的水,一定要是整壶的。这样一直到所有Vi都是0为止。

  会不会发生卡住了,既不能灌水又不能倒掉的情况?不会的。如果有Vi仍旧是负数,而Ai壶却没满:那么如果有其它Vi是正的壶里有水的话,就都倒给它;如果有其它Vi是正的壶里没水,那么就拿那个壶打水来灌(别忘了给打水的壶的Vi减1);如果根本没有任何Vi是正的壶了——这是不可能的,这意味着w是负的。有Vi仍旧是正数,而Ai壶却没满的情况和这类似,你会发现你要用到定理中的条件1)。

  这样“灌水定理”彻底得证。当然,实际解题当中如果壶的数目和容积都比较大的话,手工来找(*)中的各Ui比较困难,不过可以写个程序,连倒水的步骤都算出来。最后要指出的一点是,(*)中的Ui不是唯一的,所以倒水的方式也不是唯一的。

阅读(2175) | 评论(0)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

暂无评论
您需要登录后才能评论,请 登录 或者 注册