Maths Olympiad Prep

Library / /10 of 11

Algebra Difficulty 6.4 National olympiad Prove it Estonia

Positive integer bb is obtained by reordering the digits in a positive integer aa. Which of the following claims are definitely true?

a) The sums of the digits of numbers 2a2a and 2b2b are equal.
b) The sums of the digits of numbers 3a3a and 3b3b are equal.
c) The sums of the digits of numbers 5a5a and 5b5b are equal.

Solution

Call digits 0,1,2,3,40, 1, 2, 3, 4 small and digits 5,6,7,8,95, 6, 7, 8, 9 large. Denote the digits of kk-digit number nn from right to left by (n)0,(n)1,,(n)k1(n)_0, (n)_1, \dots, (n)_{k-1}. Denote by Σ(n)\Sigma(n) the sum of all digits of nn and by l(n)l(n) the number of large digits of nn.

a) If (a)i(a)_i is small then (2a)i=2(a)i(2a)_i = 2(a)_i or (2a)i=2(a)i+1(2a)_i = 2(a)_i + 1 depending on whether (a)i1(a)_{i-1} is small or large. Similarly if (a)i(a)_i is large then (2a)i=2(a)i10(2a)_i = 2(a)_i - 10 or (2a)i=2(a)i9(2a)_i = 2(a)_i - 9 depending on whether (a)i1(a)_{i-1} is small or large. In other words, when multiplying by 22, each large digit necessitates decreasing of the digit at its place by 1010 and increasing of the preceding digit by 11 in comparison with a small digit. Hence, for every natural number nn, Σ(2n)=2Σ(n)9l(n)\Sigma(2n) = 2\Sigma(n) - 9l(n). As Σ(a)=Σ(b)\Sigma(a) = \Sigma(b) and l(a)=l(b)l(a) = l(b), we have Σ(2a)=Σ(2b)\Sigma(2a) = \Sigma(2b).

b) If a=34a = 34 and b=43b = 43 then Σ(3a)=1+0+2=3\Sigma(3a) = 1 + 0 + 2 = 3 but Σ(3b)=1+2+9=12\Sigma(3b) = 1 + 2 + 9 = 12.

c) Obviously Σ(10a)=Σ(10b)\Sigma(10a) = \Sigma(10b). By part a), on the other hand, Σ(10n)=Σ(25n)=2Σ(5n)9l(5n)\Sigma(10n) = \Sigma(2 \cdot 5n) = 2\Sigma(5n) - 9l(5n), holding for every natural number nn. Hence 2Σ(5a)9l(5a)=2Σ(5b)9l(5b)2\Sigma(5a) - 9l(5a) = 2\Sigma(5b) - 9l(5b). The digit (5n)i(5n)_i is large if and only if the digit (n)i(n)_i is odd, because a carry during multiplying by 55 can be at most 44. Thus l(5n)l(5n) is the number of odd digits of nn, implying l(5a)=l(5b)l(5a) = l(5b). Consequently, Σ(5a)=Σ(5b)\Sigma(5a) = \Sigma(5b).

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.