Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Pebble Piles

Puzzle

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?

Source

From some compendium of Math competition problems.

Solution

Since all three piles are odd, the first operation must be 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 with 1 pebble each.

Previous Puzzle: Chameleons

On an island live 13 purple, 15 yellow and 17 maroon chameleons. When two chameleons of different colors meet, they both change into the third color. Is there a sequence of pairwise meetings after which all chameleons have the same color?

Next Puzzle: Rope Escape

Rajeev is trapped atop a building 200m high. He has with him a rope 150m long. There is a hook at the top where he stands. Looking down, he notices that midway between him and the ground, at a height of 100m, there is a ledge with another hook. In his pocket lies a Swiss knife. Hmm... how might he be able to come down using the rope, the two hooks and the Swiss knife?

10 Sep 2008
© Copyright 2008—2017, Gurmeet Manku.