Maths Olympiad Prep

Library / /59 of 740

Number theory Difficulty 4.5 AIME Prove it United States

Problem:
Compute the number of positive four-digit multiples of 1111 whose sum of digits (in base ten) is divisible by 1111.

Solution

Solution:
Let an arbitrary such number be abcd\overline{a b c d}. Then, we desire 11a+b+c+d11 \mid a+b+c+d and 11ab+cd11 \mid a-b+c-d, where the latter comes from the well-known divisibility trick for 1111. Sums and differences of multiples of 1111 must also be multiples of 1111, so this is equivalent to desiring 11a+c11 \mid a+c and 11b+d11 \mid b+d.

As a[1,9]a \in [1,9] and b,c,d[0,9]b, c, d \in [0,9], a+ca+c and b+db+d must be either 00 or 1111 (no larger multiple is achievable). There are 88 choices for such (a,c)(a, c) and 99 choices for such (b,d)(b, d), so the answer is 89=728 \cdot 9 = 72.

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.