Author |
Topic: 10 Points in a Square (Read 472 times) |
|
FiBsTeR
Senior Riddler
Gender: 
Posts: 581
|
 |
10 Points in a Square
« on: Jun 14th, 2008, 6:44pm » |
 Quote  Modify
|
10 points are placed in or on a square of side length 4. Find the least upper bound on the smallest distance between any two of these points.
(Source: AoPS)
My current upper bound is 1.66525..., though I have no idea if I'm anywhere near the answer. Any thoughts?
|
| « Last Edit: Jun 14th, 2008, 6:46pm by FiBsTeR » |
 IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 10 Points in a Square
« Reply #1 on: Jun 14th, 2008, 11:32pm » |
Quote Modify
|
It is approximately 1.6851181759356137310752870426..., or 4 times the smallest positive root of
1180129x^18 - 11436428x^17 + 98015844x^16 - 462103584x^15 + 1145811528x^14 - 1398966480x^13 + 227573920x^12 + 1526909568x^11 - 1038261808x^10 - 2960321792x^9 + 7803109440x^8 - 9722063488x^7 + 7918461504x^6 - 4564076288x^5 + 1899131648x^4 - 563649536x^3 + 114038784x^2 - 14172160x + 819200.
No, I didn't just come up with that. Up through 9 points were known by 1964. The optimal pattern for 10 points was found by Schluter in 1971, but not proved optimal until 1990 by de Groot, Peikert, and Wurtz. See:
C. de Groot, M. Monagan, R. Peikert, and D.Wurtz, Packing circles in a square: a review and new results, in P. Kall (ed.), System Modelling and Optimization (Proc. 15th IFIP Conf., Zurich, 1991), pp. 45–54,
Lecture Notes in Control and Information Sciences, Vol. 180, Springer-Verlag, Berlin, 1992.
This has optimal solutions for up through 20 points, and several references. With the exception of n<10, n=14,16,25,36, all optimality proofs have been by computer.
Edit: actually the paper is freely available here.
See here for up to 50 points. Note the patterns for n=1,4,9,16,25,36, but not 49!
|
| « Last Edit: Jun 14th, 2008, 11:56pm by Eigenray » |
IP Logged |
|
|
|
FiBsTeR
Senior Riddler
Gender:
Posts: 581
|
|
Re: 10 Points in a Square
« Reply #2 on: Jun 15th, 2008, 6:19am » |
Quote Modify
|
Thank you, Eigenray! It's just like those middle schoolers to post problems they don't have solutions to. 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print