Coin Piles
We are given two piles of coins containing A and B number of coins. In one move we can remove one coin from pile A and two coins from pile B or we can remove two coins from pile A and one from pile B.
(In other words, in one move, coins are removed from both piles and three coins should be removed in total.)
Given the number of coins in each pile, we have to find out whether it is possible to empty both the piles (in any number of moves) or not.
For example:
A = 1 coin
B = 2 coins
Is it possible to empty both piles ?
Yes. In one move we remove one coin from pile A and two coins from pile B.
Example 2 :
A = 3 coins
B = 2 coins
Is it possible to empty both piles?
Let’s see.
Suppose we remove two coins from pile A and one from pile B. What are we left with?
A = 1 coin
B = 1 coin
Can we make further moves now? No. We cannot. One move requires the removal of one coin from one pile and two coins from the other pile. We don’t have sufficient coins to make a move.
Let us suppose, we are given two piles A and B with ‘a’ and ‘b’ number of coins respectively.
A = ‘a’ coins
B = ‘b’ coins
There can be two kinds of moves:
1. We remove two coins from A and one coin from B.
2. We remove two coins from B and one coin from A.
Suppose we made ‘x’ moves of the first kind and ‘y’ moves of the second kind.
The number of coins left in pile A will be:
‘a’-2x-y
The number of coins left in pile B will be :
‘b’-2y-x
We want both piles to be empty after x+y moves have been made, i.e.
a-2x-y = 0 and
b-2y-x=0 i.e.
a=2x+y and
b = 2y+x
Total number of coins in both piles = a+ b = 2x+y+2y+x
= 3x + 3y = 3(x+y)
Hence, in order to empty both piles, the sum of coins in both piles should be a multiple of three.
Suppose, there are three coins in pile A and fifteen coins in pile B.
Total coins = 18 , a multiple of three.
But will we be able to empty the piles with valid moves?
Let’s see:
A = 3 coins
B = 15 coins
Move 1 : Remove one coin from A and two from B
A = 2 coins
B = 13 coins
Move 2 : Remove one coin from A and two from B
A = 1 coin
B = 11 coins
Move 3: Remove one coin from A and two from B
A =0 coins
B = 9 coins
No more moves can be made. Both piles are not empty, even though we kept removing one coin from the smaller pile and two coins from the larger pile.
We thus add an additional check: The size of the larger pile should not be more than twice the size of the smaller pile.
