wu :: forums - Print Page


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

        riddles >> medium >> Separating points with lines 
        
(Message started by: Aryabhatta on Jul 21^st, 2004, 2:38pm)

Title: Separating points with lines
Post by Aryabhatta on Jul 21^st, 2004, 2:38pm

You have a square and 9 points in the square arranged like a grid. (See Attachment)

1) What is the minimum number of straight lines that must be drawn so that each of the 9 points is in a region of its own?
(i.e if you pick any two points A, B from the 9 points, the line segment AB should intersect at least one of the lines you have drawn)

2) What is the minimum number in the second case? (See Attachment)

[EDIT]

To be clear: 8 points lie on a smaller square and the ninth point is the center of that square. The 8 points are the vertices of the smaller square and the midpoints of the sides.

For part 2) The figure is same as part 1) except the bottom right and the center points have been removed.

The figure does not look like it, but gives you the picture.

[EDIT]

Title: Re: Separating points with lines
Post by towr on Jul 21^st, 2004, 3:07pm

::[hide]
lowerbound for 1) is ceil(log₂(9)) = 4
and it's easy to see 4 lines is enough, so it's the minimum
o|o|o
-+-+-
o|o|o
-+-+-
o|o|o

lowerbound for 2) is ceil(log₂(7)) = 3
But I don't yet see how to arrange 3 lines to accomplish the task.. (It isn't necessarily possible, if the points were all on one line I'd get the same expression as above for the lowerbound, but obviously 6 lines would be needed)

[/hide]::

Title: Re: Separating points with lines
Post by Leonid Broukhis on Jul 21^st, 2004, 3:33pm

Consider the convex hull of the 7 dots. It is a "heptagon".
There is no way to cross all 7 sides with 3 lines.