Maths Olympiad Prep

Library / /31 of 75

Algebra Difficulty 4.7 AIME Find the answer Italy

Problem:

How many positive integers nn have the property that their representation in base 2 coincides with the representation in base 3 of 2n2 n?

Pick one

Solution

Solution:

The answer is (C). Let nn be a positive integer. Let ak,ak1,,a0a_{k}, a_{k-1}, \ldots, a_{0} be the k+1k+1 digits, from left to right, of the representation of nn in base 2. Each of the aia_{i} will take a value between 0 and 1, and we may assume without loss of generality that ak=1a_{k}=1. Therefore n=2kak+2k1ak1++a0n=2^{k} a_{k}+2^{k-1} a_{k-1}+\ldots+a_{0}. In particular the estimate n<2k+1n<2^{k+1} holds. Suppose now that nn satisfies the hypotheses of the problem, and hence that ak,ak1,,a0a_{k}, a_{k-1}, \ldots, a_{0} are also the digits of the representation in base 3 of 2n2 n. Then we have 2n=3kak+3k1ak1++a02 n=3^{k} a_{k}+3^{k-1} a_{k-1}+\ldots+a_{0} and the estimate 2n3k2 n \geq 3^{k} holds. Now if k4k \geq 4 we have 3k>2k+23^{k}>2^{k+2} and hence, putting together the estimates obtained above, we get 2n3k>2k+2>2n2 n \geq 3^{k}>2^{k+2}>2 n, which is not possible. Hence k3k \leq 3. Now by hypothesis
27a3+9a2+3a1+a0=2(8a3+4a2+2a1+a0) 27 a_{3}+9 a_{2}+3 a_{1}+a_{0}=2\left(8 a_{3}+4 a_{2}+2 a_{1}+a_{0}\right)
that is
11a3+a2a1a0=0 11 a_{3}+a_{2}-a_{1}-a_{0}=0
from which one immediately deduces that a3=0a_{3}=0 (otherwise the expression on the left is greater than 8; the aia_{i} take the value 0 or 1). Now a2a1a0=0a_{2}-a_{1}-a_{0}=0 has exactly two solutions (with at least one digit different from 0), namely (a2,a1,a0)=(1,0,1)(a_{2}, a_{1}, a_{0})=(1,0,1) and (a2,a1,a0)=(1,1,0)(a_{2}, a_{1}, a_{0})=(1,1,0) which correspond respectively to the two numbers n=6n=6 and n=5n=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.