Maths Olympiad Prep

Library / /13 of 348

Number theory Difficulty 4.4 AIME Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

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 11. Sums and differences of multiples of 11 must also be multiples of 11, 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 0 or 11 (no larger multiple is achievable). There are 8 choices for such (a,c)(a, c) and 9 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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.