Maths Olympiad Prep

Library / /57 of 155

Combinatorics Difficulty 5.7 AIME, harder Prove it Saudi Arabia

How many ways are there to insert plus signs ++ between the digits of number 111111111111111 \ldots 111 which includes thirty digits 11 so that the result will be a multiple of 3030?

Solution

Let SS be the final sum, then the necessary conditions are 3S3|S, 10S10|S.
One can check that for every positive integer nn then S(n)n(mod9)S(n) \equiv n \pmod{9} which implies that for all ways to insert the plus signs, we have
S1+1+1++10(mod3). S \equiv 1+1+1+\cdots+1 \equiv 0 \pmod{3} .
Then the condition that divisible by 33 is always satisfied.
Suppose that we inserted mm signs in total, then we have m+1m+1 parts. Each part is a positive integer that ends with 11 so the rightmost digit of SS is equal to or congruent to m+1m+1 modulo 1010. Then we must have m{9,19,29}m \in\{9,19,29\}.
It is easy to see that the given condition is also the sufficiency condition. Denote a1,a2,,am+1a_{1}, a_{2}, \ldots, a_{m+1} as the number of digits of each part that partitioned from mm signs then
a1+a2+a3++am+1=30 a_{1}+a_{2}+a_{3}+\cdots+a_{m+1}=30
This equation has (29m)\binom{29}{m} solutions. Therefore the number of ways to insert the plus signs is (299)+(2919)+(2929)\binom{29}{9}+\binom{29}{19}+\binom{29}{29}.

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.