proof


  • 0
    Y

    Re: [share my simulated method with explanation](no math theory [c++])

    If it can be z>x+y, then we have x<y → f(x,y,z) ↔f(x,y-x,z), which means if we can measure z with x Land y L jugs, we also can measure z with x, and y-x jugs, vice versa.

    The reason is for each operation allowed:
    (1) Fill any of the jugs completely with water.
    For x,y jugs, y can be obtained by x jug and x-y jug summed up together.
    For x, y-x jugs, y-x can be obtained by pouring x L water from y jug to x jug.

    (2) Empty any of the jugs.
    Obvious

    (3) Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.
    Situation 1: If we keep pouring x L water from x jug into y jug, supposed initially there is a L water in y jug, eventually there will be x-(y-a)%x remained in x jug. In this case, if we do the same operations with x jug and y-x jug, eventually we can have x-(y-x-a)%x L remained in x jug , and x-(y-x-a)%x = x-(y-a)%x;
    Situation 2: If we keep pouring x L water from y jug into x jug, supposed there is a L water in x jug initially, eventually there will be y%x L left in y jug. And in the same operations, eventually we can have (y-x)%x L water left in y-x jug, which is the same as y%x.

    So, iteratively replace f(x,y,z) with f(x, y-x,z) if y>x, or with f(x-y,y,z) if y<x, till x=y, then if z%x==0, f(x,y,z) be true. This process is isomorphic gcd problem.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.