Measure one litre using two vessels and infinite water supply
There are two vessels of capacities ‘a’ and ‘b’ respectively. We have infinite water supply. Give an efficient algorithm to make exactly 1 litre of water in one of the vessels. You can throw all the water from any vessel any point of time. Assume that ‘a’ and ‘b’ are Coprimes.
Like GCD
Let V1 be the vessel of capacity ‘a’ and V2 be the vessel of capacity ‘b’ and ‘a’ is smaller than ‘b’.
1) Do following while the amount of water in V1 is not 1.
….a) If V1 is empty, then completely fill V1
….b) Transfer water from V1 to V2. If V2 becomes full, then keep the remaining water in V1 and empty V2
2) V1 will have 1 litre after termination of loop in step 1. Return.
Let ‘a’ be the capacity of vessel V1 and ‘b’ be the capacity of V2. Since we repeatedly transfer water from V1 to V2 until V2 becomes full, we will have ‘a – b (mod a)’ water in V1 when V2 becomes full first time . Once V2 becomes full, it is emptied. We will have ‘a – 2b (mod a)’ water in V1 when V2 is full second time. We repeat the above steps, and get ‘a – nb (mod a)’ water in V1 after the vessel V2 is filled and emptied ‘n’ times. We need to prove that the value of ‘a – nb (mod a)’ will be 1 for a finite integer ‘n’.
There are two vessels of capacities ‘a’ and ‘b’ respectively. We have infinite water supply. Give an efficient algorithm to make exactly 1 litre of water in one of the vessels. You can throw all the water from any vessel any point of time. Assume that ‘a’ and ‘b’ are Coprimes.
Like GCD
Let V1 be the vessel of capacity ‘a’ and V2 be the vessel of capacity ‘b’ and ‘a’ is smaller than ‘b’.
1) Do following while the amount of water in V1 is not 1.
….a) If V1 is empty, then completely fill V1
….b) Transfer water from V1 to V2. If V2 becomes full, then keep the remaining water in V1 and empty V2
2) V1 will have 1 litre after termination of loop in step 1. Return.
void Vessel:: makeOneLitre(Vessel &V2){ // solution exists iff a and b are co-prime if (gcd(capacity, V2.capacity) != 1) return; while (current != 1) { // fill A (smaller vessel) if (current == 0) current = capacity; cout << "Vessel 1: " << current << " Vessel 2: " << V2.current << endl; // Transfer water from V1 to V2 and reduce current of V1 by // the amount equal to transferred water current = current - V2.transfer(current); } // Finally, there will be 1 litre in vessel 1 cout << "Vessel 1: " << current << " Vessel 2: " << V2.current << endl;}int Vessel::transfer(int amount){ // If the vessel can accommodate the given amount if (current + amount < capacity) { current += amount; return amount; } // If the vessel cannot accommodate the given amount, then // store the amount of water transferred int transferred = capacity - current; // Since the vessel becomes full, make the vessel // empty so that it can be filled again current = 0; return transferred;}
To prove this, let us consider the following property of coprime numbers.
For any two coprime integers ‘a’ and ‘b’, the integer ‘b’ has a multiplicative inverse modulo ‘a’. In other words, there exists an integer ‘y’ such that
(See 3rd point here). After ‘(a – 1)*y’ iterations, we will have ‘a – [(a-1)*y*b (mod a)]‘ water in V1, the value of this expression is ‘a – [(a - 1) * 1] mod a’ which is 1. So the algorithm converges and we get 1 litre in V1.
https://en.wikipedia.org/wiki/Coprime_integers
two integers a and b are said to be relatively prime, mutually prime, or coprime (also spelled co-prime)[1] if the only positive integer that evenly divides both of them is 1.
Two jars - Algoritmy.net
You have two jars, the first one has a 3 liters capacity, the second one 5 liters. You also have an unlimited source of water. Measure exactly 4 liters of water.
Ruby solution:
http://codegolf.stackexchange.com/questions/5409/water-bucket-problem
http://www.cut-the-knot.org/ctk/Water.shtml
Measuring 6 Liters Puzzle - Solution
http://www.mathsisfun.com/puzzles/measuring-6-liters-solution.html
Measuring 6 Liters
You are going to mix up some concrete, and in order to get it just right you need exactly 6 liters.
But you only have a 4-liter and a 9-liter bucket.
9-3=6, so we need 4, 4-1=3, so we need 1.
Read full article from Measure one litre using two vessels and infinite water supply
For any two coprime integers ‘a’ and ‘b’, the integer ‘b’ has a multiplicative inverse modulo ‘a’. In other words, there exists an integer ‘y’ such that
(See 3rd point here). After ‘(a – 1)*y’ iterations, we will have ‘a – [(a-1)*y*b (mod a)]‘ water in V1, the value of this expression is ‘a – [(a - 1) * 1] mod a’ which is 1. So the algorithm converges and we get 1 litre in V1.https://en.wikipedia.org/wiki/Coprime_integers
two integers a and b are said to be relatively prime, mutually prime, or coprime (also spelled co-prime)[1] if the only positive integer that evenly divides both of them is 1.
Two jars - Algoritmy.net
You have two jars, the first one has a 3 liters capacity, the second one 5 liters. You also have an unlimited source of water. Measure exactly 4 liters of water.
Ruby solution:
http://codegolf.stackexchange.com/questions/5409/water-bucket-problem
http://www.cut-the-knot.org/ctk/Water.shtml
Measuring 6 Liters Puzzle - Solution
http://www.mathsisfun.com/puzzles/measuring-6-liters-solution.html
Measuring 6 Liters
You are going to mix up some concrete, and in order to get it just right you need exactly 6 liters.
But you only have a 4-liter and a 9-liter bucket.
9-3=6, so we need 4, 4-1=3, so we need 1.
Read full article from Measure one litre using two vessels and infinite water supply
