Number coloring

Is it possible to color every positive real number so that

  • each number is colored one of 10 distinct colors, and
  • any two numbers that differ in exactly one digit are colored differently?

For example, the ten numbers 0.111 , 1.111 , 2.111 , 3.111 , 4.111 , 5.111 , 6.111 , 7.111 , 8.111 , 9.111 {\color{maroon}0.111} \ldots,\, {\color{#D61F06}1.111}\ldots,\, {\color{#EC7300}2.111} \ldots,\, {\color{limegreen}3.111} \ldots,\, {\color{#20A900}4.111} \ldots,\, {\color{teal}5.111} \ldots,\, {\color{#3D99F6}6.111} \ldots,\, {\color{#0C6AC7}7.111} \ldots,\, {\color{#302B94}8.111} \ldots,\, {\color{magenta}9.111} \ldots must all be different colors because any two of them differ in exactly one digit. However, the numbers 10.000 10.000 \ldots and 1.000 1.000 \ldots do not have to be colored differently because they differ in more than one digit.


You may assume the axiom of choice holds.

Yes No

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

5 solutions

George Ivanchyk
Jan 22, 2018

Some numbers might have different decimal notations - they either end with infinitely many zeros or infinitely many nines. If so, we pick the representation with infinitely many zeros.

Set up the binary relation where x y x \sim y if the decimal representation of x x and y y differ by a finite number of digits.
It is easy to verify that this is an equivalence relation since it is reflexive, symmetric, and transitive.
In each equivalence class, by the axiom of choice, we can choose a representative element, which we will denote by a k a k 1 a k 2 a 1 . a 1 a 2 a_k a_{k-1} a_{k-2} \dots a_1 . a_{-1} a_{-2} \dots .
For this equivalence class, given any other element b = b 2 b 1 . b 1 b 2 b = \ldots b_2 b_1 . b_{-1} b_{-2} \ldots , color it with ( a n b n ) ( m o d 10 ) ( \sum_{-\infty}^{\infty} a_n - b_n ) \pmod{10} , where we pad with leading zeros.
By construction, since the infinite sum has a finite number of non-zero terms, hence the sum exists and is an integer.
Then it is easy to check that every two numbers in this subset differing by exactly 1 digit have different colors.
Hence, every two real numbers that differ by exactly 1 digit have different numbers.

You need to take time to specify that you will use recurring zeros instead of recurring nines, whenever the option arises. This is to ensure that your definition of the integers a 1 , a 2 , . . . a_1,a_2,... is well-defined.

To be able to perform the initial partition requires the Axiom of Choice.

Mark Hennings - 3 years, 4 months ago

Log in to reply

I've added in the assumption of using the axiom of choice. Typically for construction/counter-example problems like this, it is allowed.

Calvin Lin Staff - 3 years, 4 months ago

Log in to reply

I’m not arguing with that. It is unusual to need the AofC on Brilliant, though, so I thought it worth highlighting!

Mark Hennings - 3 years, 4 months ago

Note also that some real numbers have multiple decimal representations. For instance 0.50000 = 0.49999 0.50000\dots = 0.49999\dots . They are two different numerals. For instance, 0.50002 0.50002 differs from the former only by one digit, but from the later by infinitely many digits. But they represent the same number, and must therefore have the same color.

Thus, your partition of numerals is not immediately a partition of numbers . Is it possible to assign the same color to all numerals representing the same number , without running into inconsistencies? I believe the answer is yes, but it has to be proven yet!

Arjen Vreugdenhil - 3 years, 4 months ago

I misunderstood the question to mean that any pair must be coloured differently to any other pair.

Paul Sinnett - 3 years, 4 months ago

I think we also need to specify how we are going to handle digits before the decimal point. Every number has a countably infinite number of decimals after the decimal point. Your proof seems to assume that every number has the same number of digits before the decimal point. This is not true, unless you are going to specify that every number has an infinite number of leading zeros as well. This would work, since the fact that there are only finitely many nonzero digits before the decimal point would make your sum converge.

Alternatively, you could dodge the whole "before the decimal point" business by restricting to the interval [ 0 , 1 ) [0,1) , for example.

Mark Hennings - 3 years, 4 months ago

Log in to reply

Like you mentioned, we can modify the writeup slightly so that it is a k a k 1 a 1 . a 1 a 2 a_{k} a_{k-1} \ldots a_1 . a_{-1} a_{-2} \ldots and color ( a n b n ) \sum_{-\infty}^{\infty} (a_n - b_n) with the understanding that a n = 0 a_n = 0 for large n n .

Let me make that edit.

Calvin Lin Staff - 3 years, 4 months ago

1.11111111111111... 1.21111111111111... 1.12111111111111... 1.11211111111111... 1.11121111111111... 1.11112111111111... 1.11111211111111... 1.11111121111111... 1.11111112111111... 1.11111111211111... 1.11111111121111... 1.11111111112111... 1.11111111111211... How do we colour them differently with 10 colours. Here all the numbers(except first one) differ from the first in only digit. Or am I missing something?

saurav shakya - 3 years, 4 months ago

Log in to reply

These numbers, from the second one on, all have to be coloured differently to the first number. However, any two of the "second and on" numbers differ from each other by 2 digits, and so could be coloured the same if we had to...

Mark Hennings - 3 years, 4 months ago

Log in to reply

Ya. I really missed that part. Thank you for clearing it.

saurav shakya - 3 years, 4 months ago

Let's follow the process in the solution. This list of numbers is a subset of an equivalence class since they all differ by finitely many positions.

Let's pick a representative element of 1.2111....

We color 1.1111 with color 9
We color 1.2111 with color 0
We color 1.1211 with color 0
We color 1.1121 with color 0
We color 1.1112 with color 0

Then, it is clear that every number that differs in exactly 1 place has a different color.

Calvin Lin Staff - 3 years, 4 months ago

This was exactly my method! I guess it goes to show that great minds think alike....

Stewart Gordon - 3 years, 4 months ago

Is it true that if we write every real number in base n ( n N , n 2 n \in N, n \geq 2 ), the minimum number of colors we need to use such that the numbers that differ on exactly one digit are colored different is n? I'm just curious about this, since it holds for n = 10.

Javier Álvarez - 3 years, 4 months ago

Log in to reply

Can you apply the above solution to the case when n 10 n \neq 10 ? What remains the same? What has to change?

Calvin Lin Staff - 3 years, 4 months ago
Aidan Hall
Jan 24, 2018

Gray's Reflected Binary code is used to sequence binary numbers such that only one bit changes every time you increment. (Originally designed to prevent misleading output from electromechanical switches while incrementing.)

You can apply the same pattern to a decimal sequence, even an infinite one. 001,002,003,004,005,006,007,008,009,019,018,017,016,015,014,013,012,011,010,020,021... 0.01,0.02,...

If only one digit ever changes per step the sequence can be coloured using 10 colours.

Can you prove that 001 will not be the same colour as 011, 021, 031, 101, 111, 121, etc. when this method is used?

Furthermore, how are you accommodating numbers that don't have finite decimal representations? It would take infinitely many steps to reach even one such number by changing one digit at a time, never mind the fact that the reals are an uncountable set.

Stewart Gordon - 3 years, 4 months ago
Marcus Luebke
Jan 24, 2018

Let each real number be classified by a unique "header" and "tail". The header is finite, while the tail is infinite. For example, every number written as m/(2^a * 5^b) (for integers m,a, and b) has a tail of 00000..., while m/(2^a * 5^b * 9) might have a tail of 11111..., 22222..., 33333..., up to 88888.... The tail for an irrational number like pi is harder to describe, but it still exists.

Group every number by its tail, and choose a number (O) from each group and set its color to zero. Then, for each number (N) go through the digits in the header and add the difference between the digit in N and the digit in O to the color. For any other number that differs from it by a single digit, the sum will be different. Then your done!

For example, 1/16 (0.0625 00000...) might have a color of 0+0+6+2+5=13 mod 10 = 3, while 1/12 (0.083 33333...) might have a color of 0+0+8+3=11 mod 10 = 1.

Mihir Mallick
Jan 22, 2018

Suppose you make an infinite list of decimals and color them with the same color. Then apply Cantor's diagonal method to produce an infinite list of new decimals which differ exactly in one digit and color each decimal in this new list a different color. And then keep repeating this process. (This was an informal arguement just to show the intuition behind the problem)

Since the reals are uncountable, you cannot put them in a list, or an array, to apply a diagonal method to...

Mark Hennings - 3 years, 4 months ago

Is your claim that we need infinitely many colours? I'm not sure what you mean by "keep repeating this process", or how this eventually shows that "10 colours are sufficient".


Also, the diagonalization process gives us (a/many) number which differ from each number in the list by at least one digit, as opposed to "differ exactly in one digit". For example, if you started off with the list of n 9 \frac{n}{9} , then what infinite list of new decimals are you producing?

Calvin Lin Staff - 3 years, 4 months ago
Andrew Khalil
Jan 22, 2018

If we assign colors based on the last digit (the ones position) of the summation of all the digits of each number, it will not be possible for any two numbers to differ in only one digit and have the same color.

Moderator note:

Note: There might not be a "last digit" in a recurring decimal.

E.g. how do we ensure that the numbers 121.11111 121.11111\ldots and 111.1111 111.1111\ldots are colored differently?

What happen your number, like 1 3 \tfrac13 or 2 \sqrt{2} , has an infinite number of digits? You cannot calculate your digit sum.

Mark Hennings - 3 years, 4 months ago

Log in to reply

In the case of numbers with an infinite number of digits, either the two numbers differ by an infinite or finite number of digits. If infinite, it doesn't matter if they are colored the same. If finite, you could just calculate the digit sum on only that finite list of digits.

John Ross - 3 years, 4 months ago

Log in to reply

OK, provided you set up the equivalence classes like George does, you can have a rule for each equivalence class. The initial setup needs to be made clear, though.

Mark Hennings - 3 years, 4 months ago

If two numbers with infinitely many nonzero digits differ by one digit (e.g. 2 \sqrt2 and 2 0.001 \sqrt2-0.001 ), they will still need to be coloured differently. So by your method, you still need a way to sum the digits of such numbers.

Stewart Gordon - 3 years, 4 months ago

Calculating the digit sum on that finite list of digits wouldn't work. For instance, the number 3.141592... would have the digit sum 1 when you're comparing it against 3.142592..., but the digit sum 4 when you're comparing it against 3.131592....

Stewart Gordon - 3 years, 4 months ago

We don't need to know what particular color any number is to know that it differs from the color of another.

Whatever the answer for 1/3, it must surely differ from that of 1/3 + 0.001, because the perturbation of a single digit must change the result of the sum mod 10.

Jake Boeckerman - 3 years, 4 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...