wu :: forums « wu :: forums - Coloring the rational plane » Welcome, Guest. Please Login or Register. Apr 26th, 2019, 2:48am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    medium (Moderators: ThudnBlunder, Icarus, Eigenray, william wu, towr, Grimbal, SMQ)    Coloring the rational plane « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Coloring the rational plane  (Read 2649 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

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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »