量杯倒水游戏

| Comments

量杯倒水

量杯倒水

这个问题常见于趣味题和面试题,题意大概是这样的:有两个只有最大刻度的量杯(如10毫升,3毫升), 并且有无限量的水。求怎么倒出x毫升的水?

思路与猜想

首先我们来操作一下,例如倒出4毫升的水,同时把大小量杯表示为a,b

  1. b装满,倒入a(a有3ml,b有0ml)
  2. b再装满,倒入a(a有6ml,b有0ml)
  3. b再装满,倒入a(a有9ml,b有0ml)
  4. b再装满,倒入a(a有10ml,b有2ml)
  5. a倒掉,b倒入a(a有2ml,b有0ml)
  6. 重复2-4的动作(此时a有10ml,b有1ml)
  7. a倒掉,b倒入a(a有1ml,b有0ml)
  8. b装满,倒入a(a有4ml,b有0ml)

假如我们再继续操作的话,还可以找到7ml,这样0ml~10ml的体积都是可以测量出来的。这是不是一般规律?

虽然我们进行了许多次操作,但操作是有规律的:b总是往a倒水直到a装满,这时b会剩余一点。 这样才能得到不同于a,b的体积。我们重复这个操作的过程,不考虑a装满的情况, 在a中出现的水t可以用t=mb-na来表示(a>t>=0,m>=0,n>=0)。其中m可以表示为往a倒水的次数, n表示a装满的次数。

首先考虑一下a,b不是互质的情况,假设他们的最大公约数为u,那么狠显然没法倒出t小于u的体积。 这种情况可以归结为两边除去u的情况。

现在再来考虑a,b互质的情况,我们需要考虑的是,对于t,是否都存在m,n使t=mb-na成立?

贝祖定理

我们从数学归纳法出发,很明显t=0的情况是满足要求的,假设t=1的要求也能够满足, 那么有t=mb-na成立就可以推导出t+1=m1b-n1a+m2b-n2a也是符合mb-na的。

如何证明存在m,n使得mb-na=1?这个倒不用自己动手,有个叫贝祖定理的数学定理,可以很容易推导出这个结论。

从wiki上看到的资料,贝祖定理可以证明a,b互质,存在xa+yb=1,其中x,y为整数 不过好像跟我们的要求有点出入。不过没关系,很显然x,y如果没有不等于0的话,必须有个是负数,

如果x是负数,显然符合要求,如果y是负数,那么总存在一个数k(k>0)使得y+ka>0,那么 1=xa+yb=xa+yb-kab+kab=(x-ka)a+(y+ka)b,这样也是可以符合要求的。

所以,按照我们的操作方式,假设a,b的最大公约数为u,就可以找到0ml,uml,2uml…aml的体积。

再思考

如果有多个量杯,情况会是怎样?

要倒出一定量的水,上述操作是否是最快的?

Comments