[superprismatic]

If 51 points are placed inside a square of

side length 1, what is the diameter of the

smallest circle which is guaranteed to be

able to encircle at least three of these

points, if properly placed? For purposes

of this problem, points on the boundary

of a figure are considered to be inside.

[curr3nt]

Started out trying to place the points as far away from each other as possible. At 5 points I had a point at each corner and one in the center.

next 4 points in the middle of the edges of the square

next 4 points in the middle of the 4 quadrants and so on

at 41 points I had a grid of 25 points with a grid of 16 points inside it. This would give a circle with the diameter of 1/4

The next 10 points to get to 51 would be placed in positions that would make a circle with a diameter of the square root of 1/32

[Guest]

(85/1764)^(1/2) ... about = 0.22

If you use an 8 by 7 array of points (5 spots will be sans-point) you would need a circle of this diameter. You could actually capture 4 points, but I don't think there is a way to capture 3 with a circle any smaller. I believe this is the most spread point distribution.

[curr3nt]

Pigeonhole Principle says (2/25)^(1/2) but I can't see how to place the third dot into one of the 25 boxes without there being a smaller circle elsewhere.

Edited January 14, 2011 by curr3nt

[Guest]

7x7=49, 1/6 is the answer if there are 50 points, dont see how 51th point can change the answer, will see how to spread 50 pts throughout the square. even if it changes, the answer will be VERY close to 1/6

[superprismatic]

iverson2002939's answer of 1/6 (or 2/(7*sqrt(3)) more accurately) is the best so far. I don't have any better. Does anyone else?

[superprismatic]

Boy! I must have been tired when I wrote that!

The only response that gives a reasonable answer

to the OP is #4 by curr3nt. He gives an upper

bound of (√2)/5 which the pigeonhole principle

gives by dividing the square into a 5 by 5 grid.

iverson2002939's response lassos 2 points (not

the required 3). It must be shown that the

circle works for any way of placing 51 points

in the square. If you claim to have a worse

case placement of points, you have to prove that

fact.

Anyway, as it now stands, (√2)/5 is the best

answer. Yet, it is but an upper bound on the

diameter of the smallest circle which will work.

Sorry, for my stupid post #6.

iverson2002939's answer of 1/6 (or 2/(7*sqrt(3)) more accurately) is the best so far. I don't have any better. Does anyone else?

[Guest]

I think curr3nt has it right with the Pigeonhole principle (Thanks...I used that type of distribution but didn't have the name for the concept), but he even points out that he couldn't place the last point in a 5x5 grid. With a 5x5 grid you place 2 points at each "hole" for 50 total with a minimum circle diameter of 1/4 (not(√2)/5 or 1/6 as previously posted) capturing 4 points. But again, this is only 50.

But adding that 51st "pigeon" on the 5x5 grid either puts 3 at a single point (making the smallest diameter circle become 0), or a point at the center of a square made by four of the 2-point stacks (making the circle min diameter (√2)/10). If I'm the guy laying out the points that you have to lasso, I will feel quite good about you picking a circle this small, because I can certainly pick a wider distribution of points.

Staying with the stacked point concept:

Expanding to a 5x6 grid (dividing the 1 unit side length by the respective number of points per side) will net the widest distribution of 51 points, some being stacked. By putting 2 points per gridpoint for any 21 gridpoints, and the remaining 9 gridpoint with 1 point a piece (or you could put 2 points at up to 25 gridpoints leaving 1 point and 4 empty gridpoints), you will have a location where a 1/6 diameter circle guarantees 3 points encircled, thus beating (√2)/10 as the upper bound for an array where stacking points is considered.

Now going to individual points (no stacking):

The points get closer together but you have to encircle a larger area. Using a 7x8 grid you will have several rectangles 1/6 x 1/7 whose corners are made by four points. The only way to capture 3 points is to have a circle equal to the diagonal of this rectangle, thus my before mentioned answer of (85/1764)^(1/2) = 0.21951... is the smallest diameter to assure 3 points.

Superprismatic: (√2)/5 is greater, yes, but I don't see a layout that requires a circle this big. Please let me know if I am missing something.

Boy! I must have been tired when I wrote that!

The only response that gives a reasonable answer

to the OP is #4 by curr3nt. He gives an upper

bound of (√2)/5 which the pigeonhole principle

gives by dividing the square into a 5 by 5 grid.

iverson2002939's response lassos 2 points (not

the required 3). It must be shown that the

circle works for any way of placing 51 points

in the square. If you claim to have a worse

case placement of points, you have to prove that

fact.

Anyway, as it now stands, (√2)/5 is the best

answer. Yet, it is but an upper bound on the

diameter of the smallest circle which will work.

Sorry, for my stupid post #6.

Edited January 17, 2011 by Copernicus

[superprismatic]

First, let me explain the 5 by 5 pigeonhole argument.

We place a 5 by 5 grid over the square which contains

