wu :: forums - Print Page


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

        riddles >> medium >> 10 Points in a Square
        
(Message started by: FiBsTeR on Jun 14^th, 2008, 6:44pm)

Title: 10 Points in a Square
Post by FiBsTeR on Jun 14^th, 2008, 6:44pm

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?

Title: Re: 10 Points in a Square
Post by Eigenray on Jun 14^th, 2008, 11:32pm

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 [link=http://graphics.ethz.ch/~peikert/papers/ifip.pdf]here[/link].
See [link=http://www.mathematik.uni-bielefeld.de/~sillke/BIB/square-circle-packings1.ps]here[/link] for up to 50 points. Note the patterns for n=1,4,9,16,25,36, but not 49!

Title: Re: 10 Points in a Square
Post by FiBsTeR on Jun 15^th, 2008, 6:19am

Thank you, Eigenray! It's just like those middle schoolers to post problems they don't have solutions to. :P