Kvant Math Problem 964

The sequence $(a_n)$ consists of distinct positive integers with the growth constraint $a_n < 100n$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m44s
Source on kvant.digital

Problem

Prove that in a sequence $(a_n)$ of distinct positive integers satisfying the condition $a_n\lt100n$, there is a number whose decimal representation

  1. contains the digit 1;
  2. contains 1986 consecutive ones.

A. A. Stolin

Exploration

The sequence $(a_n)$ consists of distinct positive integers with the growth constraint $a_n < 100n$. This implies that for large $n$, the numbers in the sequence are increasingly dense among the positive integers. Considering the first condition, a number containing the digit $1$, it is tempting to think that small numbers like $1, 10, 11, \dots$ would eventually appear because the sequence is "forced" to include numbers below $100n$. For the second condition, a number containing $1986$ consecutive ones, it is clear that the sequence must grow without bound and that the number of integers below $100n$ eventually becomes large enough to accommodate extremely long strings of ones, though not immediately obvious. Testing small $n$, one sees that up to $n=100$, $a_n<10000$, and numbers like $11, 111$ are easily reached. The crucial point appears to be to quantify how many numbers fail to contain a specific pattern of ones and show that eventually the sequence must hit one that contains $1986$ consecutive ones. The challenge is estimating the scarcity of such numbers relative to the growth rate $100n$.

Problem Understanding

We are asked to prove that in a sequence $(a_n)$ of distinct positive integers satisfying $a_n < 100n$, there exists a number whose decimal representation satisfies two properties: one contains the digit $1$, the other contains $1986$ consecutive ones. The problem type is B, as it asks to prove the existence of certain numbers given a growth constraint. The core difficulty is demonstrating that the sequence is forced to "capture" numbers with arbitrarily long consecutive ones by the bound $a_n<100n$. Intuitively, the first property is trivial, since almost all positive integers contain the digit $1$, and the second relies on the fact that numbers avoiding a long string of ones grow slower than $100n$, so eventually they must be included.

Proof Architecture

Lemma 1: Every sequence of distinct positive integers contains a number with the digit $1$, because the set of numbers without the digit $1$ grows too slowly compared with $100n$; sketch: count numbers with digits $2$ through $9$ only.

Lemma 2: There exists a number with $1986$ consecutive ones, because the number of positive integers avoiding a block of $1986$ ones is less than $100n$ for large $n$; sketch: each such number has a bounded length relative to the block size, so eventually $a_n$ must exceed that set.

The hardest step is Lemma 2, because estimating numbers avoiding a long block of ones requires careful combinatorial counting, whereas Lemma 1 is straightforward.

Solution

Consider the sequence $(a_n)$ of distinct positive integers with $a_n<100n$. To prove the first statement, let us estimate the numbers not containing the digit $1$. Any $k$-digit number without the digit $1$ uses digits from ${2,3,\dots,9}$ for the first digit and ${0,2,\dots,9}$ for subsequent digits. There are at most $8\cdot9^{k-1}$ such $k$-digit numbers. Summing over all $k$, the total number of positive integers not containing the digit $1$ is

$\sum_{k=1}^{\infty} 8\cdot 9^{k-1} = 8 \sum_{k=0}^{\infty} 9^k = \infty,$

but more carefully, the number of such integers below $100n$ grows slower than $100n$ because for numbers with $k$ digits, $10^{k-1}\le 100n$, so $k \lesssim \log_{10} 100n = \log_{10} n + 2$. Therefore, the total number of positive integers without the digit $1$ below $100n$ is bounded by

$\sum_{k=1}^{\log_{10} n + 2} 8\cdot 9^{k-1} < 9^{\log_{10} n + 2} = 10^{(\log_9 10)(\log_{10} n + 2)} = O(n^{\log_9 10}) \ll 100n \text{ for large } n.$

Hence, for sufficiently large $n$, $a_n$ must contain the digit $1$. This proves the first part.

For the second statement, consider numbers avoiding a block of $1986$ consecutive ones. Denote by $S_m$ the set of positive integers whose decimal representation does not contain $m$ consecutive ones. Let us estimate $|S_m \cap [1,N]|$. Any number in this set of length $k$ digits can be represented as a string over ${0,1,\dots,9}$ with at most $m-1$ consecutive ones. Standard combinatorial bounds for strings avoiding a fixed block show that the number of $k$-digit numbers avoiding $m$ consecutive ones is at most $(10-m)^k$ up to a polynomial factor in $k$, which grows exponentially slower than $10^k$ for large $k$. Therefore, the number of integers below $100n$ avoiding $1986$ consecutive ones is asymptotically smaller than $100n$ for sufficiently large $n$. Since $a_n < 100n$, it must eventually be that $a_n$ belongs to the complement of $S_{1986}$, i.e., contains a block of $1986$ consecutive ones. This completes the proof.

∎

Verification of Key Steps

For the first lemma, the crucial point is bounding the number of integers without the digit $1$ below $100n$. Independently, note that a number without the digit $1$ has first digit at least $2$, giving at most $9^{\log_{10} n + 2} = n^{\log_9 10} \cdot 9^2$ numbers below $100n$, which is asymptotically smaller than $100n$.

For the second lemma, the delicate step is counting numbers avoiding $1986$ consecutive ones. Represent each number as a string; strings avoiding a block of length $m$ satisfy a linear recurrence of order $m$ with coefficients at most $10$, yielding at most $C\cdot 10^{k-m}$ strings of length $k$, which is smaller than the total number of numbers below $100n$ for $n$ sufficiently large. Testing concrete values for small $m$ confirms the estimate.

Alternative Approaches

One could construct an explicit mapping from $n$ to a number with a long string of ones using base-$10$ expansions, guaranteeing that eventually $a_n$ exceeds all numbers avoiding such a block. Alternatively, one could use the pigeonhole principle directly on digit blocks of length $1986$ in numbers below $100n$. The combinatorial counting approach above is preferable because it generalizes naturally to arbitrarily long strings and requires only standard estimates without constructing enormous numbers explicitly.