Kvant Math Problem 640

Let the decimal expansion of $x_k$ be

kvantmathematicsolympiad

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

Problem

The number $x\in[0;1]$ is written as an infinite decimal expansion. By rearranging its first 5 digits after the decimal point in an arbitrary order, we obtain a new infinite decimal expansion corresponding to some number $x_1$. By rearranging the 2nd through 6th digits after the decimal point in the decimal expansion of $x_1$, we obtain the decimal expansion of the number $x_2$. In general, the decimal expansion of the number $x_{k+1}$ is obtained by rearranging the digits in the expansion of $x_k$ from the $(k+1)$-th through the $(k+5)$-th positions after the decimal point.

  1. Prove that no matter how the digits are rearranged at each step, the resulting sequence of numbers $x_k$ always has a limit. Denote this limit by $y$.
  2. Determine whether it is possible, by means of such a process, to obtain an irrational number $y$ from a rational number $x$.
  3. Construct a decimal fraction $x$ for which the described process always leads to irrational numbers $y$, regardless of the rearrangements of the five-digit blocks at each step.

N. Kartashov

All-Union Mathematical Olympiad (XIV, 1980, Grade 10)

Exploration

Let the decimal expansion of $x_k$ be

$$x_k=0.a^{(k)}_1a^{(k)}_2a^{(k)}_3\cdots .$$

At step $k\to k+1$ only the digits in positions $k+1,\dots,k+5$ are permuted. Every other position is untouched.

The first thing to examine is what happens to a fixed position $n$. Position $n$ can be affected only while it belongs to the moving five-digit window. The window at step $k$ is

$${k+1,k+2,k+3,k+4,k+5}.$$

The index $n$ belongs to this window exactly for

$$k=n-5,n-4,n-3,n-2,n-1.$$

After step $n-1$ the position $n$ never again enters any window. Hence its digit eventually becomes fixed. This strongly suggests that the limit exists digitwise.

Existence of a digitwise limit does not automatically imply convergence of the numbers because of the ambiguity of decimal expansions ending in infinitely many $9$'s. A safer route is to compare $x_k$ with the limiting decimal digit by digit. After step $k$, positions $1,\dots,k$ are already frozen forever. Thus $x_k$ and the eventual limit agree in their first $k$ digits after the decimal point, so their difference is at most $10^{-k}$. That gives convergence immediately.

For the second part, it is useful to understand the limit more explicitly. Let $S_n$ be the multiset of the first $n+4$ digits of the original number $x$. At time $n-1$ the digit occupying position $n$ comes from the block $n,\dots,n+4$ of the preceding stage. Tracing backwards, every digit that can reach position $n$ must originate among the first $n+4$ positions of the original expansion. Conversely, by repeatedly moving a chosen digit one place left whenever it lies inside the active window, any original digit among positions $1,\dots,n+4$ can be brought to position $n$. Thus the limiting digit $b_n$ belongs to the multiset $S_n$, and every element of $S_n$ can occur as $b_n$.

A rational decimal has eventually periodic digits. Then only finitely many different blocks $S_n$ occur. Any admissible limiting digit sequence $b_n$ satisfies $b_n\in S_n$, where the family $S_n$ is eventually periodic. Such sequences need not be periodic. Take, for example, a rational number whose tail alternates $0,1,0,1,\dots$. Then for large $n$ the set $S_n={0,1,0,1,0}$, hence $b_n$ may be chosen arbitrarily as $0$ or $1$ at each position. An arbitrary binary sequence can therefore be encoded in the limit. Choosing a nonperiodic binary sequence yields an irrational limit.

For the third part we want an $x$ such that every possible limit is irrational. We need a decimal whose admissible digit at position $n$ is forced to lie in a set depending on $n$, and whose structure prevents eventual periodicity.

A natural idea is to use only digits $0$ and $1$ and arrange them in very long blocks whose lengths grow. Let

$$x=0.,0^1,1^1,0^2,1^2,0^3,1^3,0^4,1^4\cdots .$$

The $m$-th zero-block and $m$-th one-block both have length $m$.

Consider $S_n$, the five-digit window of original positions $1,\dots,n+4$. If $n$ is at distance at least $4$ from every boundary between blocks, then the five digits ending at position $n+4$ lie entirely inside one constant block, so $S_n$ contains only $0$'s or only $1$'s. Hence the limiting digit $b_n$ is forced.

Only positions within distance $4$ of a block boundary allow any choice. There are at most $8$ such positions per boundary. Since the block lengths tend to infinity, arbitrarily long stretches of positions are forced to be all $0$ and arbitrarily long stretches are forced to be all $1$.

