wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Irrational Colouring
        
(Message started by: Barukh on May 21^st, 2006, 11:20pm)

Title: Irrational Colouring
Post by Barukh on May 21^st, 2006, 11:20pm

An irrational marker put at point P in the plane colours all points in the plane that are at irrational distance from P.

How many irrational markers are needed to colour the entire plane?

Title: Re: Irrational Colouring
Post by JocK on May 22^nd, 2006, 11:05am

I'd say: in N dimensions you need [hide]N+1[/hide] irrational markers.

Title: Re: Irrational Colouring
Post by Barukh on May 22^nd, 2006, 10:18pm

on 05/22/06 at 11:05:05, JocK wrote:

I'd say: in N dimensions you need [hide]N+1[/hide] irrational markers.

Are you sure? ;)

Title: Re: Irrational Colouring
Post by Sjoerd Job Postmus on May 23^rd, 2006, 10:20am

Let us consider the plane we have, and place a marker on it.

We find a lot of circles, all with a rational radius.

Now, think of any irrational distance, and put another marker there!

All points on the line through your two markers are covered, and probably a lot more points. But, we're not there yet. We still have a lot of points that are on a rational distance from both.

Now, my idea is, to make a triangle of the three points, with all sides being irrational in length. I suppose, but can't know for sure, that all points are covered. Can't prove it.

Title: Re: Irrational Colouring
Post by JocK on May 23^rd, 2006, 10:47am

on 05/22/06 at 22:18:31, Barukh wrote:

Are you sure? ;)

Only if you agree that in N dimensions one can arrange N markers such that only a denumerable number of points are left uncloured... 8)

Title: Re: Irrational Colouring
Post by SMQ on May 23^rd, 2006, 7:27pm

I definitely agree with JocK's last statement, but I'm not sure that's a sufficient condition for N+1 markers to color the N-space. Just because N markers leave a countable infinity of points uncovered, it doesn't seem to me to follow that there necessarily exists a marker which covers all of them, or even that the first N markers can necessarily be chosen such that the N+1^st marker covers all the uncovered points.

In fact, after fiddling around with some messy algebra (by hand--can't justify the cost of Mathematica or Maple just for puzzle solving), I'm leaning slightly toward the other extreme--needing aleph-null markers to color any space of dimension >1.

--SMQ

Title: Re: Irrational Colouring
Post by Barukh on May 24^th, 2006, 12:13am

The current consensus seems to be that N+1 markers are necessary for N dimensions. ;)

Let's go back to original question: as Sjoerd notices, 2 markers are not enough in the plane. Will 3 markers suffice? If yes, how?

Title: Re: Irrational Colouring
Post by Eigenray on May 24^th, 2006, 8:26am

on 05/23/06 at 19:27:10, SMQ wrote:

Just because N markers leave a countable infinity of points uncovered, it doesn't seem to me to follow that there necessarily exists a marker which covers all of them

For any given point, the set of markers which will not color it is a countable union of spheres S^N-1 [subset] R^N, which each have Lebesgue measure 0. Hence for any countable collection of points, the set of markers coloring all of them has full measure, so almost any position will work.

For concreteness, one may imagine a spherical shell of measure 2^-i-j enclosing the set of all points a distance r_j from P_i, where {r_j} is an enumeration of the rationals, and {P_i} is the set of uncolored points. The union of all these shells has measure < 1, and any marker outside all of them will color every P_i.

Title: Re: Irrational Colouring
Post by JocK on May 24^th, 2006, 10:51am

on 05/23/06 at 19:27:10, SMQ wrote:

Just because N markers leave a countable infinity of points uncovered, it doesn't seem to me to follow that there necessarily exists a marker which covers all of them

The union of denumerable many sets each containing a denumerable number of elements, constitutes a denumerable set.

Now, assuming that N markers leave denumerable many uncoloured points, it follows that the set of points on an arbitrary line in N-dimensional space that are unsuitable for placing the N+1^th marker is denumerable... I.e. out of the innumerable many points on the line, you can choose virtually any point as last marker.

(Basically just echoing here what Eigenray already mentioned. 8) )

Title: Re: Irrational Colouring
Post by SMQ on May 24^th, 2006, 11:36am

OK, I concede already. ;D

From the set theory side, my problem was that I was looking for a constructive solution. The set of points at a given radius from a fixed point is uncountable, and so I could imagine that the union of countably many uncountable sets could cover the plane--especially since the rationals provide a "good approximation" to the reals; but between Eigenray's Lebesgue measure method and JocK's line intersection method I can see the error of my ways.

That still leaves the question of whether or not there exists a constructive method for picking N+1 such points.

Clearly it is necessary that every point have at least one other point an irrational distance away, but is it necessary that the distance between any pair of points be irrational? Is either condition sufficient?

--SMQ

Title: Re: Irrational Colouring
Post by Sjoerd Job Postmus on May 24^th, 2006, 1:35pm

I'm pondering a bit...

Could I do this:

Let's take an irrational distance, sqrt{3}, just for kicks...

Now, I'm going to take N=0.

