wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> 7 points in a plane
        
(Message started by: thedkl on Mar 13^th, 2007, 4:46am)

Title: 7 points in a plane
Post by thedkl on Mar 13^th, 2007, 4:46am

draw 7 points on a 2d plane such that for every 3 of them there is a pair of a 1 unit distance

Title: Re: 7 points in a plane
Post by towr on Mar 13^th, 2007, 5:49am

I half suspect there isn't a solution.

Title: Re: 7 points in a plane
Post by Grimbal on Mar 13^th, 2007, 7:14am

I also half suspect. Does it make it certain? ;)

Title: Re: 7 points in a plane
Post by towr on Mar 13^th, 2007, 7:49am

I just found a solution.

[hide]Say a connects to b,c,d,e; b and c connect to f; d and e to g; and f and g are connected. [edit]Also b connect to c, and d connects to e.[/edit] (Where a connection means there's a distance of 1 between them)[/hide]

There may be more solutions, but this was enough work.

Title: Re: 7 points in a plane
Post by Grimbal on Mar 13^th, 2007, 7:57am

Damn, you are right. Congratulations!

Note that I haven't changed my mind ... I still think you are right. ::)

Title: Re: 7 points in a plane
Post by rmsgrey on Mar 13^th, 2007, 8:33am

on 03/13/07 at 07:49:17, towr wrote:

I just found a solution.

[hide]Say a connects to b,c,d,e; b and c connect to f; d and e to g; and f and g are connected. (Where a connection means there's a distance of 1 between them)[/hide]

There may be more solutions, but this was enough work.

d,e,f?
b,c,g?
Any three of b,c,d,e?

Title: Re: 7 points in a plane
Post by SMQ on Mar 13^th, 2007, 8:35am

I came up with the same solution (all colored links are unit length):

http://www.dwarfrune.com/~smq/wu/7points.gif

--SMQ

Title: Re: 7 points in a plane
Post by rmsgrey on Mar 13^th, 2007, 8:50am

Ah, the solution was incompletely specified...

There's (at least one) configuration that has only the links towr mentioned unit length, and not the additional pair of links...

Title: Re: 7 points in a plane
Post by SMQ on Mar 13^th, 2007, 8:51am

on 03/13/07 at 08:33:47, rmsgrey wrote:

d,e,f?
b,c,g?
Any three of b,c,d,e?

Are you interpreting tha problem statement the same way as the rest of us? I read it as: plot 7 points in a plane such that for any three chosen points, at least one pair of points is exactly a unit distance apart.

Edit: Ah, I see, towr forgot to mention the b-c and d-e links...

--SMQ

Title: Re: 7 points in a plane
Post by towr on Mar 13^th, 2007, 9:38am

on 03/13/07 at 08:51:51, SMQ wrote:

Edit: Ah, I see, towr forgot to mention the b-c and d-e links...

Indeed. I'll go edit them in..

Are there other solutions? I had some 1100 possible solutions left, when I tried a random one to see if it was an actual solution.

Title: Re: 7 points in a plane
Post by Eigenray on Mar 13^th, 2007, 2:27pm

This graph is called the Moser spindle; it cannot be 3-colored, and so it is impossible to color the points of R² with 3 colors such that no two points a unit distance apart are the same color. It can, however, be done with 7 colors, so the [link=http://en.wikipedia.org/wiki/The_chromatic_number_of_the_plane]chromatic number of the plane[/link] is somewhere between 4 and 7, inclusive. (Even though these bounds are easy to prove, they are still the best known after more than 50 years!)

Title: Re: 7 points in a plane
Post by Altamira_64 on Apr 12^th, 2017, 6:31am

How about 8 points? Is there a solution?