Library / /20 of 25

, 2008

Number theory Difficulty 6.5 National olympiad Prove it Ukraine

There are five piles made of $42$ , $70$ , $105$ , $462$ , and $2009$ stones respectively. You are allowed to do the following: instead of two piles consisting of $a$ and $b$ stones you can make
* two piles of $a$ and $(a+b)$ stones;
* two piles of $a$ and $|a-b|$ stones.
You can also choose $k$ different piles, in which the total number of stones equals $nk$ where $n$ is some natural number, and create
* $k$ piles of $n$ stones in each one instead.
Can we make five piles each of which will consist of
a) $2008$ stones;
b) $2009$ stones
in finite number of steps?

Solution

a) We can easily find that the GCD of all the numbers $42$ , $70$ , $105$ , $462$ , and $2009$ is $7$ . For every operation you are allowed to perform the number of stones in piles stays divisible by $7$ . Therefore the answer is "No" as the number $2008$ is not divisible by $7$ .

b) In the second case the answer is "Yes". One of the ways to obtain the necessary set of piles is as follows: $(42,70,105,462,2009) \to (42,35,105,462,2009) \to (7,35,105,462,2009)$ . Now we have a pile of $7$ stones and can increase the other pile by $7$ stones $1061$ times: $\to (7,35+7 \times 1061,105,462,2009)$ . After that we divide the five derived piles into equal parts, in which the total number of stones equals $10045$ , and arrive at the desired result.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.