Good Mornings.

First person to solve/prove this gets 1kpp. (sorry for the low offer but haven't been on much and question isn't all that challenging).


Let every point on R^2 (the cartesian plane) is colored either red, white, or blue. Prove that there must exist 2 points, distance 1 apart, with the same color. :D

P.S. This is actually a very good question well worth spending the time to think about.


Good Lucks,
Foreverlive.

The answer is 42.

And if you doubt my math, remember that: .99 = 3/3 = 1, therefore, .99 = 1

Yes it is most certainly 42...


"I checked it very thoroughly," said the computer, "and that quite definitely is the answer. I think the problem, to be quite honest with you, is that you've never actually known what the question is."(Douglas Adams)

Heh, you can (incorrectly) prove 0 to equal 1 with a bit of simple calculus ;)

You can incorrectly prove all sorts of things...

So I passed this on to my gEEk brother who works for GTRI (Ga. Tech Res. Inst.) and was the one who received the math brain in the family. He said: Define R. and he will solve it.

Does your R^2 come with or without the axiom of choice?

But that is the issue… There can not a R on the Cartesian plane, so how can you not have a R^2. The Cartesian Plan consist of x and y and the imaginary plan consist of x and j. If I assume that R is X, than I a hyperbola, but to get a number one point away I have to use a number greater than 1.0 with a very small faction. As the number grows from 1.00 toward 2.00 because of the R^2 factor, I will be 2 points 1 distance apart as I approach 2.0. In addition, my calculations show that one greater than me is needed to solve this problem because in the end all numbers lead to …. You guess it 42. So I must wait until 4/29/05 for the true enlightenment of the greater one.



And we must not forget that 6.4808^2 is … you guessed it 42.000….

Does your R^2 come with or without the axiom of choice?

feel free to use the axiom of choice if it helps. this is a typical combinatorial geometry/ramsey/pigeon hole type problem. :D

oh no i lost my towel!

True, the axiom of choice isn't required. My bad.

Define Colour(R^2)->{R,G,B} to be a 3 colouring of R^2.

A purely constructive proof:

Define the double-triangle to be points ABCD in an arrangement of points like:

AB
CD
where ABC and BCD are equilateral triangles with side length 1.

Claim: In any such double-triangle, either Colour(A) = Colour(D), or two points 1 distance apart in ABCD share the same colour. The proof is trivial.

[]

Corrollory: Let L be the distance between A and D in a double triangle.

Either any two points in the plane of distance L apart have the same colour, or two points on the plane 1 distance apart share the same colour.

[]

Let XYZ be any isosolese triangle such that length(XY)=length(XZ)=L, and length(YZ)=1

Then, by the corrollory above, colour(Z)=colour(X) and colour(Y)=colour(X), or two points on the plane 1 distance apart share the same colour. Thus colour(Z)=colour(Y), or two points on the plane 1 distance apart share the same colour.

As length(YZ)=1, this means that two points 1 distance apart share the same colour.

Laeyakk,

I don't think the proof is correct. The logic doesn't follow after the corollary. Hope you are having fun. hehe :D


Foreverlive.

Each point on R^2 is surrounded by 4 points. Let's define our point of interest to be (0,0). So the surrounding points are [counterclockwise] (1,0), (0,1), (-1,0) and (0,-1). There are 3 colors. The pigeon hole principle says that with 5 slots, and only 3 colors, there will be at least one color on 2 points. So, it looks like there is a solution...

However.....
Let Tiles X and Y consist of 5 points. Let R, W, B denote the colors red, white and blue. The tiles are cross shaped, so that if a tile was located at the origin, it would contain (0,0), (1,0), (0,1), (-1,0) and (0,-1). Underscores are used to make the "code" tags actually look like what I'm trying to describe.

Tile X

_B
RWB
_R
So if tile X is placed at the origin,
Point Color
(0,0) White
(1,0) Blue
(0,1) Blue
(-1,0) Red
(0,-1) Red

Tile Y

_W
BRW
_B
So, if Tile Y is placed at the origin,
Point Color
(0,0) Red
(1,0) White
(0,1) White
(-1,0) Blue
(0,-1) Blue

With tiles X, Y, one can cover a surface so that all points of R^2 are covered. Tiles X and Y are placed in a diagonal (ascending to the right) and the colors appear to be diagonals descending to the right. Since similar colored items are on the diagonal, their distance is 1.414 (square root of 2).

