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

 Search Thread: Advanced Search

 Messages: [ Previous | Next ]
 David Bernier Posts: 3,892 Registered: 12/13/04
Re: cotpi 69 - Black and white plane
Posted: Oct 6, 2013 8:15 AM
 Plain Text Reply
 signature.asc (0.5 K)

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?

[snip]
>>>> 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.

[snip]

> The Chi question, according to the Wikipedia article above, is
> also known as the Hadwiger?Nelson problem :
>
> < http://en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_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.

[snip]

(aside: Erdos wrote that he was almost sure that Chi > 4, for
the plane).

I thought of a decision problem, related to "random graphs"
with many pairs of points at unit distance from each other.

Suppose I have a 50x50 matrix T with entries in {0, 1}.
It's a given that T is symmetric, meaning T = T^t, and
that the main diagonal of T is all zeros.

===

The decision problem for T is this:

Do there exist 50 distinct points (x_1, y_1) ... (x_50, y_50) in
R^2 such that

T_{i, j} = 1 if and only if : (x_i - x_j)^2 + (y_i - y_j)^2 =1,
valid for 1 <= i <= 50 and for 1 <= j <= 50 ?

With '7' taking the place of '50' in a natural way,

T is a 7x7 symmentic matrix with 0/1 entries, for example:

T :=
[0 1 1 0 1 1 0]
[1 0 1 1 0 0 0]
[1 1 0 1 0 0 0]
[0 1 1 0 0 0 1]
[1 0 0 0 0 1 1]
[1 0 0 0 1 0 1]
[0 0 0 1 1 1 0]

So, do there exist 7 distinct points (x_1, y_1), (x_2, y_2), (x_3, y_3),
(x_4, y_4), (x_5, y_5), (x_6, y_6) and (x_7, y_7)
in R^2 such that:

for 1<= i, j <=7 : (x_i - x_j)^2 + (y_i - y_j)^2 = 1 if and only if
T_{i, j} = 1 ?

===

I constrcuted the 7x7 matrix T based on the Moser spindle (that is,
taking as points the vertices in the Moser spindle).

So, unless my T is mistaken, the decision problem for the 7x7 matrix
T above is that "Yes, it's doable".

I note that all that can be "gleaned" from T_{i, j} being zero
is that (x_i, y_i) and (x_j, y_j) _cannot_ be a distance 1 apart,
which seems quite weak as a constraint ...

In the context of searching for figures needing at least 4 colours
(maybe at least 5 later on), one could change the off-diagonal
'0's for just *, meaning "either 0 or 1".

Then, the new T, T2 is:

T2 :=
[0 1 1 * 1 1 *]
[1 0 1 1 * * *]
[1 1 0 1 * * *]
[* 1 1 0 * * 1]
[1 * * * 0 1 1]
[1 * * * 1 0 1]
[* * * 1 1 1 0]

I believe there are 11 basic "distance 1" constraints above, at
one per pair of unit-distance points.

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
10/2/13 Mark Brader
10/3/13 William Elliot

© The Math Forum at NCTM 1994-2018. All Rights Reserved.