Maths Olympiad Prep

Library / /21 of 40

Number theory Difficulty 6.1 National olympiad Prove it China

A non-negative number mm is called a six match number. If mm and the sum of its digits are both multiples of 6, find the number of the six match numbers less than 2012.

Solution

Let n=d1d2d3d4=1000d1+100d2+10d3+d4n = \overline{d_1d_2d_3d_4} = 1000d_1 + 100d_2 + 10d_3 + d_4, d1,d2,d3,d4[0,1,2,,9]d_1, d_2, d_3, d_4 \in [0, 1, 2, \dots, 9], and S(n)=d1+d2+d3+d4S(n) = d_1 + d_2 + d_3 + d_4.
Match the non-negative multiples of 6 less than 2000 into 167 pairs (x,y)(x, y), x+y=1998x + y = 1998, such that
(0,1998),(6,1992),(12,1986),,(996,1002).(0, 1998), (6, 1992), (12, 1986), \dots, (996, 1002).
For each pair (x,y)(x, y), let x=a1a2a3a4x = \overline{a_1a_2a_3a_4}, y=b1b2b3b4y = \overline{b_1b_2b_3b_4}, then
1000(a1+b1)+100(a2+b2)+10(a3+b3)+(a4+b4)=x+y=1998. 1000(a_1 + b_1) + 100(a_2 + b_2) + 10(a_3 + b_3) + (a_4 + b_4) = x + y = 1998.
Since x,yx, y are even, a4,b48a_4, b_4 \le 8. So a4+b416<18a_4 + b_4 \le 16 < 18. Thus, a4+b4=8a_4 + b_4 = 8. Since a3+b318<19a_3 + b_3 \le 18 < 19, a3+b3=9a_3 + b_3 = 9.
Similarly, we can obtain a2+b2=9a_2 + b_2 = 9 and a1+b1=1a_1 + b_1 = 1. Thus,
S(x)+S(y)=(a1+b1)+(a2+b2)+(a3+b3)+(a4+b4)=1+9+9+8=27. \begin{aligned} S(x) + S(y) &= (a_1 + b_1) + (a_2 + b_2) + (a_3 + b_3) + (a_4 + b_4) \\ &= 1 + 9 + 9 + 8 = 27. \end{aligned}
Consequently, there is only one of S(x)S(x) and S(y)S(y) that is the multiple of 6. (This is because that xx, yy are all multiples of 3, so are S(x)S(x) and S(y)S(y).) That is, there is only one of xx and yy which is a six match number.
Therefore, there are 167 six match numbers less than 2000, and there is just one six match number between 2000 and 2011.
Therefore, the answer is 167+1=168167 + 1 = 168.

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.