Tiling (X = part of Tile X, Y = part of Tile Y, color of letter is color in tile, black= origin, and green stands in for white since white is kinda invisible, and it does suck badly and I'm not staying up to make a jpg/gif to show you better):

XXXXX
XXXXY
YXYYY

You can see where it is going if you take 2 Tiles X and place the center of one at (0,0) and the other at (2, 1). Take 2 Tiles Y and place the center of one at (1,-1) and the other at (3, -1). As you proceed down the diagonal that descends as it goes to the right, you will alternate TileX, TileY, FlipTileX, FlipTileY, TileX and so on.

Therefore....
By contradiction, there exists a coloring such that no points of similar color are 1.0 unit apart.

Smidgit,

Nice thinking. However, I don't think that is sufficient as a counterexample of a coloring because you have provided a coloring of a very small subset of the plane. Your arguement is similar to
...........................
R_W_B_R_W_B...
_B_R_W_B_R_W_B...
R_W_B_R_W_B_R_W_B...
.....................................

where the above is a tiling of the plane with equilaterial triangles. Seemingly probable, it's only coloring the vertices of the tiling triangles and ignoring the "interiors" which gives problem. :D


Foreverlive.

WTF is palarran, he invented math damnit.

My head hurts......

"What if dog was really spelled C-A-T?" Anyone know the name of the movie and actor who said it?

Just a little fun intervention so that people like me don't have to think that hard. :)

BTW I'm still waiting for someone to define R

This is math? :confused:

Revenge of the nerds 2, Orgre (Donald Gibb)

R is the set of Real numbers

R^2 is a set of pairs of numbers (X,Y), where X,Y are Real numbers. This defines a cartesian plane.

I can't remember the proof, but I seem to remember that Dirac did the origonal one.

Laeyakk,

I don't think the proof is correct. The logic doesn't follow after the corollary. Hope you are having fun. hehe :D


Foreverlive.

Please point out the mistake after the corrollory. I'm hoping it's just a typo.

Here is a clearer version of it:

If any two points of distance L from each other are the same colour, and you arrange 3 points into an isosolese triangle of side lengths L L and 1, then all 3 points must be the same colour. Thus there is no 3-colouring of R^2.

This is identical logic, phrased less formally, with (I believe) a proof by contradiction in it. Proof by contradiction is non-constructive, so I prefer to avoid it. I need to work on the wording of my constructive proofs.

hmm... the triangle bit doesn't really appear to prove anything. You're assuming that there is a triangle that has length sides L, L, 1 and all points are the same color.

This looks like a familiar proof, but you're missing a bunch of steps.

rwb
wbr
brw

Assume that in both of the two dimensions a color must shift one bit so that they are not adjacent.

Starting on row one, you go with red white blue
Row two is White Blue Red.
Row three is Blue Red White.

Similarly column one is Red white blue
Column two is White Blue Red.
Column three is Blue Red White.

The diagonals get you every time.

Kad

Actually, I think Laeyakk's proof is sufficient. I'm constructing an example using it but the actual numbers are a pain to work with. Let me see if I can dig up a program that'll make the number crunching part easier (and produce a picture that makes it clear how I'm constructing the points)...

the diagonals aren't the same distance as the vertical/horizals; the verticle/horizontal are 1, then the diagonal is sqrt(2).

Laek's proof is not sufficient; there's nothing inescapable about setting up the coloring the way he describes it.

I guess the only missing step is this:
Consider double triangles ABCD and AXYZ, where D and Z are 1 unit apart.

(will elaborate later)

Consider the points A=(0,0), B=(1,0), C=(1/2, sqrt(3)/2), D=(3/2, sqrt(3)/2). ABC and BCD form equilateral triangles with edges of length 1. The distance L between points A and D is
sqrt((3/2)^2 + (sqrt(3)/2)^2) = sqrt(3).

We want to find a double triangle AXYZ where Z is a distance of sqrt(3) units from A, and 1 unit from D. To find a suitable location for Z, we look for an intersection of the circle of radius sqrt(3) centered at A=(0,0):
x^2 + y^2 = 3
and a circle of radius 1 centered at D=(3/2, sqrt(3)/2):
(x - (3/2))^2 + (y - sqrt(3)/2)^2 = 1

There are two such intersections in R^2. Selecting one of them:
Z=((15 - sqrt(33))/12, (5 sqrt(3) + 3 sqrt(11))/12)
From this we can find the other two points X and Y:
X=((5-sqrt(33))/12, (5 sqrt(3) + sqrt(11))/12)
Y=(5/6, sqrt(11)/6)

If either ABCD or AXYZ contains a pair of points 1 unit apart with the same color, then we are finished.
Otherwise, A and D must have the same color, and A and Z must have the same color, which means D and Z have the same color. D and Z are 1 unit apart.

hmm... the triangle bit doesn't really appear to prove anything. You're assuming that there is a triangle that has length sides L, L, 1 and all points are the same color.

This looks like a familiar proof, but you're missing a bunch of steps.

Given my Corrollory:

Corrollory: Let L be the distance between A and D in a double triangle.

Either any two points in the plane of distance L apart have the same colour, or two points on the plane 1 distance apart share the same colour.

No other assumptions are required. You can say I didn't prove my corrollory sufficiently, but the rest of the proof is solid.

To make my proof more verbose, non-constructive, and generally worse:

