Author |
Topic: Coloring the rational plane (Read 3093 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Coloring the rational plane
« on: Jul 23rd, 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 23rd, 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 co-ordinate. - (*)
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 3-D case too.
[]
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Coloring the rational plane
« Reply #2 on: Jul 24th, 2004, 12:41pm » |
Quote Modify
|
on Jul 23rd, 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 co-ordinate. - (*)
|
|
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 24th, 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 x2 + y2 = 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 (r1,s1) 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 r1 and s1 is the same.
Continuing this way we see that the parity of numerators of
ri and si 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 2-colouring.
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 24th, 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 23rd, 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 co-ordinate. |
|
(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 25th, 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 25th, 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 25th, 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 25th, 2004, 11:47am » |
Quote Modify
|
on Jul 25th, 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 3-colour 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 26th, 2004, 6:14am » |
Quote Modify
|
on Jul 25th, 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print