Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: cotpi 69 - Black and white plane
Replies: 26   Last Post: Oct 9, 2013 10:23 AM

 Messages: [ Previous | Next ]
 David Bernier Posts: 3,892 Registered: 12/13/04
Re: cotpi 69 - Black and white plane
Posted: Oct 6, 2013 6:28 AM

On 10/06/2013 05:52 AM, David Bernier wrote:
> On 10/02/2013 10:29 PM, Mike Terry wrote:
>> "quasi" <quasi@null.set> wrote in message
>> news:v9vo49lvr7j4ns7i82s869ou749lgdmrup@4ax.com...

>>> Pubkeybreaker wrote:
>>>> Susam Pal wrote:
>>>>>
>>>>> How can you construct a plane where every point is coloured
>>>>> either black or white such that two points of the same colour
>>>>> are never a unit distance apart?
>>>>>
>>>>> -- Originally posted at:
>>>>> http://cotpi.com/p/69/
>>>>> Puzzles IRC channel:
>>>>> ##puzzles on irc.freenode.net
>>>>> Puzzles IRC webchat:
>>>>> http://webchat.freenode.net/?channels=##puzzles

>>>>
>>>> It does not seem possible. Take any point. Suppose it is
>>>> white. It is the center of a circle (of radius 1). All points
>>>> on that circle must then be black. But given any point on
>>>> that circle there is another point on the circle at distance 1.
>>>> Both points are the same color.
>>>>
>>>> Unless, of course, I am being completely stupid.

>>>
>>> No, your proof is fine.
>>>
>>> quasi

>>
>> The question was asked here a few years ago whether the plane can be
>> coloured along the lines above but using three colours. The answer is no,
>> and the proof is similar but less obvious...

> [...]
>
> There is a web-page called "Chromatic Number of the Plane" by
> Alexander Bogomolny that briefly discusses the question of
> the minimum number of colours needed.
>
> The relevant definition, copied from there, is:
> ``The smallest number of colors needed in a coloring of the plane to
> ensure that no monochromatic pair is at the unit distance apart is
> called the chromatic number Chi of the plane."
>
> Ref.:
> < http://www.cut-the-knot.org/proofs/ChromaticNumber.shtml > .
>
> Two or three colours won't do, from which we see that Chi >= 4.
> A 7-colouring of a regular-hexagon tiling of the plane shows
> that seven colours will do, from which we see that Chi <= 7.
>
> Considering every point in the plane as the vertex of an
> infinite graph, then one can imagine drawing an edge between
> any pair of points exactly one-unit distance apart.
>
> If we call 'G' the infinite graph we get, then the (standard)
> graph-colouring question, about colouring the vertices of 'G'
> etc. etc. is equivalent to the question what is the value of
> Chi?
>
> Indeed, the Wikipedia article on graph colouring says:
> "When used without any qualification, a coloring of a graph is almost
> always a proper vertex coloring, [...]
>
> Ref.:
> < http://en.wikipedia.org/wiki/Graph_coloring >
>
> Then there's a theorem known as the De Bruijn?Erd?s theorem :
> <
> http://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem_%28graph_theory%29

