Maths Olympiad Prep

Library / /15 of 37

Algebra Difficulty 4.7 AIME Find the answer Italy

The base-2 representation of a number aa is 11100001001110101011101000011110000100111010101110100001. What is the seventh digit from the left of the representation of aa in base 8?

Pick one

Solution

The answer is (D). Let the base-2 expansion of a generic integer aa be
+28a8+27a7+26a6+25a5+24a4+23a3+22a2+21a1+a0 \ldots + 2^{8} a_{8} + 2^{7} a_{7} + 2^{6} a_{6} + 2^{5} a_{5} + 2^{4} a_{4} + 2^{3} a_{3} + 2^{2} a_{2} + 2^{1} a_{1} + a_{0}
then, if we group the terms three by three starting from the right, collecting a suitable power of 8, we obtain
+82(4a8+2a7+a6)+8(4a5+2a4+a3)+(4a2+2a1+a0). \ldots + 8^{2} (4 a_{8} + 2 a_{7} + a_{6}) + 8 (4 a_{5} + 2 a_{4} + a_{3}) + (4 a_{2} + 2 a_{1} + a_{0}) .
Since the terms in parentheses are always between 0 and 7, what we obtained is the expression in base 8 of the number aa. Observing how the digits are grouped, it is easy to conclude that, denoting by bkb_{k} the digits of the expansion in base 8 of the number, we have
bk=4a3k+2+2a3k+1+a3k. b_{k} = 4 a_{3k+2} + 2 a_{3k+1} + a_{3k} .
For the number under examination, operatively, it suffices to group the digits in groups of three starting from the last one on the right, and read (in base 2) the seventh group of digits starting from the left (note that the first group is made up of the single digit 1):
1110000100111010101110100001. 1|110|000|100|111|010|101|110|100|001 .
The seventh digit is thus 1012=5101_{2} = 5.

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 translated into English from it; metadata (topic, difficulty) added by this project.