Browse · MathNet
PrintFinal Round
Belarus counting and probability
Problem
Bob cuts an apple into either or pieces. Then he cuts one of these pieces into either or pieces. He repeats this procedure several times. Can Bob obtain small bits of the apple?
Solution
Answer: yes, he can. If Bob cuts a piece of the apple into pieces, then the total number of the pieces increases by . If Bob cuts a piece of the apple into pieces, then the total number of the pieces increases by . So, if Bob makes cuts into pieces and cuts into pieces, then the apple ( piece) is cut into exactly pieces.
It remains to show that there exist nonnegative integer numbers and such that . This equality is equivalent to the equality .
We divide the summands in the right-hand side of the last equality into some groups: We show that the sum of the numbers in each group is divisible either by or by . Indeed, , , , , and the last sum is divisible by since each summand of this sum is divisible by .
Therefore, the right-hand side of the equality has the form . Thus Bob can cut the apple into pieces (it is sufficient to make cuts into pieces and cuts into pieces).
It remains to show that there exist nonnegative integer numbers and such that . This equality is equivalent to the equality .
We divide the summands in the right-hand side of the last equality into some groups: We show that the sum of the numbers in each group is divisible either by or by . Indeed, , , , , and the last sum is divisible by since each summand of this sum is divisible by .
Therefore, the right-hand side of the equality has the form . Thus Bob can cut the apple into pieces (it is sufficient to make cuts into pieces and cuts into pieces).
Final answer
yes
Techniques
Invariants / monovariantsModular Arithmetic