From the 2001 Moscow Mathematical Olympiad:
Before you are three piles of stones. One contains 51 stones, one 49 stones, and one 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?
|
SelectClick for Answer> |
No. If at any point the number of stones in each pile is a multiple of the same odd number a, then this will remain true after any number of operations. On the first move we’re forced to create two piles of 100 and 5 stones (both divisible by 5), or 56 and 49 stones (both divisible by 7), or 51 and 54 stones (both divisible by 3). Whichever course we choose, all subsequent operations will produce piles divisible by that odd factor. This prevents us from producing piles of single stones.
|