Maths Olympiad Prep

Library / HMMT February /1258 of 1302

HMMT February

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=1⌊log⁡23n⌋s20(⌊n23i⌋)=103 and ∑i=1⌊log⁡20n⌋s23(⌊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−(a−1)(∑i=1∞⌊nai⌋). s_{a}(n)=n-(a-1)\left(\sum_{i=1}^{\infty}\left\lfloor\frac{n}{a^{i}}\right\rfloor\right) .
If n=(nknk−1⋯n1n0)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−(a−1)(ai−1+ai−2+⋯+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=1∞s20(⌊n23i⌋)=∑i=1∞(⌊n23i⌋−19(∑j=1∞⌊⌊n/23i⌋20j⌋))=∑i=1∞⌊n23i⌋−19∑i=1∞∑j=1∞⌊n20j⋅23i⌋ \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/p⌋q⌋=⌊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=1∞⌊n20j⌋−22∑i=1∞∑j=1∞⌊n20j⋅23i⌋ 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=1∞⌊n20j⌋,B=∑i=1∞⌊n23i⌋, and X=∑i=1∞∑j=1∞⌊n20j⋅23i⌋. 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=B−19X103=B-19 X and 115=A−22X115=A-22 X.
Thus, we have
s20(n)−s23(n)=(n−19∑j=1∞⌊n20j⌋)−(n−22∑i=1∞⌊n23i⌋)=22B−19A=22(103+19X)−19(115+22X)=22⋅103−19⋅115=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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.