Maths Olympiad Prep

Library / /17 of 36

, 2023

Number theory Difficulty 8.5 Shortlist Prove it Baltic Way

For a positive integer mm, let S(m)S(m) denote the positive integer whose decimal representation is equal to the octal representation of mm. For example, S(64)=100S(64) = 100, S(100)=144S(100) = 144, S(2023)=3747S(2023) = 3747. Two positive integers x,yx, y satisfy the relation
S(x)+S(1)S(x+1)=S(y)+S(2023)S(y+2023)<810. \frac{S(x) + S(1)}{S(x + 1)} = \frac{S(y) + S(2023)}{S(y + 2023)} < \frac{8}{10}.
What is the smallest possible value of yy if x<100x < 100?

Solution

The answer is 2137.

First of all, let's observe that x=63x = 63, y=2137y = 2137 satisfies the given relation. In fact,
S(63)+S(1)S(64)=77+1100=78100<810andS(2137)+S(2023)S(4160)=4131+374710100=787810100=78100<810. \frac{S(63) + S(1)}{S(64)} = \frac{77 + 1}{100} = \frac{78}{100} < \frac{8}{10} \quad \text{and} \\ \frac{S(2137) + S(2023)}{S(4160)} = \frac{4131 + 3747}{10100} = \frac{7878}{10100} = \frac{78}{100} < \frac{8}{10}.

Now let's assume that the octal representation of xx ends with exactly kk digits “7” (maybe k=0k = 0). In other words, x=a8k+8k1x = a \cdot 8^k + 8^k - 1 where aa is a nonnegative integer satisfying amod8<7a \bmod 8 < 7. In particular, we know that S(a+1)=S(a)+1S(a + 1) = S(a) + 1 because there is no carry in addition in the octal system, since amod8<7a \bmod 8 < 7. Therefore,
S(x)=S(a8k+8k1)=S(a)10k+79(10k1)andS(x+1)=S((a+1)8k)=S(a+1)10k=(S(a)+1)10k. S(x) = S(a \cdot 8^k + 8^k - 1) = S(a) \cdot 10^k + \frac{7}{9}(10^k - 1) \quad \text{and} \\ S(x + 1) = S((a + 1) \cdot 8^k) = S(a + 1) \cdot 10^k = (S(a) + 1) \cdot 10^k.

Let's observe that k=0k = 0 would imply that S(x)+S(1)=S(x+1)S(x) + S(1) = S(x + 1) and therefore k0k \neq 0. k3k \ge 3 would imply x831>100x \ge 8^3 - 1 > 100 and therefore k=1k = 1 or k=2k = 2. If k=2k = 2 then a=0a = 0 (because 82+821>1008^2 + 8^2 - 1 > 100) and therefore x=821=63x = 8^2 - 1 = 63 and S(x)+S(1)S(x+1)=78100\frac{S(x)+S(1)}{S(x+1)} = \frac{78}{100}. k=1k = 1 is also impossible because:
10S(a)+810S(a)+10<810    10S(a)+8<8S(a)+8    S(a)<0. \frac{10S(a) + 8}{10S(a) + 10} < \frac{8}{10} \implies 10S(a) + 8 < 8S(a) + 8 \implies S(a) < 0.

Now let's assume that we can find a solution with y<2137=41318y < 2137 = 4131_8. Then yy has at most 4 digits in its octal representation. Let did_i for i=0,1,2,3i = 0, 1, 2, 3 be equal to 1 if there is a carry at the ii-th position in addition of yy and 2023=374782023 = 3747_8 in octal system. It is easy to conclude that
S(y+2023)S(y)S(2023)=i=03(8)10idi+i=0310i+1di=2i=0310idi. S(y+2023)-S(y)-S(2023) = \sum_{i=0}^{3} (-8) \cdot 10^i \cdot d_i + \sum_{i=0}^{3} 10^{i+1} \cdot d_i = 2 \sum_{i=0}^{3} 10^i \cdot d_i.
We have the implication:
S(y)+S(2023)S(y+2023)=78100    S(y)+S(2023)S(y+2023)S(y)S(2023)=7822    S(y)+S(2023)=7811i=0310idi. \begin{aligned} \frac{S(y) + S(2023)}{S(y + 2023)} &= \frac{78}{100} & \implies & \frac{S(y) + S(2023)}{S(y + 2023) - S(y) - S(2023)} &= \frac{78}{22} \\ & \implies & S(y) + S(2023) &= \frac{78}{11} \sum_{i=0}^{3} 10^i \cdot d_i. \end{aligned}
We know that d3=1d_3 = 1 because otherwise we would have:
S(y)+S(2023)7811111<3747=S(2023). S(y) + S(2023) \le \frac{78}{11} \cdot 111 < 3747 = S(2023).
Because 78 is coprime with 11, we need to have the divisibility 11i=0310idi11|\sum_{i=0}^{3} 10^i \cdot d_i. Since d3=1d_3 = 1, there are only three possible cases: i=0310idi=1001,1100,1111\sum_{i=0}^{3} 10^i \cdot d_i = 1001, 1100, 1111. They correspond to S(y)+S(2023)=7098,7800,7878S(y) + S(2023) = 7098, 7800, 7878, so S(y)=3351,4053,4131S(y) = 3351, 4053, 4131. The first two cases are impossible because they assume d1=0d_1 = 0 but 5+4>75 + 4 > 7, so there has to be a carry at the first position.

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.