Maths Olympiad Prep

Library / HMMT November /44 of 672

HMMT November

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 11∣a+b+c+d11 \mid a+b+c+d and 11∣a−b+c−d11 \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 11∣a+c11 \mid a+c and 11∣b+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 8⋅9=728 \cdot 9 = 72.

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.