there are 2 urns with some balls in each of them. Either one can remove same number of balls from each or one can double the number of balls in one of them. How to empty the 2 urns.
Solution
Say urn containing larger number of balls is A and number of balls
m and the other urn is B and number of balls n. There are 2 method
and 1st method is straight forward and 2nd
method is more elegant.
Method 1)
we have to reduce both and if n =1 then double the number of balls
and double again.
If n = 2 then double the number of balls.
if n >2 remove n-2 balls from both then balls in A >2 (as m
>n) and in B 2 and double the number of balls..
As long as number of balls in A >4 keep doubling the number of
balls in B and remove 2 from each.
As the number of balls in A keeps decreasing by 2 it shall be
reduced to 3 or 4(depending on odd or even after removing m-2). In
case it is 4 then after doubing the number of balls in B it becomes
4 then remove 4 from both.
In case it is 3 and in b 2 (do not double it) remove 1 from both
so number of balls left is 2 in A and 1 in B and then double the the
number of balls in b to 2 and remove 2 balls from both the urns..
Method 2)
Let k be the highest number such that m > 2**k( that is if m
is a power or 2 then take m/2) .
Keep doubling the number of balls in B so that N(the number after
doubling) N >2**k
If both numbers are same then remove them and both the urns are
empty
m > 2**K and n > 2**K then remove 2**K then m <= 2**K
and n < 2**K.
Interchange the roles of m and n if m < n.
So each time the value is larger urn becomes ½ or less of the
previous. And the lower one becomes not more than the previous larger
Keep repeating the process until both are same as they are reducing
the 2 numbers will converge to be same.
To illustrate as an example let m = 69 and n = 10
Keep doubling n, i.e 20 , 40, 80
Remove 64 that is m = 5 n = 16( > 8)
Then keep doubling m = 10
Remove 8 so m =2 and n = 8
Keep doubling m till it is 8 and remove 8 from both
No comments:
Post a Comment