|
6
|
|
edited Dec 30 2010 at 13:08 |
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. Algorithm Algorithms to generate the solution
6. Correctness of the algorithms
Hope that helps.
Thanks
|
|
|
|
|
5
|
|
edited Dec 29 2010 at 13:10 |
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
Hope that helps.
Thanks
|
|
|
|
|
4
|
|
edited Dec 29 2010 at 13:05 |
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 C = A + B is just straightforward, and is not considered in the formal description of this problem
2
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
3
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.
4
5. Algorithm to generate the solution
Hope that helps.
Thanks
|
|
|
|
3
|
|
edited Dec 29 2010 at 12:54 |
1. 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
2. Formal description 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 exist exists a pair of natural numbers (x, y) so that C = Ax - By.
- b
- c) (An easier way to know if there exists a solution) : If there exist a pair of natural numbers (x,y), x,y) such that C = Ax - By, then there exist a solution to the problem
3. Proof of the formal descriptionabove mentioned properties:
- a) Other people have proved like above.
- b) Straight forward if you look at the analysis part (part 1)
- b
- c) The following algorithm (in part 4) will make sure that it would output a solution with the smallest amount of steps.
4. Algorithm to generate the solution
|
|
|
|
|
2
|
|
edited Dec 29 2010 at 12:04 |
Analysis of the general problem:
- There there will be no solution if C > A + B
- The case where C = A + B is just straightforward, and is not considered in the formal description of this problem
Formal description of the problem
- a) If there exist a solution, then there exist a pair of natural numbers (x, y) so that C = Ax - By.
- b) If there exist a pair of natural numbers (x,y), then there exist a solution to the problem
Proof of the formal description
- a) Straight forward if you look at the analysis part (part 1)
- b) The following algorithm (in part 4) will make sure that it would output a solution with the smallest amount of steps.
Algorithm to generate the solution
- a) Algorithm to find the pair (x,y)
[to be described here later]
- b) Algorithm to generate a solution given the quintet of (A,B,C,x,y)
(to be continued in part 4)
Algorithm: http://img585.imageshack.us/img585/4756/waterbucketgeleralalgor.png
Hope that helps.
Thanks
|
|
|
|
|
1
|
|
answered Dec 29 2010 at 11:46 |
Analysis of the general problem:
- There there will be no solution if C > A + B
- The case where C = A + B is just straightforward, and is not considered in the formal description of this problem
Formal description of the problem
- a) If there exist a solution, then there exist a pair of natural numbers (x, y) so that C = Ax - By.
- b) If there exist a pair of natural numbers (x,y), then there exist a solution to the problem
Proof of the formal description
- a) Straight forward if you look at the analysis part (part 1)
- b) The following algorithm (in part 4) will make sure that it would output a solution with the smallest amount of steps.
Algorithm to generate the solution
- a) Algorithm to find the pair (x,y)
- b) Algorithm to generate a solution given the quintet of (A,B,C,x,y)
(to be continued in part 4)
|
|
|
