Competition problem — Combinatorics

Library / /22 of 48

Combinatorics Difficulty 6.0 AIME, harder Prove it Greece

A pupil has $7$ pieces of paper. He chooses some of them and cuts each of them into seven pieces. In the sequel, he chooses some of the pieces and cuts each of them into seven pieces. He continues this procedure many times with the pieces he has in hands every time. Is it possible to have some time $2009$ pieces of paper?

Solution

Let he choose at the beginning $\alpha_1$ from the seven pieces and each of them into seven pieces. Then he will have totally $7 - \alpha_1 + 7\alpha_1 = 7 + 6\alpha_1$ pieces of paper. Suppose that in the next step he chooses $\alpha_2$ pieces of paper and cuts each of them into seven pieces. Then he will have totally $7 + 6\alpha_1 - \alpha_2 + 7\alpha_2 = 7 + 6(\alpha_1 + \alpha_2)$ pieces of paper. If he continues this procedure $\kappa$ times, then he will have totally $7 + 6(\alpha_1 + \alpha_2 + \dots + \alpha_\kappa)$ pieces of paper. Therefore we are looking for the value of $\kappa$ satisfying the equation
$7 + 6(\alpha_1 + \alpha_2 + \dots + \alpha_\kappa) = 2009 \Rightarrow 6(\alpha_1 + \alpha_2 + \dots + \alpha_\kappa) = 2002,$
which is absurd, because $2002$ is not divided by $6$ . Hence it is not possible for him to have some time $2009$ pieces of paper.

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.