Maths Olympiad Prep

Library / /10 of 24

Combinatorics Difficulty 6.1 National olympiad Prove it Belarus

Bob cuts an apple into either 2020 or 1414 pieces. Then he cuts one of these pieces into either 2020 or 1414 pieces. He repeats this procedure several times.
Can Bob obtain 1!+2!+3!++1013!+2014!1! + 2! + 3! + \dots + 1013! + 2014! small bits of the apple?

Solution

Answer: yes, he can.
If Bob cuts a piece of the apple into 2020 pieces, then the total number of the pieces increases by 1919. If Bob cuts a piece of the apple into 1414 pieces, then the total number of the pieces increases by 1313. So, if Bob makes xx cuts into 2020 pieces and yy cuts into 1414 pieces, then the apple (11 piece) is cut into exactly 1+19x+13y1 + 19x + 13y pieces.

It remains to show that there exist nonnegative integer numbers xx and yy such that 1+19x+13y=1!+2!+3!++1013!+2014!1 + 19x + 13y = 1! + 2! + 3! + \dots + 1013! + 2014!. This equality is equivalent to the equality 19x+13y=2!+3!+4!++1013!+2014!19x + 13y = 2! + 3! + 4! + \dots + 1013! + 2014!.

We divide the summands in the right-hand side of the last equality into some groups:
2!+3!+4!++1013!+2014!=(2!+3!+4!+5!)+(6!+8!)+(7!+9!+10!)+(11!+12!)+(13!+14!++1013!+2014!). \begin{align*} 2! + 3! + 4! + \dots + 1013! + 2014! &= (2! + 3! + 4! + 5!) + (6! + 8!) + \\ &\quad (7! + 9! + 10!) + (11! + 12!) + (13! + 14! + \dots + 1013! + 2014!). \end{align*}
We show that the sum of the numbers in each group is divisible either by 1313 or by 1919. Indeed, 2!+3!+4!+5!=152=8192! + 3! + 4! + 5! = 152 = 8 \cdot 19, 6!+8!=6!(1+78)=6!57=6!3!196! + 8! = 6! (1 + 7 \cdot 8) = 6! \cdot 57 = 6! \cdot 3! \cdot 19, 7!+9!+10!=7!(1+8!9+8!9!10)=7!793=7!61!137! + 9! + 10! = 7! (1 + 8! \cdot 9 + 8! \cdot 9! \cdot 10) = 7! \cdot 793 = 7! \cdot 61! \cdot 13, 11!+12!=11!(1+12)=11!1311! + 12! = 11! (1 + 12) = 11! \cdot 13, and the last sum 13!+14!++1013!+2014!13! + 14! + \dots + 1013! + 2014! is divisible by 1313 since each summand of this sum is divisible by 1313.

Therefore, the right-hand side of the equality has the form 19a+13b19a + 13b. Thus Bob can cut the apple into 1!+2!+3!++1013!+2014!1! + 2! + 3! + \dots + 1013! + 2014! pieces (it is sufficient to make aa cuts into 2020 pieces and bb cuts into 1414 pieces).

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.