Maths Olympiad Prep

Library / /1302 of 1394

, 2020

Number theory Difficulty 6.0 National Olympiad Prove it United States

Problem:
A positive integer NN is piquant if there exists a positive integer mm such that if nin_{i} denotes the number of digits in mim^{i} (in base 10), then n1+n2++n10=Nn_{1}+n_{2}+\cdots+n_{10}=N. Let pMp_{M} denote the fraction of the first MM positive integers that are piquant. Find limMpM\lim _{M \rightarrow \infty} p_{M}.

Solution

Solution:
For notation, let ni(m)n_{i}(m) denote the number of digits of mim^{i} and N(m)=n1(m)+n2(m)++n10(m)N(m)=n_{1}(m)+n_{2}(m)+\cdots+n_{10}(m). Observe that ni(10m)=ni(m)+in_{i}(10 m)=n_{i}(m)+i so N(10m)=N(m)+55N(10 m)=N(m)+55. We will determine, for kk \rightarrow \infty, how many of the integers from N(10k)N\left(10^{k}\right) to N(10k+1)1N\left(10^{k+1}\right)-1, inclusive, are piquant.

Increment mm by 1 from 10k10^{k} to 10k+110^{k+1}. The number of digits of mim^{i} increases by one if mi<10h(m+1)im^{i}<10^{h} \leq (m+1)^{i}, or m<10him+1m<10^{\frac{h}{i}} \leq m+1 for some integer hh. This means that, as we increment mm by 1, the sum n1+n2++n10n_{1}+n_{2}+\cdots+n_{10} increases when mm "jumps over" 10hi10^{\frac{h}{i}} for i10i \leq 10. Furthermore, when mm is big enough, all "jumps" are distinguishable, i.e. there does not exist two h1i1h2i2\frac{h_{1}}{i_{1}} \neq \frac{h_{2}}{i_{2}} such that m<10h1/i1<10h2/i2m+1m<10^{h_{1} / i_{1}}<10^{h_{2} / i_{2}} \leq m+1.

Thus, for large kk, the number of times n1(m)+n2(m)++n10(m)n_{1}(m)+n_{2}(m)+\cdots+n_{10}(m) increases as mm increments by 1 from 10k10^{k} to 10k+110^{k+1} is the number of different 10hi10^{\frac{h}{i}} in the range (10k,10k+1]\left(10^{k}, 10^{k+1}\right.]. If we take the fractional part of the exponent, this is equivalent to the number of distinct fractions 0<ji10<\frac{j}{i} \leq 1 where 1i101 \leq i \leq 10. The number of such fractions with denominator ii is φ(i)\varphi(i), so the total number of such fractions is φ(1)+φ(2)++φ(10)=32\varphi(1)+\varphi(2)+\cdots+\varphi(10)=32.

We have shown that for sufficiently large k,N(10k+1)N(10k)=55k, N\left(10^{k+1}\right)-N\left(10^{k}\right)=55 and exactly 32 integers in the range [N(10k),N(10k+1))\left[N\left(10^{k}\right), N\left(10^{k+1}\right)\right) are piquant. This implies that limMpM=3255\lim _{M \rightarrow \infty} p_{M}=\frac{32}{55}.

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.