Maths Olympiad Prep

Library / Saudi Arabian Mathematical Competitions /215 of 395

Saudi Arabian Mathematical Competitions

Combinatorics Difficulty 5.7 AIME, harder Prove it Saudi Arabia

How many ways are there to insert plus signs ++ between the digits of number 111111…111111111 \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 3∣S3|S, 10∣S10|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
S≡1+1+1+⋯+1≡0(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,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.