Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Feb 11, 2010

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

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

    ReplyDelete
  2. Thanx Shantanu.. Correct Solution :)

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

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

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

    ReplyDelete