Maths Olympiad Prep

Library / HMMT February /832 of 1302

HMMT February

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=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 \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. Fractions can be typed as 3/2, and spacing doesn't matter.

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))=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=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,pn, p, qq. 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} 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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.