From the 2001 Moscow Mathematical Olympiad:
Before you are three piles of stones: one containing 51 stones, second with 49 stones, and the third 5 stones.
On each move you can either combine two piles into one or divide any pile with an even number of stones into two equal piles.
Is it possible to end up with 105 piles, each containing a single stone?
If I split a pile that has an odd factor into two equal piles, then both new piles must also have that factor. And if I combine two piles with a common odd factor then the result has that factor too.
I have only three possible first moves since I have nothing splittable:
1) If I combine 51 and 5 then I have piles of 56 and 49 and all of my remaining piles will have a multiple of 7 stones, so I can't get to 105 piles
2) If I combine 51 and 49, then I have piles of 100 and 5 and all of my remaining piles have a multiple of 5 stones.
3) If I combine 49 and 5 then I have piles of 51 and 54 and all of my remaining piles have a multiple of 3 stones.
Regardless of my first move, afterwards all of my piles must be in multiples of an odd factor > 1. So Not only can't I end up with 105 piles of 1, but I can't even get a single pile of 1.
|
|
Posted by Paul
on 2016-05-17 15:26:44 |
Solution
