Maths Olympiad Prep

Library / /1345 of 1394

Algebra Difficulty 6.1 National Olympiad Prove it United States

Problem:
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 \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).

Solution

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))=ni n_{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,p,qn, p, q. Similarly,
115=j=1n20j22i=1j=1n20j23i 115=\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=1n20j23i. A=\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}

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 reproduced verbatim; metadata (topic, difficulty) added by this project.