Painting the plane

[Jimmy Snyder]

To each point of the Euclidean plane a color is assigned, some are red, the rest blue. Without knowing how the assignment was made, show that for each number A greater than zero, there is a pair of points whose distance apart is A and both of which have been assigned the same color.

[<<<GUILLE>>>]

of what I have understood, this is my answer:

Each let's say A=red. and the other points is B=blue. then, for each A point there are 2 B points, which means that there are, for example, three lines of points: line 1, 2 and 3. line 1 has B points only. line 2 has A points only. line 3 has B points only.

[Jimmy Snyder]

No, GUILLE, A is a distance, not a color. The painting is arbitrary and may or may not have two blues for each red, or lines that are all one color.

[BicycleTree]

Pick any equilateral triangle BCD with sides of length A. Now, zero, one, two, or three of the points B, C, D are red. If zero are red, then all are blue and any two corners of the triangle satisfy the condition (because they are A apart). If three are red, again any two corners satisfy the condition. If two are red, they are A apart so they satisfy the condition. If one is red, two are blue, and these two satisfy the condition.

[Jimmy Snyder]

Very good BicycleTree.

Oops, did I say two colors? I meant three. Each point is associated with one of the three colors red, green, or blue. Now show that for each number A greater than zero, there is a pair of points whose distance apart is A and both of which have been assigned the same color.

[BicycleTree]

Pick an equilateral triangle BCD and a different equilateral triangle BCE, both with sides of length A. If D and E are different colors then clearly B and C are the same color, so assume D and E are the same color (say wlog blue), and assume that there do not exist any two points of the same color separated by A.

Now pick a point a distance of A from D, and a distance of A * sqrt(3) away from E. (there are only two such points) Call this point P, and call the two points that are A from P and E, points Q and R (Q and R are A from each other and each is A from E and P). Now by assumption, since P is A from D, P is not blue; wlog say P is red. So Q and R are green, since each is A from both P, a red point, and E, a blue point. But since Q and R are A apart, this contradicts the assumption that there do not exist points A apart that have the same color.

[Jimmy Snyder]

Correct again BicycleTree (although there is a simpler proof)

Show that using 9 colors you can paint the points of the plane in such a way that there is a positive number A for which no pair of points is distance A apart and painted the same color.

[BicycleTree]

I originally did answer the last one but I've already gotten 2 from this thread so I'll leave the answer for someone else this time.

[BicycleTree]

You know, I've been thinking and thinking but I don't see any simpler proof of the second question than the one I used.

[Jimmy Snyder]

The proof below is similar to yours except that I use lower case letters for points, and upper case for distances. Also, I have pointed out where the simplification lies.

By the first paragraph of your proof any two points whose distance apart is B = A * sqrt (3) are the same color. A triangle with two sides of length B and one side of length A (the same as your triangle dep) has all three points the same color and two of them distance A apart. (there is no need to consider points q and r and that is the simplification.)

[BicycleTree]

OK--the same general idea.

So how far does this go? Is there a proof that the condition holds for 6 colors?

[TenaliRaman]

I am not exactly aware of any proofs, but its known that the chromatic number of a plane is between 4 and 7. However the given problem is more relaxed than the chromatic number problem. So i believe its possible to show for 6 colors.

Ofcourse i say this with my tongue in cheek.

-- AI

[Jimmy Snyder]

So how far does this go? Is there a proof that the condition holds for 6 colors?

I'm afraid you are getting ahead of me. I haven't seen a solution to the 9 color problem yet.

[BicycleTree]

Well, nobody else seems to be answering so I will say my answers to the 9 and 7 color problems.

For 9 colors, use a rectangular grid so that each square is surrounded by 8 squares of different colors.

For 7 colors, use a regular hexagonal grid so that each hexagon is surrounded by 6 hexagons of different colors.

[Jimmy Snyder]

I'm sorry BicycleTree, but I cannot accept this answer for several reasons. Set aside for the time being, the seven color problem and lets concentrate on the 9 color problem.

1. You give no description of the dimensions of the rectangular (It seems you mean specifically square) grid.

2. You have not demonstrated that such a grid is possible. For instance, it is easy to see that a grid of 9 squares could be colored in the way you suggest so that the central square is surrounded by 8 squares of different colors. However, you need to show that the entire plane can be tesselated in such a way that EVERY square in the plane is surrounded by 8 squares of different colors.

3. You need to show how such a grid would satisfy the requirement of the puzzle.

[BicycleTree]

Well, since the 9 color is satisfied by the hexagonal grid as well as by the rectangular grid, I'll just answer for the hexagonal grid. Color it this way:
Place a hexagon of color 1.
Place hexagons of colors 2-7 around the first hexagon.
Tile the resulting shape as demonstrated here:
http://img235.echo.cx/my.php?image=hexgrid24xd.png
Vertexes represent hexagons. The red-boxed hexagon is the starting hexagon. It can be seen that every color in a tiled block of 7 colors in the middle of the grid is surrounded by the 6 other colors, therefore if the tiling--each tile is 7 hexagonal blocks as boxed in indigo--is continued infinitely this will also be the case.
This satisfies the condition because if the hexagons are regular and A is just longer than a diagonal of the hexagon, then the two points at the endpoints of the segment of length A must land in two hexagons that are either neighbors or have 1 hexagon between them. Because of the tiling, this ensures that the endpoints are always of different colors (it is easily seen from the grid, and presumably easily proven, that hexagons of the same color always have at least 2 other hexagons between them).

Actually, there probably is a way to color the plane using 4 colors so that there is a length where every pair of points that length apart are different colors. This follows from the four-color theorem, since a length A in the plane defines a graph, and every graph can be colored with 4 colors so that you have no vertices with adjacent colors. Of course this is not a certain argument, because the length defines an infinitely fine graph.

[Jimmy Snyder]

Very good BicycleTree,

As far as I know, the situation for 4, 5, and 6 is unsolved. But my information is about 30 years old. Perhaps progress has been made.

[BicycleTree]

One thing to add: the plane + the length A must be a planar graph because it is impossible to construct either of the graphs that Kuratowski's theorem demands using only straight edges of a single length:
http://www.math.lsa.umich.edu/mmss/coursesONLINE/graph/graph5/