an arbitrary pattern of 51 points. By the pigeonhole

principle, there must be at least one 1/5 by 1/5 square

which contains at least 3 points somewhere in it. This

is true because, if we assume it is not true, then each

of those 1/5 by 1/5 boxes can contain no more than 2

points, implying that there can be no more than 50

points inside the 1 by 1 square -- contradicting the

fact that there are 51 points in there. The diameter

of the smallest circle which contains a 1/5 by 1/5

box is (√2)/5. So, this size circle will do the job.

That is not to say that there are not smaller circles

which will also work. Thus, (√2)/5 is an upper bound

on the diameter of the smallest circle which is

guaranteed to encircle at least 3 of the 51 points.

If two (or more) points are "stacked", then they only

count as one point. Points are only different if they

have distinct coordinates in some coordinate system.

So, the problem is talking about 51 distinct points,

as is the usual convention.

You seem to believe that points must lie at the

lattice points of some grid. They don't. They can

be sprinkled about in any way you like.

You said, "Superprismatic: (√2)/5 is greater, yes,

but I don't see a layout that requires a circle this

big. Please let me know if I am missing something."

The answer is no, you're not missing something when

you say that. The fact that you (or I) don't see

a pattern that requires a circle that big does not

mean that such a layout does not exist.

I hope I have cleared things up a bit. By the way,

thanks for working on this problem.

