Maths Olympiad Prep

Library / /20 of 68

, 2017

Algebra Difficulty 4.8 AIME Prove it United States

Problem:

How many ways are there to insert +'s between the digits of 111111111111111111111111111111 (fifteen 1's) so that the result will be a multiple of 3030?

Solution

Solution:

Answer: 20022002

Note that because there are 1515 1's, no matter how we insert +'s, the result will always be a multiple of 33. Therefore, it suffices to consider adding +'s to get a multiple of 1010. By looking at the units digit, we need the number of summands to be a multiple of 1010. Because there are only 1515 digits in our number, we have to have exactly 1010 summands. Therefore, we need to insert 99 +'s in 1414 possible positions, giving an answer of (149)=2002\binom{14}{9} = 2002.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.