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?

  • 2
    $\begingroup$ Is the set a 5x5 rectangle of lattice points, or do we have 25 lattice points all over the place? $\endgroup$ Jan 4, 2021 at 20:56
  • 1
    $\begingroup$ I added a picture to clarify! $\endgroup$
    – ThomasL
    Jan 4, 2021 at 21:10
  • 2
    $\begingroup$ oeis.org/A262355 $\endgroup$
    – RobPratt
    Jan 4, 2021 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, 2021 at 20:50

1 Answer 1


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



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.

  • $\begingroup$ The ASCII representations here were very helpful for understanding the proof. $\endgroup$
    – bobble
    Jan 5, 2021 at 2:05
  • $\begingroup$ Though, we have a 4 point circle whose origin is the center and covers the four corners $\endgroup$ Jan 5, 2021 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, 2021 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$ Jan 5, 2021 at 2:32
  • $\begingroup$ @PaulPanzer Good find, let me see if I can fix this. $\endgroup$
    – xnor
    Jan 5, 2021 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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