Is it possible to color every positive real number so that
For example, the ten numbers 0 . 1 1 1 … , 1 . 1 1 1 … , 2 . 1 1 1 … , 3 . 1 1 1 … , 4 . 1 1 1 … , 5 . 1 1 1 … , 6 . 1 1 1 … , 7 . 1 1 1 … , 8 . 1 1 1 … , 9 . 1 1 1 … must all be different colors because any two of them differ in exactly one digit. However, the numbers 1 0 . 0 0 0 … and 1 . 0 0 0 … do not have to be colored differently because they differ in more than one digit.
You may assume the axiom of choice holds.
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.
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 , . . . is well-defined.
To be able to perform the initial partition requires the Axiom of Choice.
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.
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!
Note also that some real numbers have multiple decimal representations. For instance 0 . 5 0 0 0 0 ⋯ = 0 . 4 9 9 9 9 … . They are two different numerals. For instance, 0 . 5 0 0 0 2 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!
I misunderstood the question to mean that any pair must be coloured differently to any other pair.
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 ) , for example.
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 … and color ∑ − ∞ ∞ ( a n − b n ) with the understanding that a n = 0 for large n .
Let me make that edit.
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?
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...
Log in to reply
Ya. I really missed that part. Thank you for clearing it.
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.
This was exactly my method! I guess it goes to show that great minds think alike....
Is it true that if we write every real number in base n ( n ∈ N , n ≥ 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.
Log in to reply
Can you apply the above solution to the case when n = 1 0 ? What remains the same? What has to change?
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.
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.
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...
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 9 n , then what infinite list of new decimals are you producing?
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.
Note: There might not be a "last digit" in a recurring decimal.
E.g. how do we ensure that the numbers 1 2 1 . 1 1 1 1 1 … and 1 1 1 . 1 1 1 1 … are colored differently?
What happen your number, like 3 1 or 2 , has an infinite number of digits? You cannot calculate your digit sum.
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.
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.
If two numbers with infinitely many nonzero digits differ by one digit (e.g. 2 and 2 − 0 . 0 0 1 ), they will still need to be coloured differently. So by your method, you still need a way to sum the digits of such numbers.
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....
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.
Problem Loading...
Note Loading...
Set Loading...
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 if the decimal representation of x and 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 … .
For this equivalence class, given any other element b = … b 2 b 1 . b − 1 b − 2 … , color it with ( ∑ − ∞ ∞ a n − b n ) ( m o d 1 0 ) , 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.