Re: Ten points in a square
- From: quasi <quasi@xxxxxxxx>
- Date: Fri, 11 Apr 2008 19:43:13 -0500
On Fri, 11 Apr 2008 23:57:25 +0100, Angus Rodgers
<twirlip@xxxxxxxxxxx> wrote:
On Fri, 11 Apr 2008 18:34:10 -0500, quasi <quasi@xxxxxxxx> wrote:
On 11 Apr 2008 21:54:31 GMT, David W. Cantrell
<DWCantrell@xxxxxxxxxxx> wrote:
"Zdislav V. Kovarik" <kovarik@xxxxxxxxxxx> wrote:
It is a standard exercise on Pigeonhole Principle to prove:
If you place 10 distinct points in a square of side 1, then at least
two points will have distance no more than sqrt(2)/3 (about 0.4714).
My question: This number is an upper bound for the minimum
positive distance. Has anyone found the least upper bound?
(It is at least 1/3, just place the points at lattice points
with stepsize 1/3. With slightly more effort, one can replace
1/3 by sqrt(2)/(2*sqrt(2)+1), about 0.3694.)
By the way, tens of millions of pseudorandom experiments have
not exceeded 0.32.
It is 0.421..., which follows from the packing of ten unit circles, proven
optimal, shown at <http://www.stetson.edu/~efriedma/cirinsqu/>.
It's not clear to me that the 10 circle packing configuration answers
the OP's question.
It's clear to me that it doesn't. Wow, such confidence, for
once! So I must be wrong ... and indeed I am! See below. :-)
There's no requirement for the placed points to be any given distance
away from the boundary of the square.
Letting x be the answer to the OP's question, then, as far as I can
see, the 10 circle packing configuration gives a _lower_ bound on x.
In other words, what we now know is
0.421... <= x <= sqrt(2)/3
Unless I'm missing something.
I don't think so.
But it might be possible to deduce an answer. Let the radii of the
circles in that configuration be r, so that the required bound is 2r.
Then it looks as if the centres occupy a square of side 1 - 2r, so,
if the figure is magnified by the inverse of this, it would seem
that the 10 centres fit into a square of unit side when the radii
are r/(1 - 2r), so the separation is 2r/(1 - 2r).
If I understand the diagram correctly, r = 1/(6.747+), so 2r/(1 - 2r)
= 1/(1 - 2r) - 1 = .4213+ ... which is obviously (with hindsight!)
just what David meant in the first place. D'oh!
But it still doesn't prove that .4213 ... is an upper bound since,
while every packing configuration induces a 10-point configuration,
the converse is not obvious, and possibly not true.
Thus, all you have is a _lower_ bound on x.
Hence, bolstered by your analysis, I stand (for now) by my earlier
claim that what David's argument (and your amplification) actually
proves is .4213 ... <= x. Thus, all we know, based on the information
so far in this thread, is that
.4213 ... <= x <= sqrt(2)/3
Unless I'm missing something.
quasi
.
- References:
- Ten points in a square
- From: Zdislav V. Kovarik
- Re: Ten points in a square
- From: David W . Cantrell
- Re: Ten points in a square
- From: quasi
- Re: Ten points in a square
- From: Angus Rodgers
- Ten points in a square
- Prev by Date: Re: Ten points in a square
- Next by Date: china wholesale nike shox r3 r4 oz nz tl turob energia shoes cheap lacoste T-shirts
- Previous by thread: Re: Ten points in a square
- Next by thread: Re: Ten points in a square
- Index(es):
Relevant Pages
|
