Maths Olympiad Prep

Library / /693 of 860

Number theory Difficulty 5.4 AIME, harder Find the answer

For any positive integers aa and bb with b>1b>1, let sb(a)s_{b}(a) be the sum of the digits of aa when it is written in base bb. Suppose nn is a positive integer such that i=1log23ns20(n23i)=103 and i=1log20ns23(n20i)=115\sum_{i=1}^{\left\lfloor\log _{23} n\right\rfloor} s_{20}\left(\left\lfloor\frac{n}{23^{i}}\right\rfloor\right)=103 \quad \text { and } \sum_{i=1}^{\left\lfloor\log _{20} n\right\rfloor} s_{23}\left(\left\lfloor\frac{n}{20^{i}}\right\rfloor\right)=115 Compute s20(n)s23(n)s_{20}(n)-s_{23}(n).

A number or a short expression. Spacing and $ signs are ignored.

Solution

First we will prove that sa(n)=n(a1)(i=1nai)s_{a}(n)=n-(a-1)\left(\sum_{i=1}^{\infty}\left\lfloor\frac{n}{a^{i}}\right\rfloor\right) If n=(nknk1n1n0)an=\left(n_{k} n_{k-1} \cdots n_{1} n_{0}\right)_{a}, then the digit nin_{i} contributes nin_{i} to the left side of the sum, while it contributes ni(ai(a1)(ai1+ai2++a1+a0))=nin_{i}\left(a^{i}-(a-1)\left(a^{i-1}+a^{i-2}+\cdots+a^{1}+a^{0}\right)\right)=n_{i} to the right side, so the two are equal as claimed. Now we have 103=i=1s20(n23i)=i=1(n23i19(j=1n/23i20j))=i=1n23i19i=1j=1n20j23i\begin{aligned} 103 & =\sum_{i=1}^{\infty} s_{20}\left(\left\lfloor\frac{n}{23^{i}}\right\rfloor\right) \\ & =\sum_{i=1}^{\infty}\left(\left\lfloor\frac{n}{23^{i}}\right\rfloor-19\left(\sum_{j=1}^{\infty}\left\lfloor\frac{\left\lfloor n / 23^{i}\right\rfloor}{20^{j}}\right\rfloor\right)\right) \\ & =\sum_{i=1}^{\infty}\left\lfloor\frac{n}{23^{i}}\right\rfloor-19 \sum_{i=1}^{\infty} \sum_{j=1}^{\infty}\left\lfloor\frac{n}{20^{j} \cdot 23^{i}}\right\rfloor \end{aligned} where we have used the fact that n/pq=npq\left\lfloor\frac{\lfloor n / p\rfloor}{q}\right\rfloor=\left\lfloor\frac{n}{p q}\right\rfloor for positive integers n,pn, p, qq. Similarly, 115=j=1n20j22i=1j=1n20j23i115=\sum_{j=1}^{\infty}\left\lfloor\frac{n}{20^{j}}\right\rfloor-22 \sum_{i=1}^{\infty} \sum_{j=1}^{\infty}\left\lfloor\frac{n}{20^{j} \cdot 23^{i}}\right\rfloor Let A=j=1n20j,B=i=1n23i, and X=i=1j=1n20j23iA=\sum_{j=1}^{\infty}\left\lfloor\frac{n}{20^{j}}\right\rfloor, \quad B=\sum_{i=1}^{\infty}\left\lfloor\frac{n}{23^{i}}\right\rfloor, \quad \text { and } \quad X=\sum_{i=1}^{\infty} \sum_{j=1}^{\infty}\left\lfloor\frac{n}{20^{j} \cdot 23^{i}}\right\rfloor Then we have 103=B19X103=B-19 X and 115=A22X115=A-22 X. Thus, we have s20(n)s23(n)=(n19j=1n20j)(n22i=1n23i)=22B19A=22(103+19X)19(115+22X)=2210319115=81\begin{aligned} s_{20}(n)-s_{23}(n) & =\left(n-19 \sum_{j=1}^{\infty}\left\lfloor\frac{n}{20^{j}}\right\rfloor\right)-\left(n-22 \sum_{i=1}^{\infty}\left\lfloor\frac{n}{23^{i}}\right\rfloor\right) \\ & =22 B-19 A \\ & =22(103+19 X)-19(115+22 X) \\ & =22 \cdot 103-19 \cdot 115=81 \end{aligned} Remark. The value n=22399976n=22399976 satisfies both equations, so a valid solution to the system exists. It seems infeasible to compute this solution by hand.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.