Let $N$ be a positive integer. Suppose given any real $x\in (0,1)$ with decimal representation $0.a_1a_2a_3a_4\cdots$, one can color the digits $a_1,a_2,\cdots$ with $N$ colors so that the following hold: 1. each color is used at least once; 2. for any color, if we delete all the digits in $x$ except those of this color, the resulting decimal number is rational. Find the least possible value of $N$. ~Sutanay Bhattacharya
Problem
Source: India EGMO 2022 TST P4
Tags: number theory, combinatorics
28.11.2021 14:40
The answer is $N=10$. Let us first prove that $N\ge 10$ always works. Take the decimal expansion of $x$, color the first $N$ digits with the $N$ colors in any order, and from that point on, color every $0$ with the first color, every $1$ with the second color, \dots, and every $9$ with the tenth color (if $x$ has a finite decimal expansion, we assume there are infinitely many zeros after the last non-zero digit; clearly this changes nothing). Now for every color, the decimal formed by digits of that colors eventually becomes a single digit repeated, so it's rational. Now we will prove that $N\le 9$ cannot work. Take $x$ to be the following number: $$x=0.0123456789001122\cdots 8899000111\cdots 9990000\cdots.$$The $i$-th block has $0$ $i$ times, $1$ $i$ times, \dots, $9$ $i$ times; then the $(i+1)$-th block begins. Now suppose we can color this with $N$ colors as stipulated. Let $x_i$ be the decimal formed by all the digits with the $i$-th color. Since $x_i$ is rational, it's decimal expansion is eventually periodic; suppose it's period length is $d_i$. Suppose the last digit in $x$ that occurs in any of the non-periodic parts of the $x_i$s is at position $A$. Let $M=\max\{d_1,\cdots, d_N\}$. In the decimal expansion of $x$, one can find a string of at least $N(M+1)$ consecutive zeros that occurs after the $A$-th place. Then some color must have at least $M$ zeros from this part, say the $j$-th color. Then $x_j$ has a string of at least $d_j$ zeros after its non-periodic part; so the entire period must be a string of zeros. In other words, after some point, all the digits of $x_j$ are $0$. Similarly, for every digit $d$ in $\{0,1,\cdots, 9\}$, one can find some $x_j$ so that all digits of $x_j$ are $d$ after some point. But there are ten possible $d$'s, and only $N<10$ possible $x_j$'s, so this is impossible.
28.11.2021 17:03
Consider the number $x$ containing every digit $1,2,3,\cdots,9,0$ once, then twice, thrice etc. If a color has only one digit eventually, then it has density at most $\frac{1}{10}$. If a color has more than one digit, there are two consecutive digits, WLOG let it be $01$. Consider the first $5M(M+1) + c$ numbers for sufficiently large constant $c$ so that after $c$ it is periodic, it has at most $M+c$ instances of $01$. Take $M$ large so we have density of this color is $0$. So there must be at least $10$ colors. And $N = 10$ works by giving each digit its own color.