Login/RegisterInterview Puzzles :: Discussion
-
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?
Explanation :
No Best Answer on this question yet!Not Yet Asked in Any of the Companies
Since all three piles are odd, the first operation must be the merger of two existing piles, resulting in an even-sized pile and an odd-sized pile. Let g denote the greatest common divisor of these two pile sizes. Since one pile is odd sized and the other pile is even sized, g must be odd. For odd g, no matter what sequence of operations is carried out (merger of two existing piles or division of an even pile into two equal piles), every pile size will continue to be a multiple of g. If g > 1, then we can never reach a configuration where all piles are size 1. Now, starting with {5, 49, 51}, three states are possible: {54, 51}, {5, 100} and {49, 56}. The GCD is 3, 5 and 7, respectively, in these three states. So we can never get 105 piles of 1 pebble each.
