11
$\begingroup$

enter image description here

You are given a 5x5 set of lattice points. What is the minimum number of circles, which pass through each of the 25 points at least once?

$\endgroup$
4
  • 2
    $\begingroup$ Is the set a 5x5 rectangle of lattice points, or do we have 25 lattice points all over the place? $\endgroup$ – new QOpenGLWidget Jan 4 at 20:56
  • 1
    $\begingroup$ I added a picture to clarify! $\endgroup$ – ThomasL Jan 4 at 21:10
  • 2
    $\begingroup$ oeis.org/A262355 $\endgroup$ – RobPratt Jan 4 at 22:00
  • $\begingroup$ OEIS acknowledges that doesn't seem to generalize to NxN. Also, for the same problem with circular arcs, see A187679, which doesn't seem to have been investigated at n=7 or beyond. $\endgroup$ – smci Jan 6 at 20:50
10
$\begingroup$

Here's a proof we can't do it with less than

5

circles.

Each circle covers at most 8 points. In fact, the max is 6 points except for these five 8-point circles:

x O x O x   x O O x x   x x x x x   x x x x x   x x O O x
O x x x O   O x x O x   x O O x x   x x O O x   x O x x O
x x x x x   O x x O x   O x x O x   x O x x O   x O x x O
O x x x O   x O O x x   O x x O x   x O x x O   x x O O x
x O x O x   x x x x x   x O O x x   x x O O x   x x x x x

Note that any two of the 8-point circles overlap at two points. This means that each one beyond the first covers 6 new points at best. So, the total point coverage from 4 circles is at most 8 + 6 + 6 + 6 = 26 points. That's just above 25 points in the grid, but this leave little slack, and we run into trouble covering the corners or center.

One of the five 8-point circles must be present. First, say it's the first-listed one:

x O x O x
O x x x O
x x x x x
O x x x O
x O x O x

Then, it's not possible to cover the center point while covering 4 points not already covered by that 8-point circle. This is because the only >4-point circle covering the center is below, with lowercase o marking redundantly covered points.

O o x x x
x x O x x
x x O x x
o O x x x
x x x x x

If it's one of the other 8-point circle, we can say it's the one below on account of symmetry.

x O O x x
O x x O x
O x x O x
x O O x x
x x x x x

Any circle that covers the top left corner gives at most 4 new points not already covered by this eight-point circle, since the only >4-point circles covering that corner are those below and reflections, with redundant points marked with lowercase o.

O o x x x   O x o x x
x x O x x   x x x o x
x x O x x   x x x x x
O o x x x   x x x O x
x x x x x   O x O x x

Either way we're limited to 8 + 6 + 6 + 4 = 24 points covered.

$\endgroup$
7
  • $\begingroup$ The ASCII representations here were very helpful for understanding the proof. $\endgroup$ – bobble Jan 5 at 2:05
  • $\begingroup$ Though, we have a 4 point circle whose origin is the center and covers the four corners $\endgroup$ – new QOpenGLWidget Jan 5 at 2:31
  • $\begingroup$ @zixuanisbadatPuzzling That's fine, as long as there's one circle with 4 points or less, the proof goes through. $\endgroup$ – xnor Jan 5 at 2:31
  • $\begingroup$ "That's because the only type of circle covering >4 points including a corner is the 6-point circle below, but it covers only one corner, so we can't cover all four corners while still having our 8-point circle." Looks obviously wrong to me. (Take the large 8 point circle and move it one g.u. either horizontally or vertically.) $\endgroup$ – Paul Panzer Jan 5 at 2:32
  • $\begingroup$ @PaulPanzer Good find, let me see if I can fix this. $\endgroup$ – xnor Jan 5 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.