Maths Olympiad Prep

Library / Greece — Selection Examination /30 of 61

Greece — Selection Examination

Combinatorics Difficulty 6.0 AIME, harder Prove it Greece

A pupil has 77 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 20092009 pieces of paper?

Solution

Let he choose at the beginning α1\alpha_1 from the seven pieces and each of them into seven pieces. Then he will have totally 7−α1+7α1=7+6α17 - \alpha_1 + 7\alpha_1 = 7 + 6\alpha_1 pieces of paper. Suppose that in the next step he chooses α2\alpha_2 pieces of paper and cuts each of them into seven pieces. Then he will have totally 7+6α1−α2+7α2=7+6(α1+α2)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(α1+α2+⋯+ακ)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(α1+α2+⋯+ακ)=2009⇒6(α1+α2+⋯+ακ)=2002, 7 + 6(\alpha_1 + \alpha_2 + \dots + \alpha_\kappa) = 2009 \Rightarrow 6(\alpha_1 + \alpha_2 + \dots + \alpha_\kappa) = 2002,
which is absurd, because 20022002 is not divided by 66. Hence it is not possible for him to have some time 20092009 pieces of paper.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.