Colouring digits to make a rational Number

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Colouring digits to make a rational Number

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: India EGMO 2022 TST P4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

222 posts

#1 h Nov 28, 2021, 11:37 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

222 posts

#2 h Nov 28, 2021, 11:40 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1184 posts

L567

#5 h Nov 28, 2021, 2:03 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

112 posts

#6 h Apr 26, 2025, 1:33 AM

Y by

$N=10$ is achievable by giving each digit its own color. To see why $N=9$ is not, all we need to do is consider the rational
$x=0.0123456789001122\cdots 8899000111\cdots 9990000\cdots$ The rest is left as an exercise to the reader

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a