**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!!

Not possible.

ReplyDeleteLemma: 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.

Thanx Shantanu.. Correct Solution :)

ReplyDeleteim not sure of my solution..

ReplyDeletethis 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...

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

ReplyDeletei was not sure of my soln....

ReplyDeletelater after posting it, i came 2 know dat i was wrong...

:) chalega :P

ReplyDelete