Author |
Topic: Separating points with lines (Read 1296 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
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]
|
| « Last Edit: Jul 21st, 2004, 2:42pm by Aryabhatta » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
 |
Re: Separating points with lines
« Reply #1 on: Jul 21st, 2004, 3:07pm » |
 Quote  Modify
|
::
lowerbound for 1) is ceil(log2(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(log2(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)
::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Separating points with lines
« Reply #2 on: Jul 21st, 2004, 3:33pm » |
Quote Modify
|
Consider the convex hull of the 7 dots. It is a "heptagon".
There is no way to cross all 7 sides with 3 lines.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print