- #1
shybishie
- 7
- 0
Place 6 points in the plane, such that ratio of maximum distance / minimum distance (over these points) is as small as possible. The question is - what is the smallest ratio possible, and can we prove this is a tight bound? The following is my attempt for 6 (and fewer points):
1) For three points, we can clearly achieve max dist / min dist = 1 (equilateral triangle)
2) For four points, I tried 2 configurations - a point inside a triangle (couldn't do better than [tex]\sqrt{3}[/tex] doing that though, using an equilateral triangle and it's centroid) . Also, I got a better result with a square (I got [tex]\sqrt{2}[/tex] , with the maximum length side being the diagonal). I think that should be improvable though?
3) For five points, the best I got was with a regular pentagon (about 1.62).
4) For six points, a regular hexagon was NOT the best distribution - that gave a ratio of 2 between largest and smallest distance. The best I got was a regular pentagon, with the sixth point at it's intersection of angle bisectors - about a ratio of 1.9. Any way to improve this, and (more trickily) prove it's tight? My source says [tex]\sqrt{3}[/tex] is the tight bound?
I guess where I'm most stuck is proving a lower bound; i.e, you can't do better than x - I'm not sure how to get started there, even for the n = 4 case. If anyone has ideas or strategies, I'd really appreciate.
P.S: This isn't a homework or coursework problem - just a random puzzle from Rutgers problem solving seminar website.
1) For three points, we can clearly achieve max dist / min dist = 1 (equilateral triangle)
2) For four points, I tried 2 configurations - a point inside a triangle (couldn't do better than [tex]\sqrt{3}[/tex] doing that though, using an equilateral triangle and it's centroid) . Also, I got a better result with a square (I got [tex]\sqrt{2}[/tex] , with the maximum length side being the diagonal). I think that should be improvable though?
3) For five points, the best I got was with a regular pentagon (about 1.62).
4) For six points, a regular hexagon was NOT the best distribution - that gave a ratio of 2 between largest and smallest distance. The best I got was a regular pentagon, with the sixth point at it's intersection of angle bisectors - about a ratio of 1.9. Any way to improve this, and (more trickily) prove it's tight? My source says [tex]\sqrt{3}[/tex] is the tight bound?
I guess where I'm most stuck is proving a lower bound; i.e, you can't do better than x - I'm not sure how to get started there, even for the n = 4 case. If anyone has ideas or strategies, I'd really appreciate.
P.S: This isn't a homework or coursework problem - just a random puzzle from Rutgers problem solving seminar website.
Last edited: