Author |
Topic: Irrational Colouring (Read 1265 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Irrational Colouring
« on: May 21st, 2006, 11:20pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Irrational Colouring
« Reply #1 on: May 22nd, 2006, 11:05am » |
Quote Modify
|
I'd say: in N dimensions you need N+1 irrational markers.
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Irrational Colouring
« Reply #2 on: May 22nd, 2006, 10:18pm » |
Quote Modify
|
on May 22nd, 2006, 11:05am, JocK wrote:| I'd say: in N dimensions you need N+1 irrational markers. |
|
Are you sure? 
|
|
IP Logged |
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: Irrational Colouring
« Reply #3 on: May 23rd, 2006, 10:20am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Irrational Colouring
« Reply #4 on: May 23rd, 2006, 10:47am » |
Quote Modify
|
on May 22nd, 2006, 10:18pm, 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... 
|
| « Last Edit: May 23rd, 2006, 10:51am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Irrational Colouring
« Reply #5 on: May 23rd, 2006, 7:27pm » |
Quote Modify
|
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+1st 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
|
|
IP Logged |
--SMQ
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Irrational Colouring
« Reply #6 on: May 24th, 2006, 12:13am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Irrational Colouring
« Reply #7 on: May 24th, 2006, 8:26am » |
Quote Modify
|
on May 23rd, 2006, 7:27pm, 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 SN-1 [subset] RN, 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 rj from Pi, where {rj} is an enumeration of the rationals, and {Pi} 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 Pi.
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Irrational Colouring
« Reply #8 on: May 24th, 2006, 10:51am » |
Quote Modify
|
on May 23rd, 2006, 7:27pm, 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+1th 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. )
|
| « Last Edit: May 24th, 2006, 11:04am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Irrational Colouring
« Reply #9 on: May 24th, 2006, 11:36am » |
Quote Modify
|
OK, I concede already. 
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
|
|
IP Logged |
--SMQ
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: Irrational Colouring
« Reply #10 on: May 24th, 2006, 1:35pm » |
Quote Modify
|
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 d1=p/q
But the distance from the second marker would be:
d2 = 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?
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Irrational Colouring
« Reply #11 on: May 24th, 2006, 1:50pm » |
Quote Modify
|
on May 24th, 2006, 12:13am, 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 on a line that color the plane, they'll also color any other plane through that line. So for RN you need just min(N+1,3) markers.
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Irrational Colouring
« Reply #12 on: May 24th, 2006, 2:28pm » |
Quote Modify
|
Ha, yes... it was there all the time.. staring us right in the face..
Well done Eigenray!
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: Irrational Colouring
« Reply #13 on: May 25th, 2006, 3:54am » |
Quote Modify
|
on May 24th, 2006, 1:50pm, Eigenray wrote:
Wait, I never consented to that! If you can find 3 markers on a line that color the plane, they'll also color any other plane through that line. So for RN you need just min(N+1,3) markers. |
|
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...
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Irrational Colouring
« Reply #14 on: May 25th, 2006, 11:16am » |
Quote Modify
|
on May 25th, 2006, 3:54am, 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.
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Irrational Colouring
« Reply #15 on: May 25th, 2006, 11:49am » |
Quote Modify
|
on May 24th, 2006, 11:36am, 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 RN 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_har d;action=display;num=1148507742)
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Irrational Colouring
« Reply #16 on: May 25th, 2006, 12:06pm » |
Quote Modify
|
Suppose (x,y) is a rational distance from all three points (0,0), (1,0), and (z,0). Then
(1) x2 + y2 = r2
(2) (x-1)2 + y2 = s2
(3) (x-z)2 + y2 = t2
with r,s,t rational. Subtracting (2)-(1) shows x is rational, and (3)-(1) gives
z2 - 2xz + r2-t2 = 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=21/3, e, pi, etc.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Irrational Colouring
« Reply #17 on: May 26th, 2006, 11:17pm » |
Quote Modify
|
Nicely done! 
I personally prefer a configuration where three points on a line are equally spaced.
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Irrational Colouring
« Reply #18 on: May 26th, 2006, 11:55pm » |
Quote Modify
|
on May 26th, 2006, 11:17pm, 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 RN.
The question how many markers you need when all are to be placed at mutually rational distances, is still open...
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: Irrational Colouring
« Reply #19 on: May 27th, 2006, 2:19am » |
Quote Modify
|
on May 26th, 2006, 11:55pm, JocK wrote:
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 RN.
The question how many markers you need when all are to be placed at mutually rational distances, is still open...
|
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print