Search All of the Math Forum:

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

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

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

On 10/06/2013 09:19 AM, David Bernier wrote:
> On 10/06/2013 08:15 AM, David Bernier wrote:
>> 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 :
>>>
>>>
>>> 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.

> [...]
>
> With 7 points and 2 real variables per point, we have
> 14 real variables and 11 equations. The Moser spindle
> has 3 degrees of freedom, with centroid counting for 2
> and the orientation counting for 1.
>
> So, with 50 points, we have 100 real variables
> so it might be typically 100-3 = 97 "distance 1" constraints.
> I wonder if this is easy or hard, as a decision problem ...

Suppose we are looking for finite plane point-configurations
that must use at least 4 colours. Suppose Q is such as
configuration.

If Z is a point in the configuration Q, and Z has
two or fewer points in Q at unit-distance from Z,
then it seems to me harmless to delete the Point Z
from the configuration, meaning that
Q less Z would still need at least 4 colours.

But is it really true? and if so, how could one
prove it?

Indeed, in the Moser spindle, with the seven points, we have
in some order: 4, 3, 3, 3, 3, 3, 3
points at unit-distance [from A, B, C, D, E, F and G, respectively].
So always at least 3 points at distance 1 from some given point,
in the case of the Moser spindle at least.

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