I have only one point, which I'll put a marker at. Because the marker is 0 away from the point, it's unsolvable with any number of markers...

Anyhow, Ignore that... take our current N=0 solution, and suddenly, look at the bigger picture, the line we put our marker on! N=1.

Ok, so we have 1 marker on a line, which is not enough, because there are a lot of points still uncovered...

Now, let's add a marker at our chosen distance: sqrt{3}... I say that all points are now covered.

Why?

Say: Marker Original is on position x=0... just for kicks...
Marker 2 would be on x=sqrt{3}

Let us take a point on rational distance from x, which would have d₁=p/q
But the distance from the second marker would be:
d₂ = sqrt{3} - p/q
Which is clearly irrational (no proof, but it's provable, you go ahead). So, it is covered.

So we can cover N=1 with 2 markers... proven

Now, N=2... let's take our original solution, and extend it.

I myself would try and make an isoles(sp?) triangle... with sides sqrt(3)... but would it work? I'd guess so...

Can someone prove this works?

Title: Re: Irrational Colouring
Post by Eigenray on May 24^th, 2006, 1:50pm

on 05/24/06 at 00:13:57, Barukh wrote:

The current consensus seems to be that N+1 markers are necessary for N dimensions. ;)

Wait, I never consented to that! If you can find 3 markers [hide]on a line[/hide] that color the plane, they'll also color [hide]any other plane through that line[/hide]. So for R^N you need just [hide]min(N+1,3)[/hide] markers.

Title: Re: Irrational Colouring
Post by JocK on May 24^th, 2006, 2:28pm

Ha, yes... it was there all the time.. staring us right in the face.. ;D

Well done Eigenray!

Title: Re: Irrational Colouring
Post by Sjoerd Job Postmus on May 25^th, 2006, 3:54am

on 05/24/06 at 13:50:03, Eigenray wrote:

Which raises one question: Can we do it with 3 markers on a line, at all? Would that work?

Intuition says "no", but who knows.

Anyhow, let's place a marker at -infinity, and define a point (p,q) (from real)

Since the distance between (-infinity,0) and (p,q) is infinity (which is clearly not a rational number anyhow ), (p,q) is coloured.

But anyhow, this idea is flawed ;) we shouldn't apply normal rules to infinity... ;)

Title: Re: Irrational Colouring
Post by JocK on May 25^th, 2006, 11:16am

on 05/25/06 at 03:54:44, Sjoerd Job Postmus wrote:

Which raises one question: Can we do it with 3 markers on a line, at all? Would that work?

If you read the thread carefully, you'll see that the answer to this question has been given... In fact, you are very, very unlucky in case - after randomly placing three markers on a line - you are left with uncoloured points.

Title: Re: Irrational Colouring
Post by JocK on May 25^th, 2006, 11:49am

on 05/24/06 at 11:36:58, SMQ wrote:

[..] is it necessary that the distance between any pair of points be irrational? Is either condition sufficient?

The right question to ask - I think - is:

How many markers do you need in R^N to colour all points that are not covered by a marker, in case you are not allowed to place a marker at a point that is an irrational distance from another marker.

(For a related problem, see: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1148507742)

Title: Re: Irrational Colouring
Post by Eigenray on May 25^th, 2006, 12:06pm

Suppose (x,y) is a rational distance from all three points (0,0), (1,0), and (z,0). Then
(1) x² + y² = r²
(2) (x-1)² + y² = s²
(3) (x-z)² + y² = t²
with r,s,t rational. Subtracting (2)-(1) shows x is rational, and (3)-(1) gives
z² - 2xz + r²-t² = 0,
which means z is algebraic over Q (and of degree <2). So there are only countably many choices for z which won't give a contradiction here (at most 2 for each of the countably many possibilities for x,r,t).

For specific examples, the points (0,0), (1,0), (z,0) will work for z=2^1/3, e, pi, etc.

Title: Re: Irrational Colouring
Post by Barukh on May 26^th, 2006, 11:17pm

Nicely done! :D

I personally prefer a configuration where three points on a line are equally spaced.

Title: Re: Irrational Colouring
Post by JocK on May 26^th, 2006, 11:55pm

on 05/26/06 at 23:17:44, Barukh wrote:

I personally prefer a configuration where three points on a line are equally spaced.

I think Eigenray wanted to demonstrate that you can allow one of the distances between three markers on a line to be rational, and stil colour whole R^N.

The question how many markers you need when all are to be placed at mutually rational distances, is still open...

Title: Re: Irrational Colouring
Post by Sjoerd Job Postmus on May 27^th, 2006, 2:19am

on 05/26/06 at 23:55:58, JocK wrote:

If you really want a mutual rational distance, you can't solve this problem on a line...

Let's think of three markers...
(0,0), (p/q, 0), (r/s,0)
Let's define another point: (t/u,0)

distance to point one: t/u
distance to point two: t/u - p/q = (tq - up)/uq
distance to point three: t/u - r/s = (ts - ur)/ur
Which is another way of saying: The distances are all rational.

So, you can't solve it using only a line, if you are limited to rational distances.