>>
>
> It implies that: 'G' as above can be coloured with 'k' colours if and
> only if every finite subgraph of 'G' can be coloured with 'k' colours.
>
> The parameter 'k' can be any positive integer.
>
> So, maybe we _cannot_ colour 'G' with just 4 colours .... [thought
> experiment, etc.]
>
> The Chi question, according to the Wikipedia article above, is
> also known as the Hadwiger?Nelson problem :
>
>
> The "Moser spindle" unit-distance graph shows that Chi >=4 :
> < http://en.wikipedia.org/wiki/Moser_spindle >
>
> There are only 7 vertices, so it's easy to describe:
>
> Let A be a point in the plane at (0, 0).
> Let B be the point (1,0).
> Let C be the point in Quadrant I which is at unit distance
> from both A and B. So C has coordinates: (cos pi/3, sin pi/3).
>
> A is one of the two points which are at unit distance from
> both B and C. Let us call the second point D.
>
> Let E be an as yet undetermined point on the circle of
> radius 1 centered at A.
>
> Let F be determined, relative to A and E, by requiring
> that the unit-segment AF is obtained by rotating the
> unit-segment AE through pi/3 [60 degrees] counter-clockwise.
>
> Then, E and F shall be one unit distance apart.
>
> A is one of the two points at unit distance from both E and
> F. Let G be the second point at unit distance from both E and
> F.
>
> We have the unit-sided equilateral triangles: ABC, BCD,
> AEF, EFG.
>
> Like ("suggested") in the figure in the top right box at:
> http://en.wikipedia.org/wiki/Moser_spindle ,
>
> with A being the highest point in the figure,
> points D and G are the furthest from A,
> and also the lowest in the drawing.
>
> The points called B, C, E, F are all at unit distance
> from A .
>
> Then we require finally that D and G be a unit distance apart.
> Then the line segments AD and AG have the same length.
> We can fix G down to unique by asking that there be a
> counter-clockwise rotation through A of less than 180 degrees
> that maps segment AD to segment AG.
>
> With a three-colouring, considering in turn
> {A, B, C, D} and {A, E, F, G},
> one is forced to colour D the colour of A, and also
> forced to colour G the colour of A. So D and G, although
> unit distance apart, share the same colour (X).
>
> So the Moser spindle needs at least 4 colors.
>
> The Moser spindle is related by Wikipidia to be a Laman graph,
> which have a type of rigidity property:
> < http://en.wikipedia.org/wiki/Laman_graph > .
>
> After some thinking, I realized that the Moser spindle, as a rigid
> figure in the plane consisting of 4 equilateral triangles of
> unit length and 7 distinct vertices, is constructible by
> ruler and compass ...
>
> Also, I tried that out experimentally.
>
> The wikipedia article on ruler and compass,
> < http://en.wikipedia.org/wiki/Compass-and-straightedge_construction >
>
> says that:
> ``It is possible (according to the Mohr?Mascheroni theorem) to construct
> anything with just a compass if it can be constructed with a ruler and
> compass, provided that the given data and the data to be found consist
> of discrete points (not lines or circles)."
>
> In the Moser spindle case, if we suppose A = (0, 0) and
> B = (1, 0) as the starting point,
> then it's easy to construct C by compass.
>
> Also, constructing D by compass is easy. Then G seems
> easy also, which leaves E and F.
>
> So, I thought of writing a computer program to devise pseudo-random
> compass-only constrcutions of finite number of points, with an aim
> of getting "lots" of pairs of points at unit distance from each other.
>
> One can think of two sub-problems of the Chromatic Number of the Plane
> problem:
>
> (a) Finding a finite set of points in the plane for which at least 5
> colors are required (thus giving a configuration where 4 colours
> are not enough) , and
>
> (b) devising a 6-colouring of the plane .
>
> I thought Erdos had said something about what he thought was more
> probable (4, 5, 6, 7), but I can't find it.

Got it.

Ilan Vardi wrote in sci.math:

<<
Here is a pretty good list of references for the chromatic number of
the plane
[snip]

[6] P. Erd\"os, ``Problems and Results in Combinatorial Geometry,''
in ``Discrete Geometry and Convexity,'' Edited by Jacob E. Goodman,
Erwin Lutwak, Joseph Malkevitch, and Richard Pollack, Annals of
the New York Academy of Sciences Vol. 440, New York Academy of
Sciences 1985, Pages 1-11.

States that 3<chi(n)<8 and ``I am almost sure that chi(2)>4.''
States a question of L. Moser: Let R be large and S a measurable
[snip]
>>

Source:
< http://www.ics.uci.edu/~eppstein/junkyard/plane-color.html > .

And a scan of Erdos's paper:

< www.renyi.hu/~p_erdos/1985-23.pdf >

where Erdos writes:
<<
Hadwiger and Nelson posed the following problem:
[snip]

It is known that 4 <= h(2) <= 7. I am almost sure that h(2)>4.
[snip]
>>

David Bernier

--
Let us all be paranoid. More so than no such agence, Bolon Yokte K'uh
willing.

Date Subject Author
10/2/13 cotpi
10/2/13 Pubkeybreaker
10/2/13 quasi
10/2/13 Mike Terry
10/6/13 David Bernier
10/6/13 David Bernier
10/6/13 David Bernier
10/6/13 David Bernier
10/6/13 David Bernier
10/6/13 quasi
10/6/13 quasi
10/6/13 David Bernier
10/6/13 David Bernier
10/6/13 quasi
10/6/13 David Bernier
10/9/13 Phil Carmody
10/9/13 David Bernier
10/2/13 Eric Lafontaine
10/2/13 Michael F. Stemper
10/2/13 quasi
10/2/13 quasi
10/2/13 Haran Pilpel
10/2/13 quasi
10/2/13 quasi
10/2/13 Ted Schuerzinger