Maths Olympiad Prep

Library / /27 of 39

Number theory Difficulty 6.2 National olympiad Prove it Ukraine

Decimal representation of a number aa is written one or several times on the blackboard. As a result, the binary representation of the same number aa is obtained. Find all possible values of aa.

Solution

Let decimal representation of aa consist of exactly kk digits, and binary representation consists of exactly ll times more digits, i.e. of klkl digits. Since all digits of aa equal to either 00 or 11, then the number aa should belong to, from one side, the interval [10k1,16(10k1)][10^{k-1}, \frac{1}{6}(10^k - 1)], and from the other side, to the interval [2k/l1,2k/l1][2^{k/l-1}, 2^{k/l} - 1]. Hence we come to two inequalities: 10k12k/l110^{k-1} \le 2^{k/l} - 1 and 16(10k1)2k/l1\frac{1}{6}(10^k - 1) \ge 2^{k/l-1}. After transformation, we get 23<(1027)k<10\frac{2}{3} < (\frac{10}{27})^k < 10. This inequality, obviously, is wrong for l4l \ge 4.

For l=1l=1 we have the only possible value k=1k=1 and the first answer - number 11.

If l=2l=2, then k=2k=2. From all two-digit numbers, having only 0,10,1 as digits, only 1010 suits - the second answer.

For the last case, l=3l=3, possible values are k{7,8,9,10}k \in \{7,8,9,10\}. Let's examine them.

For k=10k=10 we have 109>229+22810^9 > 2^{29} + 2^{28}. That is, if aa is a ten-digit number such that written thrice it represents binary form of itself, then it has to have 11 in the second-highest decimal position, i.e. a>11108>230a > 11 \cdot 10^8 > 2^{30} - a contradiction (binary representation of aa should be a 3030-digit number).

For all other values of kk we see that a=(22k+2k+1)a = (2^{2k} + 2^k + 1). For k=9k=9, 22k+2k+1=2626572^{2k} + 2^k + 1 = 262657. Numbers 100,101,...,10810^0, 10^1, ..., 10^8 give remainders 1,10,...,100000,212029,190341, 10, ..., 100000, 212029, 19034 and 190340190340 under the division by 262657262657, respectively. Since aa is a sum of several powers of 1010 with the highest 10810^8, we have to choose from 1,10,...,100000,212029,19034,1903401, 10, ..., 100000, 212029, 19034, 190340 such that they sum up either to 262657190340262657-190340, or to 22626571903402 \cdot 262657-190340. By examination of options we see that it is impossible to get such numbers. Similarly, we can check all other cases. Let's see (for example) the case k=8k=8. 210+28+1=657932^{10} + 2^8 + 1 = 65793. The remainders of 100,101,...,10710^0, 10^1, ..., 10^7 under the division by 6579365793 equal 1,10,...,10000,234207,131051, 10, ..., 10000, 234207, 13105 and 536-536. We have to select a combination of powers, summing up to 536536 - others impossible. By checking two last digits (00,01,10,07,0500, 01, 10, 07, 05) we see that it is impossible to get the required two last digits 3636.

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.