## Return to Answer

6 added 108 characters in body; edited body

## 1. The problem

You are given two buckets of A and B volume units of water. Can you measure C volume units out of those two buckets (not using any other container).

Hint:

• What are the values of C that there is a solution, or there is no solution.
• What is the minimum number of steps to get C, if you know there exists a solution.
• Find the algorithm to describe the solution.

## 2. Analysis of the general problem:

• There will be no solution if C > A + B, or C is not divisible by gcd(A,B).
• The solution when C = A + B is just straightforward.

## 3. Formal properties of the problem

• a) (Property of C given (A,B)) : For any value of A and B, there exists a solution if-and-only-if C <= A+B and gcd(A,B) | C
• b) (How to describe C given (A,B)) : If there exist a solution, then there exists a pair of natural numbers (x, y) so that C = Ax - By and C <= A+B.
• c) (An easier way to know if there exists a solution) : If there exist a pair of natural numbers (x,y) such that C = Ax - By and C <= A+B, then there exist a solution to the problem

## 4. Proof of the above mentioned properties:

• a) Other people in this thread have given the hint on how to prove this. You can prove yourself by using "proof by contradiction".
• b) Straight forward if you look at the analysis part (part 2).
• c) The following algorithm (in part 5) will make sure that it would output a solution with the smallest amount of steps.

## 5. AlgorithmAlgorithms to generate the solution

• b) Algorithm to find the pair (x,y)

[to be described here later]

• c) Algorithm to generate a solution given the quintet of (A,B,C,x,y)

## 6.Correctnessofthealgorithms

Hope that helps. Thanks

5 deleted 57 characters in body; added 82 characters in body

## 1. The problem

You are given two buckets of A and B volume units of water. Can you measure C volume units out of those two buckets (not using any other container).

Hint:

• What are the values of C that there is a solution, or there is no solution.
• What is the minimum number of steps to get C, if you know there exists a solution.
• Find the algorithm to describe the solution.

## 2. Analysis of the general problem:

• There there will be no solution if C > A + B, or C is not divisible by gcd(A,B).
• The case where solution when C = A + B is just straightforward, and is not considered in the formal description of this problem.

## 3. Formal properties of the problem

• a) (Property of C given (A,B)) : For any value of A and B, there exists a solution if-and-only-if C <= A+B and gcd(A,B) | C
• b) (How to describe C given (A,B)) : If there exist a solution, then there exists a pair of natural numbers (x, y) so that C = Ax - By.
• c) (An easier way to know if there exists a solution) : If there exist a pair of natural numbers (x,y) such that C = Ax - By, then there exist a solution to the problem

## 4. Proof of the above mentioned properties:

• a) Other people in this thread have proved like abovegiven the hint on how to prove this. You can prove yourself by using "proof by contradiction".
• b) Straight forward if you look at the analysis part (part 1)2).
• c) The following algorithm (in part 45) will make sure that it would output a solution with the smallest amount of steps.

## 5. Algorithm to generate the solution

• b) Algorithm to find the pair (x,y)

[to be described here later]

• c) Algorithm to generate a solution given the quintet of (A,B,C,x,y)

Hope that helps. Thanks

4 added 432 characters in body

## 1. Theproblem

You are given two buckets of A and B volume units of water. Can you measure C volume units out of those two buckets (not using any other container).

Hint:

• What are the values of C that there is a solution, or there is no solution.
• What is the minimum number of steps to get C, if you know there exists a solution.
• Find the algorithm to describe the solution.

## 2. Analysis of the general problem:

• There there will be no solution if C > A + B, or C is not divisible by gcd(A,B).
• The case where C = A + B is just straightforward, and is not considered in the formal description of this problem

## 3. Formal properties of the problem

• a) (Property of C given (A,B)) : For any value of A and B, there exists a solution if-and-only-if C <= A+B and gcd(A,B) | C
• b) (How to describe C given (A,B)) : If there exist a solution, then there exists a pair of natural numbers (x, y) so that C = Ax - By.
• c) (An easier way to know if there exists a solution) : If there exist a pair of natural numbers (x,y) such that C = Ax - By, then there exist a solution to the problem

## 4. Proof of the above mentioned properties:

• a) Other people have proved like above.
• b) Straight forward if you look at the analysis part (part 1)
• c) The following algorithm (in part 4) will make sure that it would output a solution with the smallest amount of steps.

## 5. Algorithm to generate the solution

• b) Algorithm to find the pair (x,y)

[to be described here later]

• c) Algorithm to generate a solution given the quintet of (A,B,C,x,y)

Hope that helps. Thanks

3 added 510 characters in body
2 added 121 characters in body
1