$5.$Let x be a real number with $0<x<1$ and let $0.c_1c_2c_3...$ be the decimal expansion of x.Denote by $B(x)$ the set of all subsequences of $c_1c_2c_3$ that consist of 6 consecutive digits. For instance , $B(\frac{1}{22})={045454,454545,545454}$ Find the minimum number of elements of $B(x)$ as $x$ varies among all irrational numbers with $0<x<1$
Problem
Source: ITAMO 2018
Tags: combinatorics
10.06.2021 18:04
We claim the answer is $7$. Let $a = 0.100000100000010000000...$ where there are $5, 6, 7, \ldots$ zeroes separating consecutive ones. If $a$ is rational, then it would be periodic after a certain $k^{th}$ digit. Let the repeated part contain $l$ digits. Since there are an infinite number of sequences of more than $2l$ consecutive zeroes, at least one of them is after the $k^{th}$ digit. Thus, the repeated part must contain $l$ zeroes, but there are an infinite number of ones, contradiction. Thus, $a$ is irrational. Note that $B(a) = \{000000, 000001, 000010, 000100, 001000, 010000, 100000\}$, which has $7$ elements. Thus, the answer must be at most $7$. Now we claim that if $|B(x)| \leq 6$, then $x$ must be rational. Let $B_k(x)$ be the set of all subsequences of the decimal expansion of $x$ with $k$ digits. So $B_6(x) = B(x)$. We claim that if $|B_k(x)| \leq k$, then $x$ must be rational. We will prove this via induction on $k$. For $k = 1$, $|B_k(x)| \leq k$ becomes $|B_1(x)| = 1$, which makes $x = 0.yyy... = \frac{y}{9}$ for some digit $y$, so $x$ must be rational. Now let's say the statement holds for $k$. We will show that it also holds for $k + 1$. Let $B_{k+1} \leq k + 1$. Note that each subsequence of length $k + 1$ begins with a subsequence of length $k$, so $|B_{k+1}(x)| \geq |B_k(x)|$. Then $|B_k(x)| \leq |B_{k+1}(x)| \leq k + 1$. If $|B_k(x)| \leq k$, then $x$ must be rational. If $|B_k(x)| = |B_{k+1}(x)| = k + 1$, then each subsequence of length $k$ has a one-to-one correspondence with a subsequence of length $k + 1$. This means that after the $k^{th}$ digit, each digit is uniquely determined by the previous $k$ digits. Note that at least one $k$-digit sequence in $B_k(x)$ would eventually repeat itself. Since the sequence after the first appearance must coincide with the sequence after the second appearance, the sequence becomes periodic, thus $x$ must be rational. This completes the induction. Since $x$ is irrational, $|B(x)| \geq 7$. Therefore, the answer is $\boxed{7}$.