First of all, I start from the position that that I have proven that any two points L distance apart are the same color in any 3-colored plane where all points 1 distance apart are not the same colour. If you disagree with my corrollory, I can write out a verbose arguement for it. I considered the double-triangle result to be trivial. See the appendix of this post for a proof of it.

Now that you have that statement, take any 3 points arranged in a triangle such that the triangle has sides L L and 1. (ABC, with AB = L BC = L and AC = 1)

Assume the plane has no points 1 distance apart that are the same colour. Here is the only assumption.

Thus, all points L distance apart are the same colour. (from the corrolory). This is not an assumption.

As A and B are L distance apart, the color of A must equal the colour of B.
As B and C are L distance apart, the color of B must equal the colour of C.

These are not assumptions. They follow from my corrollory and my assumption that we have a plane with the desired property (3-coloured, all points 1 distance apart are different colours).

Thus, the colour of A = colour of B = colour of C. (colour equality is transative, I hope!)

However, A and C are 1 distance apart, and the same colour. This contradictions the assumption above. So the thing I assumed must not be possible.

There does not exist a 3-coloured plane where all points 1 distance apart are different colours.

All of this proof-by-contradiction is irrelivent. My original proof is constructive, and I believe solid.

Appendix:
(this is the proof to the 'claim' and the demonstration that the corrollory follows from it).

Quick double-triangle proof.

Let ABCD be any 4 points arranged in a double-triangle as follows:

AB
CD
where AB = BD = CD = AC = BC = 1

I will use the colours Red Green and Blue.

Assume the plane has the property that no two points 1 distance apart have the same colour.

Without loss of generality, the colour of A can be assumed to be Red. (the same proof holds, with simple substitutions, if you assume A to be Green or Blue.)

Then B and C cannot be Red. They must be Blue or Green.

They cannot both be Blue nor can they both be Green. So one is Blue and the other is Green.

D is 1 distance from both B and C. So it is not the colour of B or C.

One of B and C is green and the other is blue. So D is not green and D is not blue. Thus D is the same color as A, red.

D is the same colour as A.

Now, let L = AD, the distance between A and D.

Then, for any two points A and D L distance apart, you can find points B and C such that ABCD forms the above mentioned double triangle. Thus, on any 3-coloured plane where points 1 distance apart are different colours, all points L distance apart are the same colour.
[]

Does this prove the corollory sufficiently?

And yes, you can build a graph on 7 points, where all adjacent nodes are 1 distance apart in R^2, such that it cannot be 3-coloured. My original proof was designed so that it tells you how to build that graph -- it's a constructive proof. =)

Consider the points A=(0,0), B=(1,0), C=(1/2, sqrt(3)/2), D=(3/2, sqrt(3)/2). ABC and BCD form equilateral triangles with edges of length 1. The distance L between points A and D is
sqrt((3/2)^2 + (sqrt(3)/2)^2) = sqrt(3).

We want to find a double triangle AXYZ where Z is a distance of sqrt(3) units from A, and 1 unit from D. To find a suitable location for Z, we look for an intersection of the circle of radius sqrt(3) centered at A=(0,0):
x^2 + y^2 = 3
and a circle of radius 1 centered at D=(3/2, sqrt(3)/2):
(x - (3/2))^2 + (y - sqrt(3)/2)^2 = 1

There are two such intersections in R^2. Selecting one of them:
Z=((15 - sqrt(33))/12, (5 sqrt(3) + 3 sqrt(11))/12)
From this we can find the other two points X and Y:
X=((5-sqrt(33))/12, (5 sqrt(3) + sqrt(11))/12)
Y=(5/6, sqrt(11)/6)

If either ABCD or AXYZ contains a pair of points 1 unit apart with the same color, then we are finished.
Otherwise, A and D must have the same color, and A and Z must have the same color, which means D and Z have the same color. D and Z are 1 unit apart.

Beautiful work, Palarran (that picture is worth a thousand words). I will find you in game with the 1k later if you are around.

Laeyakk, I will try to read your msg again later. Maybe I didn't understand it when I first read it.

Palarran = Master of all that is math, bow down minions! Now someone explain to me wtf you guys are talking about....wait, nm, i don't think i want to know.

Hey Laeyakk,

Just read your original proof again and it is indeed the same as what Palarran said. Since you got the answer first, I will look you up with the 1k then. Grats for the good work. And I agree that writing the argument is a huge pain. :D


Foreverlive.

Does that also prove that if you have 4 possible colors, the rule still applies (I mean there must be 2 identical colors withing 1 distance somewhere)?

Lani

Does that also prove that if you have 4 possible colors, the rule still applies (I mean there must be 2 identical colors withing 1 distance somewhere)?

Lani

This is not known to mathematics.

You can 7-colour R^2 (with unit adjacent points). You cannot 3-colour R^2 (with unit adjacent points). That is all that is known.

Laeyakk is the man. I have never doubted this. You should see some of his posts in the Enchanter boards... :eek: