Author 
Topic: Coloring the rational plane (Read 2584 times) 

Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Coloring the rational plane
« on: Jul 23^{rd}, 2004, 9:43am » 
Quote Modify

This is a classic that doesn't seem to be on the site: How many colors are required to color every point of [bbq]^{k} in such a way that no two points a unit distance apart are the same color? Easy: k=1 Medium: k=2,3 Hard: k > 3


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Coloring the rational plane
« Reply #1 on: Jul 23^{rd}, 2004, 3:56pm » 
Quote Modify

Nice problem Eigenray. For k = 1. [] Consider the rationals in [0,1). Give a random colouring to those, say f:[0,1)> {R,B} Extend f to Q using f(r) = f({r}) iff [r] is even. [r] is integral part and {r} is fractional part of r. Any two points a unit distance apart are coloured differently using this colouring. So for k = 1, 2 colours are sufficient. For k = 2 For k = 2 also 2 colours are sufficient i think. I think we can show that if PQR is an equilateral triangle with side 1, then one of the points P, Q, R has to have an irrational coordinate.  (*) So we have the following: Pick a rational point Q. Colour it Red. Colour all rational points at a distance 1 from Q Blue. Since we do not have a triangle, all the rational points can be coloured with just 2 colours so that no two a unit distance apart are given the same colour. I think (*) might apply to the 3D case too. []


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Coloring the rational plane
« Reply #2 on: Jul 24^{th}, 2004, 12:41pm » 
Quote Modify

on Jul 23^{rd}, 2004, 3:56pm, Aryabhatta wrote: For k = 2 also 2 colours are sufficient i think. I think we can show that if PQR is an equilateral triangle with side 1, then one of the points P, Q, R has to have an irrational coordinate.  (*) 
 Ok. So that proves that there is no triangle. That does not imply a 2 colouring.


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Coloring the rational plane
« Reply #3 on: Jul 24^{th}, 2004, 1:24pm » 
Quote Modify

Ok. Hopefully a correct proof for k = 2. [] For k = 2, 2 colours are sufficient. Consider the rational points on the circle x^{2} + y^{2} = 1. If (r,s) is a rational point on that circle and r and s are written in lowest terms then denominators of r and s have to be odd. Also the numerators are of different parity (i.e. one is odd and one is even). This follows from the solutions to the pythagorean triplet problem. Now consider the unit circle with center (r,s). Now any rational point say (r_{1},s_{1}) on this circle is of the form (even/odd + even/odd, odd/odd + odd/odd) or (even/odd + odd/odd,odd/odd + even/odd) which is basically (even/odd,even/odd) or (odd/odd, odd/odd) Thus parities of the numerators of r_{1} and s_{1} is the same. Continuing this way we see that the parity of numerators of r_{i} and s_{i} are same only if i is odd. (i.e. as i gets larger the parities flip between being same and being different) We started at (0,0). This means that we cannot have a cycle of odd length, which gives us a 2colouring. Hope I haven't goofed up this time. []


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Coloring the rational plane
« Reply #4 on: Jul 24^{th}, 2004, 4:47pm » 
Quote Modify

Yes, excellent. And the case k=3 is not hard once you've done k=2. Unfortunately, this method doesn't work for k [ge] 4, and I don't even know what the answer is for that case. on Jul 23^{rd}, 2004, 3:56pm, Aryabhatta wrote:I think we can show that if PQR is an equilateral triangle with side 1, then one of the points P, Q, R has to have an irrational coordinate. 
 (A nice proof of this invokes Pick's Theorem)


IP Logged 



TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001


Re: Coloring the rational plane
« Reply #5 on: Jul 25^{th}, 2004, 12:10am » 
Quote Modify

Quote:Yes, excellent. And the case k=3 is not hard once you've done k=2. 
 Would one use a unit sphere for this? (are the denominators still odd in this case?)

« Last Edit: Jul 25^{th}, 2004, 12:19am by TenaliRaman » 
IP Logged 
Self discovery comes when a man measures himself against an obstacle  Antoine de Saint Exupery



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Coloring the rational plane
« Reply #6 on: Jul 25^{th}, 2004, 3:51am » 
Quote Modify

Very elegant solution for a very nice problem! I haven't heard about this classic (?) before. I wonder: is it meaningful to ask this question for [bbr]^{k}? It seems that for k=1 the answer is still the same...


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Coloring the rational plane
« Reply #7 on: Jul 25^{th}, 2004, 11:47am » 
Quote Modify

on Jul 25^{th}, 2004, 3:51am, Barukh wrote: I wonder: is it meaningful to ask this question for [bbr]^{k}? It seems that for k=1 the answer is still the same... 
 For k=2 we require at least 4 colours. [] Assume that we can 3colour the plane so that any two points a distance 1 are given different colours. Under this assumption we can show that: Given any two points XY such XY = [sqrt]3, then colour of X is same as the colour of Y.  (*) Using this we can show that all points of the plane have to be coloured the same colour which gives rise to a contradiction. This can be done because starting at P, we can find a polygonal line to any other point Q such that the each vertex of the line is [sqrt]3 away from the previous vertex. Now to prove (*). Given points X and Y such that XY = [sqrt]3. Let BC be the perpendicular bisector of XY such that XBC and YBC are equilateral triangles of side 1. Say colour of X is red. Under the assumption that no two points a unit distance apart are coloured the same, B is green and C is blue say. Then Y has to be red, the same colour as X.


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Coloring the rational plane
« Reply #8 on: Jul 26^{th}, 2004, 6:14am » 
Quote Modify

on Jul 25^{th}, 2004, 3:51am, Barukh wrote:Very elegant solution for a very nice problem! I haven't heard about this classic (?) before. I wonder: is it meaningful to ask this question for [bbr]^{k}? 
 Any sufficiently nice problem is a classic The case of [bbr]^{k} ("The chromatic number of the plane") is a famous problem that has been open since 1956, and the best known bounds (4 [le] [chi] [le] 7) have not changed since then. Both bounds have elementary proofs (see, for example, problem A4 on the 1988 Putnam).


IP Logged 



