### Pebble Piles

Problem: You are given three piles with 5, 49 and 51 pebbles respectively. Two operations are allowed:
(a) merge two piles together or
(b) divide a pile with an even number of pebbles into two equal piles.

Is there a sequence of operations that would result in 105 piles with one pebble each?

Update(12/02/10):
Solution: Posted by Shantanu Gangal (CSE IITB Alumnus and BCG Consultant) in comments!!

1. Not possible.

Lemma: If the gcd of all the pile sizes is a odd number (>1), then the objective isn't possible.
Proof: Assume that the common gcd of piles is n, an odd no > 1. Hence, both the operation will keep this invariance. As a result, you can never create a pile of size < n.

Now, the only operation you can do at {5, 49, 51} is (a).
But, 3| {51, 54}; 5|{5, 100} and 7|{49, 56}. Hence the desired piling isn't possible.

2. Thanx Shantanu.. Correct Solution :)

3. im not sure of my solution..
this is mine..
if after all such operations we get 105 single pebbled piles...
the last operation would be dividing a pile of 2 into 2 piles of 1 pebble.
in that way the proceeding from back
we get 52 piles of 2 pebbles and 1 single pebbled pile.There is no pile with equal number if pebbles as this 1 pebbles pile.
So this is not possible...

4. I am sorry.. I did not get this. Why is this not possible?

5. i was not sure of my soln....
later after posting it, i came 2 know dat i was wrong...

6. :) chalega :P