# How many circles needed to pass through each of 5x5 lattice points? 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?

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

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.

• The ASCII representations here were very helpful for understanding the proof. Jan 5, 2021 at 2:05
• Though, we have a 4 point circle whose origin is the center and covers the four corners Jan 5, 2021 at 2:31
• @zixuanisbadatPuzzling That's fine, as long as there's one circle with 4 points or less, the proof goes through.
– xnor
Jan 5, 2021 at 2:31
• "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.) Jan 5, 2021 at 2:32
• @PaulPanzer Good find, let me see if I can fix this.
– xnor
Jan 5, 2021 at 2:34