Any eventually periodic sequence has bounded run lengths. Our forced sequence has unbounded runs of $0$'s and $1$'s, and changing finitely many digits near each boundary cannot destroy that. Hence every possible limit is nonperiodic, therefore irrational.

The delicate point is proving rigorously that every digit among the first $n+4$ original positions can indeed be transported to position $n$.

Problem Understanding

We are given a decimal expansion of a number $x\in[0,1]$. At step $k$ we may permute arbitrarily the five digits occupying positions $k+1,\dots,k+5$ after the decimal point. Repeating this process produces numbers $x_k$.

We must prove that for every choice of permutations the sequence $(x_k)$ converges. Denote its limit by $y$.

Next, we must decide whether a rational starting number $x$ can lead, by a suitable choice of permutations, to an irrational limit $y$.

Finally, we must construct a decimal fraction $x$ for which every possible limit $y$ is irrational, regardless of the permutations chosen.

This is a Type D problem. We must establish existence of the limit, exhibit a rational $x$ together with a process producing an irrational limit, and construct an $x$ whose every possible limit is irrational.

The core difficulty is understanding which original digits can eventually occupy a given position in the limit.

Proof Architecture

For each position $n$, its digit is modified only during the five steps $n-5,\dots,n-1$; hence the digit at position $n$ eventually stabilizes.

After step $k$, the first $k$ digits after the decimal point are already stabilized forever; therefore $x_k$ and the limiting decimal agree in their first $k$ digits, giving $|x_k-y|\le10^{-k}$.

Let $S_n$ be the multiset of the first $n+4$ digits of the original expansion. Any digit appearing at position $n$ in the limit must come from $S_n$, because a digit can move left by at most one position during each step.

Every digit among the first $n+4$ original positions can be moved to position $n$ by repeatedly shifting it one position left whenever it lies in the active window.

Hence the $n$-th digit of the limit may be chosen arbitrarily among the digits occurring in $S_n$.

For the rational number with tail $010101\dots$, every large $S_n$ contains both $0$ and $1$, so any binary sequence can be realized as the tail of a limit.

Choosing a nonperiodic binary sequence produces an irrational limit.

For the number $0^1 1^1 0^2 1^2 0^3 1^3\cdots$, all positions farther than $4$ from every block boundary have a uniquely determined limiting digit.

These forced stretches contain arbitrarily long runs of $0$'s and arbitrarily long runs of $1$'s; therefore every possible limit has unbounded run lengths and cannot be eventually periodic.

The most delicate lemma is the converse reachability statement that every original digit among positions $1,\dots,n+4$ can be transported to position $n$.

Solution

Write

$$x_k=0.a^{(k)}_1a^{(k)}_2a^{(k)}_3\cdots .$$

For a fixed position $n$, the digit $a^{(k)}_n$ can be changed only when $n$ belongs to the active block

$${k+1,k+2,k+3,k+4,k+5}.$$

This happens exactly for

$$k=n-5,n-4,n-3,n-2,n-1.$$

After step $n-1$, the position $n$ never again belongs to any active block. Hence there exists a digit $b_n$ such that

$$a^{(k)}_n=b_n$$

for all sufficiently large $k$.

Let

$$y=0.b_1b_2b_3\cdots .$$

After step $k$, every position $1,\dots,k$ has already passed permanently out of all future active blocks. Consequently the first $k$ digits of $x_k$ coincide with those of $y$. Therefore

$$|x_k-y|\le 10^{-k}.$$

Hence $x_k\to y$. This proves the first statement.

Now fix $n$. Let $S_n$ denote the multiset of the first $n+4$ digits of the original expansion of $x$.

A digit originally at position $m$ can move left by at most one position during a single step. Since only the steps $m-5,m-4,\dots$ can affect it, after $t$ further steps it can have moved left by at most $t$ places. Thus a digit reaching position $n$ must satisfy

$$m\le n+4.$$

Hence the limiting digit $b_n$ must be one of the digits contained in $S_n$.

We prove the converse. Let a digit originally occupy position $m\le n+4$. During step $m-5$ it lies in the active block. By choosing the permutation appropriately, place it at the leftmost position of that block. Its position decreases by one. At the next step it again belongs to the active block, and we can again move it to the leftmost position. Repeating this procedure, the digit moves one place left at every step until it reaches position $n$. Since

$$m-n\le4,$$

at most four such moves are required. Thus every digit among the first $n+4$ original positions can be placed at position $n$ when that position becomes fixed.

