wu :: forums
« wu :: forums - Coloring the rational plane »

Welcome, Guest. Please Login or Register.
Nov 18th, 2018, 4:37pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: Eigenray, ThudnBlunder, Grimbal, towr, Icarus, SMQ, william wu)
   Coloring the rational plane
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Coloring the rational plane  (Read 2620 times)
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Coloring the rational plane  
« on: Jul 23rd, 2004, 9:43am »
Quote Quote Modify 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: male
Posts: 1321
Re: Coloring the rational plane  
« Reply #1 on: Jul 23rd, 2004, 3:56pm »
Quote Quote Modify 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: male
Posts: 1321
Re: Coloring the rational plane  
« Reply #2 on: Jul 24th, 2004, 12:41pm »
Quote Quote Modify 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.  Embarassed
 
IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Coloring the rational plane  
« Reply #3 on: Jul 24th, 2004, 1:24pm »
Quote Quote Modify 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: male
Posts: 1948
Re: Coloring the rational plane  
« Reply #4 on: Jul 24th, 2004, 4:47pm »
Quote Quote Modify 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: male
Posts: 1001
Re: Coloring the rational plane  
« Reply #5 on: Jul 25th, 2004, 12:10am »
Quote Quote Modify 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: male
Posts: 2276
Re: Coloring the rational plane  
« Reply #6 on: Jul 25th, 2004, 3:51am »
Quote Quote Modify 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?  Undecided
 
It seems that for k=1 the answer is still the same...
IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Coloring the rational plane  
« Reply #7 on: Jul 25th, 2004, 11:47am »
Quote Quote Modify Modify

on Jul 25th, 2004, 3:51am, Barukh wrote:

 
I wonder: is it meaningful to ask this question for [bbr]k?  Undecided
 
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: male
Posts: 1948
Re: Coloring the rational plane  
« Reply #8 on: Jul 26th, 2004, 6:14am »
Quote Quote Modify 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?  Undecided

Any sufficiently nice problem is a classic Wink  
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 Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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