Competition problem — Combinatorics

Library / /29 of 29

Combinatorics Difficulty 6.1 National olympiad Prove it Ukraine

There are $2012$ piles of stones. The first pile contains $2^0$ stones, the second pile contains $2^1$ stones, the third pile contains $2^2$ stones, and so on. The $2012$ -th pile contains $2^{2011}$ stones. At one step, one can pick three piles and add $2$ stones to the first pile, $3$ stones to the second pile, and $4$ stones to the third pile, or pick any three piles and take $2$ stones out of the first pile, $3$ stones out of the second pile, and $4$ stones out of the third pile, provided that each pile has enough stones. Is it possible after a finite number of such operations to get exactly $3^{1005}$ stones in each pile?

Solution

After each operation the total number of stones changes by a number which is divisible by $9$ . At the end, the total number is $2012 \cdot 3^{1005}$ , which is divisible by $9$ . However, at the starting moment the total number is $2^0 + 2^1 + 2^2 + \ldots + 2^{2011} = 2^{2012} - 1$ , which is not divisible by $9$ . Indeed, $2012 = 335 \cdot 6 + 2$ , $2^6 = 64 = 1 \pmod{9}$ , therefore
$2^{2012} - 1 = (2^6)^{335} \cdot 2^2 - 1 = 4 - 1 = 3 \pmod{9}.$

Looking for a route rather than 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.