I think curr3nt has it right with the Pigeonhole principle (Thanks...I used that type of distribution but didn't have the name for the concept), but he even points out that he couldn't place the last point in a 5x5 grid. With a 5x5 grid you place 2 points at each "hole" for 50 total with a minimum circle diameter of 1/4 (not(√2)/5 or 1/6 as previously posted) capturing 4 points. But again, this is only 50.

But adding that 51st "pigeon" on the 5x5 grid either puts 3 at a single point (making the smallest diameter circle become 0), or a point at the center of a square made by four of the 2-point stacks (making the circle min diameter (√2)/10). If I'm the guy laying out the points that you have to lasso, I will feel quite good about you picking a circle this small, because I can certainly pick a wider distribution of points.

Staying with the stacked point concept:

Expanding to a 5x6 grid (dividing the 1 unit side length by the respective number of points per side) will net the widest distribution of 51 points, some being stacked. By putting 2 points per gridpoint for any 21 gridpoints, and the remaining 9 gridpoint with 1 point a piece (or you could put 2 points at up to 25 gridpoints leaving 1 point and 4 empty gridpoints), you will have a location where a 1/6 diameter circle guarantees 3 points encircled, thus beating (√2)/10 as the upper bound for an array where stacking points is considered.

Now going to individual points (no stacking):

The points get closer together but you have to encircle a larger area. Using a 7x8 grid you will have several rectangles 1/6 x 1/7 whose corners are made by four points. The only way to capture 3 points is to have a circle equal to the diagonal of this rectangle, thus my before mentioned answer of (85/1764)^(1/2) = 0.21951... is the smallest diameter to assure 3 points.

Superprismatic: (√2)/5 is greater, yes, but I don't see a layout that requires a circle this big. Please let me know if I am missing something.

[Guest]

Thanks superprismatic for the explanation. I see now why that is the upper bound.

I definitely agree that there may be a patterned or random distribution that exists despite my lack of site, but my gut says a smaller diameter can be proved. I just lack the theory to prove my thoughts. Your explanation of the pigeonhole principle does give me another idea to further minimize the circle, but contemplate I must.

Great Puzzle! Thanks for posting.

First, let me explain the 5 by 5 pigeonhole argument.

We place a 5 by 5 grid over the square which contains

an arbitrary pattern of 51 points. By the pigeonhole

principle, there must be at least one 1/5 by 1/5 square

which contains at least 3 points somewhere in it. This

is true because, if we assume it is not true, then each

of those 1/5 by 1/5 boxes can contain no more than 2

points, implying that there can be no more than 50

points inside the 1 by 1 square -- contradicting the

fact that there are 51 points in there. The diameter

of the smallest circle which contains a 1/5 by 1/5

box is (√2)/5. So, this size circle will do the job.

That is not to say that there are not smaller circles

which will also work. Thus, (√2)/5 is an upper bound

on the diameter of the smallest circle which is

guaranteed to encircle at least 3 of the 51 points.

If two (or more) points are "stacked", then they only

count as one point. Points are only different if they

have distinct coordinates in some coordinate system.

So, the problem is talking about 51 distinct points,

as is the usual convention.

You seem to believe that points must lie at the

lattice points of some grid. They don't. They can

be sprinkled about in any way you like.

You said, "Superprismatic: (√2)/5 is greater, yes,

but I don't see a layout that requires a circle this

big. Please let me know if I am missing something."

The answer is no, you're not missing something when

you say that. The fact that you (or I) don't see

a pattern that requires a circle that big does not

mean that such a layout does not exist.

I hope I have cleared things up a bit. By the way,

thanks for working on this problem.

Edited January 17, 2011 by Copernicus

[Guest]

Thanks.

Yes thanks for pointing out my mistake, I was ignoring the fact that the smallest circle must be guaranteed to encircle 3 points under any arrangement. However, 7x7 is the way to go if you want to spread the 49 points as further as possible.

It is equivalent to divide the square into small grids of 6x6 and you put a point at every vertex of small squares. Therefore, a slight improvement. A circle that circumscribes a small grid (which has the radius of sqrt(2)/6) will be guaranteed to encircle at least 3 points (actually 4) with 49 points in the square. It can now be deduced with 51 points in the square, a circle of this radius can also be guaranteed to include 3 points if properly placed. (You can't use anything like 7x8 grid because you will use all the 51 points and still has not completed the pattern, hence failing to prove it is a pattern where points are furthest away from one another.)

[k-man]

The worst possible distribution of points is the one where all points are at equal distances from the nearest points. This is achieved by placing the points in the following pattern

This pattern actually allows placing 52 points instead of 51 in a square. The boundaries of this pattern don't make a perfect square and to fit this pattern in the perfect square it needs to be "slightly squeezed" vertically. That's why the answer I'm posting here can be slightly improved upon.

So, ingoring the "slight squeezing" necessary and accepting x=1/6 the diameter of a circumscribed circle is at most (√3)/9.

[superprismatic]

I'm not sure what you mean by "worst possible".

If I were to take a stab at what that meant, I would

say that the worst possible distribution of points

is one which makes the smallest distance between

two points in the distribution as large as possible.

It is not clear that this is the same as "one where

all points are at equal distances from the nearest

points". I know, for example, that these are not

equivalent for 8 points on the surface of a sphere.

The "worst possible" with your criteria could be for

these 8 points to form the vertices of a cube. But

my "worst possible" criteria would put the 8 points

at the vertices of a quite different polyhedron.

In any case, why is the "worst possible" for 51

points the same as it is for 52? Instead of using

4 rows of 7 and 4 rows of 6 for 52 points, you

could have used 3 rows of 9 and 3 rows of 8 for

51 points.

It seems to me that proof is required to show that

using a particular spread of points for your

calculations is sufficient to prove the general case.

The worst possible distribution of points is the one where all points are at equal distances from the nearest points. This is achieved by placing the points in the following pattern

This pattern actually allows placing 52 points instead of 51 in a square. The boundaries of this pattern don't make a perfect square and to fit this pattern in the perfect square it needs to be "slightly squeezed" vertically. That's why the answer I'm posting here can be slightly improved upon.

So, ingoring the "slight squeezing" necessary and accepting x=1/6 the diameter of a circumscribed circle is at most (√3)/9.

[k-man]

I got some more time to polish my solution, so here are some additional thoughts and the final answer. The lower bound from the same distribution of the points can be estimated by fitting the pattern from my previous post into the unit square making x=2/(7√3). From this value of x the lower bound of the circle diameter is 4/21. So, our answer should be somewhere in the range of 4/21 < d < (√3)/9 or in decimal approximation 0.19048 < d < 0.19245

The ultimate answer, in my opinion, lies in stretching the pattern to fit the unit square perfectly. After stretching, the distance between points will not be the same anymore, but will be as close to being the same as possible and there will be points on every edge of the square. Increasing the distance in one place will mean decreasing it somewhere else. So, after stretching the pattern we end up with points forming isosceles triangles with the base of 1/6 and sides of 2/(7√3). After some calculations the diameter of the circumscribed circle is 16/(7√143) or approximately 0.19114

[k-man]

I'm not sure what you mean by "worst possible".

If I were to take a stab at what that meant, I would

say that the worst possible distribution of points

is one which makes the smallest distance between

two points in the distribution as large as possible.

It is not clear that this is the same as "one where

all points are at equal distances from the nearest

points".

By "worst possible", in the context of this puzzle, I meant the distribution of points that maximizes the distance between any two points, which is the same as your definiton. Maybe I didn't describe the distribution very well, but that's why I attached the image.

I know, for example, that these are not

equivalent for 8 points on the surface of a sphere.

The "worst possible" with your criteria could be for

these 8 points to form the vertices of a cube. But

my "worst possible" criteria would put the 8 points

at the vertices of a quite different polyhedron.

I'm not sure I follow you here completely, but some things that work in 2 dimensions don't work once you apply them to a 3-dimensional problem.

In any case, why is the "worst possible" for 51

points the same as it is for 52? Instead of using

4 rows of 7 and 4 rows of 6 for 52 points, you

could have used 3 rows of 9 and 3 rows of 8 for

51 points.

It seems to me that proof is required to show that

using a particular spread of points for your

calculations is sufficient to prove the general case.

I agree that I haven't provided a formal proof of my solution, but that's all I got for now.