wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> medium >> Coloring the rational plane
(Message started by: Eigenray on Jul 23rd, 2004, 9:43am)

Title: Coloring the rational plane
Post by Eigenray on Jul 23rd, 2004, 9:43am
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

Title: Re: Coloring the rational plane
Post by Aryabhatta on Jul 23rd, 2004, 3:56pm
Nice problem Eigenray.

For k = 1.
[]
[hide]
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.

[/hide]

For k = 2
[hide]

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.

[/hide]
[]

Title: Re: Coloring the rational plane
Post by Aryabhatta on Jul 24th, 2004, 12:41pm

on 07/23/04 at 15:56:17, Aryabhatta wrote:
[hide]
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. - (*)

[/hide]


Ok. So that proves that there is no triangle. That does not imply a 2 colouring.  :-[


Title: Re: Coloring the rational plane
Post by Aryabhatta on Jul 24th, 2004, 1:24pm
Ok. Hopefully a correct proof for k = 2.
[]
[hide]

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.

[/hide]
[]

Title: Re: Coloring the rational plane
Post by Eigenray on Jul 24th, 2004, 4:47pm
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 07/23/04 at 15:56:17, 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 (http://planetmath.org/encyclopedia/PicksTheorem.html))

Title: Re: Coloring the rational plane
Post by TenaliRaman on Jul 25th, 2004, 12:10am

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?)

Title: Re: Coloring the rational plane
Post by Barukh on Jul 25th, 2004, 3:51am
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...

Title: Re: Coloring the rational plane
Post by Aryabhatta on Jul 25th, 2004, 11:47am

on 07/25/04 at 03:51:08, 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.
[]
[hide]

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.

[/hide]

Title: Re: Coloring the rational plane
Post by Eigenray on Jul 26th, 2004, 6:14am

on 07/25/04 at 03:51:08, 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 ([hide]4[/hide] [le] [chi] [le] [hide]7[/hide]) have not changed since then.  Both bounds have elementary proofs (see, for example, problem A4 on the 1988 Putnam).



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board