Therefore:

$$b_n \text{ may be any digit occurring among the first } n+4 \text{ original positions.}$$

We turn to the second question. Consider the rational number

$$x=0.0101010101\cdots=\frac1{99}.$$

For every sufficiently large $n$, the first $n+4$ digits contain both $0$ and $1$. By the characterization just proved, the digit $b_n$ may be chosen arbitrarily as $0$ or $1$.

Choose a binary sequence which is not eventually periodic, for example

$$b_n= \begin{cases} 1,& n=m^2\text{ for some }m,\ 0,& \text{otherwise}. \end{cases}$$

For each $n$ we select the permutations so that the stabilized digit at position $n$ equals this prescribed value. The resulting limit

$$y=0.b_1b_2b_3\cdots$$

is not eventually periodic. A decimal expansion is rational if and only if it is eventually periodic. Hence $y$ is irrational.

Thus an irrational limit can indeed be obtained from a rational starting number.

For the third question, define

$$x= 0., 0^1,1^1,0^2,1^2,0^3,1^3,0^4,1^4\cdots ,$$

where $0^m$ means a block of $m$ consecutive zeros and $1^m$ a block of $m$ consecutive ones.

Let $B$ be the set of positions where one block ends and the next begins. If a position $n$ satisfies

$$|n-t|>4 \qquad\text{for every }t\in B,$$

then the five positions

$$n,n+1,n+2,n+3,n+4$$

lie entirely inside a single constant block of the original expansion. Hence all digits in $S_n$ are equal, either all $0$ or all $1$. The characterization above shows that $b_n$ is then uniquely determined and equals that common value.

Around each boundary there are at most eight positions with distance at most $4$ from the boundary. Only at those positions can any choice occur.

Since the block lengths are

$$1,1,2,2,3,3,\dots ,$$

they grow without bound. Consequently, for every integer $L$ there exists a zero-block of length exceeding $L+8$ and a one-block of length exceeding $L+8$. Inside such a block, after removing the at most four positions near each end, there remains a forced run of more than $L$ consecutive zeros or ones in every possible limit sequence $(b_n)$.

Hence every possible limit contains arbitrarily long runs of zeros and arbitrarily long runs of ones.

Assume that some limit $y$ were rational. Its decimal expansion would be eventually periodic with period $p$. In an eventually periodic sequence, every run of equal digits has length at most $p$ beyond the preperiod, because the pattern repeats every $p$ places. This contradicts the existence of arbitrarily long runs of zeros and ones.

Therefore every possible limit $y$ is irrational.

The required construction is

$$\boxed{ x= 0., 0^1,1^1,0^2,1^2,0^3,1^3,0^4,1^4\cdots }.$$

Verification of Key Steps

The first delicate step is the claim that position $n$ stabilizes. The active block at step $k$ is ${k+1,\dots,k+5}$. Solving

$$k+1\le n\le k+5$$

gives

$$n-5\le k\le n-1.$$

Exactly five steps can affect position $n$. No later step contains $n$, so stabilization is unconditional.

The second delicate step is the reachability lemma. Suppose a digit starts at position $m\le n+4$. During a step whose active block contains that digit, we may place it at the leftmost position of the block. Its index decreases by one. Repeating this operation whenever possible decreases the index successively

$$m,m-1,m-2,\dots,n.$$

Since $m-n\le4$, the digit reaches position $n$ before that position freezes. The argument would fail if the window length were smaller than $5$, because then positions farther than the window length minus one could not be transported.

The third delicate step is excluding rational limits in the final construction. Near each boundary at most four positions on either side are uncontrolled. A block of length $M$ therefore contributes a forced monochromatic run of length at least $M-8$. Since $M$ is unbounded, the limit has unbounded runs. Any eventually periodic sequence with period $p$ has run lengths bounded by $p$. The contradiction is exact.

Alternative Approaches

Instead of describing the set of possible digits at position $n$ via transport of individual digits, one may formulate the process as a finite-state flow. Each step only redistributes the contents of a five-position buffer. The stabilization of position $n$ then follows from the fact that the buffer moves strictly to the right. This gives a compact proof of convergence but obscures the characterization of possible limits.

For the third part, one may replace the block lengths $1,1,2,2,3,3,\dots$ by any sequence of alternating zero-blocks and one-blocks whose lengths tend to infinity. The essential property is that, away from a bounded neighborhood of each boundary, every digit is forced. The chosen construction is the simplest explicit example because the growth of block lengths is transparent and easy to verify.