Maths Olympiad Prep

Library / /475 of 740

, 2013

Algebra Difficulty 5.1 AIME, harder Prove it United States

Problem:

Let b(n)b(n) be the number of digits in the base 4-4 representation of nn. Evaluate i=12013b(i)\sum_{i=1}^{2013} b(i).

Solution

Solution:

We have the following:

- b(n)=1b(n) = 1 for nn between 11 and 33.
- b(n)=3b(n) = 3 for nn between 4234=44^{2} - 3 \cdot 4 = 4 and 342+3=513 \cdot 4^{2} + 3 = 51. (Since a42b4+ca \cdot 4^{2} - b \cdot 4 + c takes on 3443 \cdot 4 \cdot 4 distinct values over 1a31 \leq a \leq 3, 0b30 \leq b \leq 3, 0c30 \leq c \leq 3, with minimum 44 and maximum 5151.)
- b(n)=5b(n) = 5 for nn between 4434334=524^{4} - 3 \cdot 4^{3} - 3 \cdot 4 = 52 and 344+342+3=8193 \cdot 4^{4} + 3 \cdot 4^{2} + 3 = 819.
- b(n)=7b(n) = 7 for nn between 46345343341=8204^{6} - 3 \cdot 4^{5} - 3 \cdot 4^{3} - 3 \cdot 4^{1} = 820 and 346+344+342+3>20133 \cdot 4^{6} + 3 \cdot 4^{4} + 3 \cdot 4^{2} + 3 > 2013.

Thus

i=12013b(i)=7×20132×(819+51+3)=140912×873=140911746=12345. \sum_{i=1}^{2013} b(i) = 7 \times 2013 - 2 \times (819 + 51 + 3) = 14091 - 2 \times 873 = 14091 - 1746 = 12345.

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.